# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1072: Into three piles

From New Scientist #2228, 4th March 2000 [link]

Sunny Bay fisherfolk have a tradition that when they return home with a catch of fish they take all the catch and divide it into three piles. Over the years they have pondered the question: given a particular number of fish, how many different ways can they be divided up? For example, they could divide up 10 fish in 8 ways, namely, (1, 1, 8), (1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 2, 6), (2, 3, 5), (2, 4, 4) and (3, 3, 4).

One day the fisherfolk netted four large sea shells. On one side of each was one of the letters A, B, C and D and each shell carried a different letter. Each shell also had on its reverse one of the numbers 0, 1, 2, 3, 4, 5, 6, … The fisherfolk found that if they caught N fish then the number of different ways of dividing them into three piles was:

[(A × N × N) + (B × N) + C] / D

rounded to the nearest whole number. (Whatever the number of fish, the calculation would never result in a whole number plus a half; so there was no ambiguity about which whole number was the nearest).

I recall that D was less than 21, that is, the number on the reverse of the shell with D on it was less than 21. Also A and C were different.

What were A, B, C and D?

[enigma1072]

### One response to “Enigma 1072: Into three piles”

1. Jim Randell 5 March 2018 at 6:44 am

This Python program eliminates possible candidate coefficient sets (a, b, c, d) until there is only one remaining.

It runs in 99ms.

Run: [ @repl.it ]

```from enigma import irange, printf

# decompose total <t> into <k> numbers of at least <m>
def decompose(t, k, m=1, s=[]):
if k == 1:
if not(t < m):
yield s + [t]
else:
for x in irange(m, t - m * (k - 1)):
yield from decompose(t - x, k - 1, x, s + [x])

# initial possibilities for coefficients (a, b, c, d)
# when n < 3 the answer should be 0, so:
# when n = 0: c/d < 1/2
# when n = 1: (a + b + c) / d < 1/2
# when n = 2: (4a + 2b + c) / d < 1/2
rs = list()
for d in irange(1, 21):
for c in irange(0, 21):
t = d - 2 * c
if not(t > 0): break
for a in irange(0, 10):
if a == c: continue
for b in irange(0, 10 - a):
if not(2 * (a + b) < t and 8 * a + 4 * b + 2 * c < d): continue
rs.append((a, b, c, d))

# consider increasing values for n
# until the coefficient set is not ambiguous
n = 2
while len(rs) > 1:
# count the number of decompositions
n += 1
s = sum(1 for _ in decompose(n, 3))

# keep the coefficients that agree with this number
ss = list()
for (a, b, c, d) in rs:
(t, r) = divmod((a * n + b) * n + c, d)
if 2 * r == d: continue
if 2 * r > d: t += 1
if t != s: continue
ss.append((a, b, c, d))

printf("[n={n}, s={s}, candidates: {n0} -> {n1}]", n0=len(rs), n1=len(ss))
rs = ss

# output solution
for (a, b, c, d) in rs:
printf("a={a} b={b} c={c} d={d}")
```

Solution: A=1, B=0, C=0, D=12.

That is, the number of partitions of n into three positive integers is the nearest integer to n² / 12.

So we could write code to calculate the number of decompositions into 3 piles as:

```decompose3 = lambda n: (n * n + 6) // 12
```

The program starts with 292 candidate coefficient sets that give a result of 0 for n = 0, 1, 2, and then considers increasing values of n discarding coefficient sets that don’t match the computed number of partitions. By the time it has reached n = 9 it has narrowed the set of possibilities down to a single value, giving the solution.

The number of partitions appears in OEIS as sequence A069905 (which gives a link to a general proof of the formula [link]), although this is a subsidiary entry to A001399.

Incidentally, the constraint that A and C be different is required because (n² + 1) / 12 also works.

This site uses Akismet to reduce spam. Learn how your comment data is processed.