Apples and Monkeys

[Guest]

There are 5 Monkeys and a number of apples. They want to divide the apples into equal shares, but all forget. They all go to sleep. In the middle of the night, the first monkey suddenly remembers, and goes and divides the apples into five equal groups. He finds out that there is an extra, and eats it. Then, he hides his share and goes to sleep. The second monkey remembers ten minutes later, divides the apples, and finds out there is an extra. He eats the extra, hides his share and goes to sleep. The third, fourth, and fifth all do the same process, and at the end, there are still many apples left. Assuming that the monkeys didn't cut any apples, what is the least number of apples that there could've been at the beginning?

[Guest]

One last thought: Extra kudos to whoever finds the general formula for the answer for arbitrary number of monkeys. I'm pretty sure this is possible so long as iterated functions count as a general formula - in other words, you can say "for M monkeys, you need to generate a function f and some integers i, j and k, all of which depend on M, and the answer is N apples where N = j+ f( f( f( ... f(i)...))), and f() is applied recursively M-k times" for example, and you provide the functional dependence of f, i,j,and k on M, of course.

[Guest]

Got it.

After a drive home and a few glasses of wine, here's what I have:

The general answer for M monkeys is as follows:

let h(M) = (M-1) * (M * (M-1)^(M-2) - 1)

let f(n) = M * n / (M-1) + 1

The answer for the minimum number of apples N to start with is then

N = f( f( f( ... f( h(M) ) ... ) ) )

... where f() is applied recursively, M-1 times.

I'm happy to see that this follows the form I suggested for the general answer, with i being h(M) above, j=0, and k=1.

If we were to restate the problem for 10 little monkeys the answer would be 9,999,999,991 apples instead of 3121.

Here are the solutions for M=3 up to M=10:

M N

=====

3 25

4 253

5 3121

6 46,651

7 823,537

8 16,777,209

9 387,420,481

10 9,999,999,991

The formula doesn't hold for M < 3. For M=2, it yields 3, when the correct answer is 7. This is because of the condition that after the final monkey is done, there must still be some apples left.

I think it holds, though, for all M >= 3. If anybody finds differently, let me know.

Edited March 1, 2009 by mrentropy

[Guest]

Duuuh --- now that I've had some sleep - the general answer for M monkeys is:

N = M^M - M + 1.

[Guest]

..... which follows the form given by pjharry. Sorry to flood the msg board. My interface won't let me delete/edit my previous posts.

[Guest]

i got 3121, but how is this possible?! this doesn't seem realistic at all, though...i'll check my work again

[sipun1987]

Ans is 621

621, 496, 396, 316, 252