### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,123)
- misc (2)
- project euler (2)
- puzzle (31)
- site news (43)
- tantalizer (31)
- teaser (3)

### Site Stats

- 168,282 hits

Programming Enigma Puzzles

14 February 2015

Posted by on **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

andyou, my organ-grinding friend”.How many monkeys were there?

[enigma258]

Advertisements

%d bloggers like this:

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.

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:

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 intoMequal 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

Mmonkeys required to do their procedure we get sequences that look like this:The first thing we notice is that as

Mincreases 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=10appears to be following[n(M^M) – (M – 1)]forn=1, 2, 3, 4, 5, 6, …And, in fact, this holds true for the other values ofMtoo. 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:So, we just need to look for cases where this number is divisible by

(M + 1).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.

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

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.

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.

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

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

But I can see from comments above that the way the teaser is phrased removes some of those I found.