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.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

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

%d bloggers like this: