# Enigmatic Code

Programming Enigma Puzzles

## Enigma 209: Double number slab

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

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]

### 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).