Enigmatic Code

Programming Enigma Puzzles

Enigma 209: Double number slab

From New Scientist #1355, 28th April 1983 [link]

Enigma 209

A double number slab is just two rows of squares in a rectangle, with the correct number in each square. The numbers in the top row are just 1, 2, 3, …, n. In each bottom row square is written the number of times the number above it occurs in the completed slab.

So, for instance, if n=5, you fill in the top row as shown, and in the bottom row you replace A by the number of 1’s, B by the number of 2’s, …, E by the number of 5’s in the whole slab.

Given that n is at least 4, can you say:

(a) for what value of n is it impossible to complete the slab properly?
(b) for what value of n is each second-row number less than or equal to every number to the left of it?

[enigma209]

Advertisements

3 responses to “Enigma 209: Double number slab

  1. Jim Randell 25 July 2014 at 8:25 am

    This Python program runs in 47ms.

    from itertools import count
    from enigma import irange, printf
    
    # overall there are 2n numbers in the grid, so the sum of the numbers
    # on the bottom row must be 2n.
    
    def decompose(t, n, m):
      if n == 1:
        if not(t > m):
          yield [t]
      else:
        for i in irange(1, min(t - 1, m)):
          for r in decompose(t - i, n - 1, m):
            yield [i] + r
    
    def solve(n):
      # generate decompositions of 2n for the bottom row
      for r in decompose(2 * n, n, n + 1):
        # see if this row is consistent
        if all(x == r.count(i + 1) + 1 for (i, x) in enumerate(r)):
          yield r
    
    a = b = False
    n = 4
    while not(a and b):
      # count the total number of solutions, and descending solutions
      t = d = 0
      for r in solve(n):
        printf("[{n}: {r}]")
        t += 1
        if not any(y > x for (x, y) in zip(r[:-1], r[1:])): d += 1
      printf("[{n}: {t} solutions, {d} descending]")
    
      if not(a) and t == 0:
        printf("(a) n={n} has no solutions")
        a = True
    
      if not(b) and d > 0:
        printf("(b) n={n} has descending solutions")
        b = True
      
      n += 1
    

    Solution: (a) The slab cannot be completed for n=6; (b) For n=7 the second row is a descending sequence.

    In general for n > 6 there is a solution with the bottom row of the form:

    (n – 3, 3, 2, …, 2, 1, 1, 1)

    with (n – 7) 1’s in the middle.

    As can be seen all but 4 of the numbers in the bottom row are 1, hence there are n – 3 1’s overall (as required).
    There are two 2’s in the bottom row, hence 3 2’s overall.
    There is one 3 in the bottom row, hence 2 3’s overall.
    Whatever n – 3 is there is only one of it in the bottom row, hence 2 occurrences overall.
    The remaining numbers don’t appear in the bottom row, so only appear once in the overall grid.

  2. Brian Gladman 25 July 2014 at 1:37 pm
    from itertools import count
    
    # return partitions of 'nbr' into 'bits' bits of maximum
    # size 'max_bit' (return values in increasing order)
    def part(nbr, bits, max_bit, parts=[]):
      if bits == 0:
        if nbr == 0:
          yield parts
      elif nbr:
        for i in range(1 if not parts else parts[-1], min(nbr, max_bit) + 1):
          yield from part(nbr - i, bits - 1, max_bit, parts + [i])
    
    a = b = 0
    for n in count(4):
      has_sol = False
      # there are 2 * n numbers in total so the second row must have this sum
      for p in part(2 * n, n, n + 1):
        # the number of times a number occurs is one more than the number
        # of times it occurs in the second row
        cnt = [p.count(i) + 1 for i in range(1, n + 1)]
        # does this contain the same values as the partition itself?
        if sorted(cnt) == p:
          has_sol = True
          # is the second row in non-increasing order
          if cnt == sorted(cnt, reverse=True):
            b = n, cnt
      else:
        # if there is no solution for this n value
        if not has_sol:
          a = n
      if a and b:
        break
    print('(a) n = {} is not possible.'.format(a))
    print('(b) n = {0[0]:} gives a non-increasing sequence ({0[1]:}).'.format(b))
    
  3. Hugh Casement 17 August 2014 at 10:03 am

    In case it’s of interest, I found no slabs for n < 4, two for n = 4 (2, 3, 2, 1 and 3, 1, 3, 1), and one for n = 5 (3, 2, 3, 1, 1).

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: