Enigmatic Code

Programming Enigma Puzzles

Enigma 258: Monkey business

From New Scientist #1405, 12th April 1984 [link]

A group of monkeys had a sackful of nuts. One night one of the monkeys decided secretly to take his share of the nuts, so he divided them into equal piles, one for each monkey: there was one nut left over so he gave it to his organ-grinder. He hid his own pile away and returned the remaining piles to the sack.

A little later than night the second monkey did precisely the same thing, divided the nuts into equal piles, one pile for each of the monkeys, and gave the odd remaining nut to the organ-grinder. He hid away his own pile and returned the rest of the piles to the sack.

This continued through the night, each monkey repeating the same performance not knowing that the others had already removed their shares.

The number of nuts originally in the sack was the smallest number possible for all this to have happened to that particular group of monkeys.

At this point the organ-grinder turned to the monkeys and said: “Isn’t this a rather clichéd puzzle?”, to which one of the monkeys replied: “Ah, yes, but in this case we are now able to divide the remaining nuts equally between all the monkeys and you, my organ-grinding friend”.

How many monkeys were there?

[enigma258]

Advertisements

6 responses to “Enigma 258: Monkey business

  1. Jim Randell 14 February 2015 at 8:28 am

    At first I thought this puzzle was flawed, but on careful reading it does have solutions that make sense, and we can take the smallest (and most reasonable) solution to be the answer to the puzzle.

    This Python program runs in 36ms.

    from itertools import count
    from enigma import irange, first, printf
    
    # generate numbers of nuts (initial, final)
    # such that each of M monkeys can secretly take a share
    def generate(M):
      # consider the final monkeys share
      for n0 in count(1):
        # how many nuts did the final monkey start with
        N = M * n0 + 1
        # and then for each of the other monkeys
        for _ in irange(2, M):
          (N, r) = divmod(N * M, M - 1)
          if r > 0: break
          # and 1 nut for the organ grinder
          N += 1
        else:
          # loop wasn't terminated by break
          yield (N, n0 * (M - 1))
    
    def main():
      # consider increasing numbers of monkeys
      for M in count(3):
        # find the smallest number of nuts
        for (N, n) in first(generate(M)):
          printf("[M={M} N={N} n={n}]")
          # divide the remaining nuts amongst the monkeys and the organ grinder
          (m, r) = divmod(n, M + 1)
          if r == 0:
            printf("M={M} N={N}")
            return
    
    main()
    

    Solution: There were 5 monkeys.

    This is the smallest possible solution – 5 monkeys and 3,121 nuts in the sack at the beginning.

    We can summarise the allocations of nuts below:

    Enigma 258 - Diagram

    But there are larger solutions, the next largest occurs with 9 monkeys and 387,420,481 nuts in the sack. If each nut weighs 1 gram then the sack would weigh over 380 tonnes, which would probably be a bit unwieldy (and take a long time to divide into 9 piles).

    The program considers increasing numbers of moneys (M, starting at 3), looking for the smallest possible number of nuts in the sack for that number of monkeys such that each monkey could divide the number of nuts into the sack into M equal piles with exactly one nut left over (this is implied, although not explicitly stated), hide one pile, and then return the remaining (M – 1) piles to the sack.

    Once this number is found (and the number of nuts remaining in the sack) we look to see if the remaining nuts can be equally divided into (M + 1) equal piles (one for each monkey and one for the organ grinder), if it can then we have found a solution to the problem.

    If we examine the number of nuts required for each of the M monkeys required to do their procedure we get sequences that look like this:

     3 → 25, 52, 79, 106, 133, 160, ...
     4 → 253, 509, 765, 1021, 1277, 1533, ...
     5 → 3121, 6246, 9371, 12496, 15621, 18746, ...
     6 → 46651, 93307, 139963, 186619, 233275, 279931, ...
     7 → 823537, 1647080, 2470623, 3294166, 4117709, 4941252, ...
     8 → 16777209, 33554425, 50331641, 67108857, 83886073, 100663289, ...
     9 → 387420481, 774840970, 1162261459, 1549681948, 1937102437, 2324522926, ...
    10 → 9999999991, 19999999991, 29999999991, 39999999991, 49999999991, 59999999991, ...

    The first thing we notice is that as M increases the first term in the respective sequence gets very big quite quickly, but the subsequent terms increase roughly linearly.

    The second thing we notice is that the sequence for M=10 appears to be following [n(M^M) – (M – 1)] for n=1, 2, 3, 4, 5, 6, … And, in fact, this holds true for the other values of M too. The (M^M) term explains why the numbers increase in size so quickly.

    This gives us a quick way of generating further solutions.

    When n=1 (the smallest number of nuts for a particular group of monkeys) the number of nuts remaining in the sack after all the monkeys have secretly taken their share is:

    (M – 1)^M – (M – 1)

    So, we just need to look for cases where this number is divisible by (M + 1).

    from itertools import count
    from enigma import irange, printf
    
    for M in count(3):
      # number of nuts at the start
      N = (M ** M) - (M - 1)
      # number of nuts at the end
      n = ((M - 1) ** M) - (M - 1)
      # can they be evenly distributed amongst the monkeys and the organ grinder?
      if n % (M + 1) == 0:
        printf("M={M} N={N} n={n}")
    

    It turns out that the numbers of monkeys where there are possible solutions are: 5, 9, 13, 21, 25, 29, 33, 37, 45, 57, 61, 73, 81, 85, 93, …

    These numbers are all one more than multiples of 4, but exclude 17, 41, 49, 53, 65, 69, 77, 89, 97, …, which I don’t see a pattern in.

    The setter could have excluded these higher solutions by putting an upper limit on the number of nuts the sack can contain, maybe up to 1 million.

    See [ http://mathworld.wolfram.com/MonkeyandCoconutProblem.html ] / OEIS A006091 for more information on the “Monkey and Coconut” problem.

    • Hugh Casement 14 February 2015 at 3:35 pm

      Please explain to me what is wrong with the solution I found:
      4 monkeys and 765 nuts.
      first monkey takes 191 and leaves 573;
      second monkey takes 143 and leaves 429;
      third monkey takes 107 and leaves 321;
      fourth monkey takes 80 and leaves 240;
      at each step one nut is given to the human.
      In the morning each of the five gets 48.
      The “organ grinder” is of course really an ethologist in disguise, Carlos’ aunt (Tia Maria), who is studying the behaviour of monkeys in Brazil (where the nuts come from).

      • Jim Randell 14 February 2015 at 4:10 pm

        765 isn’t the smallest possible starting number of nuts in the sack for a group of 4 monkeys, such that each monkey can discard one nut from the pile and divide the remaining nuts exactly between the 4 monkeys.

        That would be 253. But at the end there would be 78 nuts left, and they wouldn’t be able to divide them exactly amongst the 4 monkeys and the organ grinder. So there cannot be 4 monkeys in the group.

        • Hugh Casement 14 February 2015 at 7:08 pm

          Ah, yes.  I overlooked (or misread) the sentence starting “The number of nuts …”.
          Without it, there would be very many solutions: for example, 2 monkeys and 15, 27, 39, 51, … etc. nuts.  For that m, n = 3k + 1.
          Perhaps I should learn American Sign Language.

  2. Brian Gladman 17 February 2015 at 12:01 am
    from itertools import count
    
    # Start with N nuts and M monkeys and let a[i] be the i'th monkey's share on
    # round i (i = 0 .. M - 1) with the organ-grinder getting G nuts.   Let R be
    # the number of nuts left at the end (divided into M + 1 equal parts (A) for
    # the monkeys and the organ-grinder). We hence have for each round:
    #
    #    0       N = M.a[0] + G
    #    1       N - (a[0] + G) = M.a[1] + G
    #    2       N - (a[0] + a[1] + 2.G) = M.a[2] + G
    #    ...  
    #    M - 1   N - (a[0] + a[1] + .. + a[M - 2] + (M - 1).G) = M.a[M - 1] + G
    #    left    N - (a[0] + a[1] + .. + a[M - 1] + M.G) = R = (M + 1).A
    #
    # If we let b[k] = a[k] + G, these equations can be recast as:
    #
    #    N + (M - 1).G    = M.b[0]           k = 0
    #    (M - 1).b[k - 1] = M.b[k]           k = 1 .. M - 1 
    #    (M - 1).b[M - 1] = R + (M - 1).G    k = M
    #
    # Eliminating the b values now gives:
    #
    #    R + (M - 1).G = {(M - 1) / M}^M.{N + (M - 1).G}
    #
    # and hence:
    #
    #    M^M.{R + (M - 1).G} = (M - 1)^M.{N + (M - 1).G}
    #
    # Since M and (M - 1) have no common factors, we obtain:
    #
    #    R + (M - 1).G = k.(M - 1)^M
    #    N + (M - 1).G = k.M^M
    #
    # for k any integer.  Hence we obtain:
    #
    #    N  =  k.M^M - (M - 1).G
    #    R  =  k.(M - 1)^M - (M - 1).G
    
    G = 1
    for M in range(3, 41):
      for k in range(1, 50):
        N = k * M ** M - (M - 1) * G
        R = k * (M - 1) ** M - (M - 1) * G
        if not R % (M + 1):
          print('{:02d} {} {}'.format(M, N, R))
          break
    

    This gives solutions for all numbers of monkeys except those numbers in the sequence 3, 7, 11, 15, …

    # M N R
    # 04 765 240
    # 05 3121 1020
    # 06 233275 78120
    # 08 67108857 23059197
    # 09 387420481 134217720
    # 10 89999999991 31381059600
    # 12 98077104930805 34522712143920
    # ...
    

    This is not the same sequence as that given by Jim because he has used only the first solution in each sequence i.e. for k = 1 (n = 1 in his description).

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: