Puzzle time - Coconuts and a monkey

[jon-nyc]

Let's call r(0) the initial number of coconuts. r(1) the number remaining after the first guy threw one to the monkey and took 1/5th, r(2) after the second did, etc. r(5) is the amount remaining when they wake up, which then gets split between the 5 guys after tossing one to the monkey.

Note that

r(k) = 4(r(k-1)-1)/5

Now, Klaus expanded that for r(5) and came up with that nasty equation.

Let's instead employ a little trick. Lets define a simple translation:

a(k) = r(k) + 4

Now if you substitute that into the equation above you get

a(k) = a(k-1)*4/5

so a(5) = a(o)*(4/5)^5

Our original r(5) is 1 mod 5, to allow an even division after throwing one to the monkey. That means a(5) is 0 mod 5.

So a(0) needs to be a power of 5 big enough to clear out the denominator 5^5 and make the product a multiple of 5.

So, a(0) = 5^6 or 15625.

and r(0) = 15,621

[Klaus]

@jon-nyc said in Puzzle time - Coconuts and a monkey:

Let's instead employ a little trick. Lets define a simple translation:
a(k) = r(k) + 4
Now if you substitute that into the equation above you get
a(k) = a(k-1)*4/5

OK, that's neat and significantly simpler than what I did.

It's not so obvious where that translation stems from, though. Can you derive it? I believe these kinds of recurrence relations can be solved analytically.

Also, I think your solution also depends on the key insight I posted above:

I'd say the key idea here is the observation that it is sufficient to consider "the rest are split equally among the five men". It is sufficient to demand that this number is integer. If it is, everything else will be integer, too, because it's all multiplication with 5 and addition of integers only (which preserves integer-ness).

[jon-nyc]

I don’t know what you mean derive it. It didn’t take much insight to see that shifting 4 made the complications in the recursion equation go away.

Note that if you allow negative numbers of coconuts a starting number of -4 works also.

[jon-nyc]

In my solution the fact that all the r(k) are integers is a given from the problem definition. That all the a(k) are integers follows.

[Klaus]

@jon-nyc said in Puzzle time - Coconuts and a monkey:

Note that if you allow negative numbers of coconuts a starting number of -4 works also.

Yes, as I said above -55062504 + k*15625 is a solution for any integer k

[Klaus]

@jon-nyc said in Puzzle time - Coconuts and a monkey:

In my solution the fact that all the r(k) are integers is a given from the problem definition. That all the a(k) are integers follows.

You only make sure that a(5) resp r(5) is integer. An additional argument is needed for the other k's. It's not a difficult argument, but it's worth spelling out.

[jon-nyc]

That r(0..5) are integers is given in the problem definition.

[Klaus]

Yes, but it's not obvious that your solution fulfils that criterion.

[jon-nyc]

a(k) = (4/5)^k a(0).

a(k) = 2^2k*a(0)/5^k

since a(0) = 5^6,

a(k) = 2^2k *5^6/5^k = 2^2k * 5 ^(6-k)

It's apparent from that that a(k) will be integers for k in [0-5]. It follows that r(k) will be integers for the same range of k.

[jon-nyc]

Also from this:

a(5) = 2^10*a(0)/5^5

It follows that a(5) will be 0 mod 5 for a(0) = 5^6*i for any integer i.

So valid solutions for r(5) include 15625*i - 4 for any integer i.

Note that is equivalent to your expression:

-55062504 + k*15625

since -55062504 = -3524*15625 - 4

your expression becomes:

(k-3524)*15,625 - 4

or just 15,625*i - 4

[jon-nyc]

They published their solution and it’s kind of weak:

SOLUTION: You can solve this by considering two men instead of five, then three, then guessing. But the following argument is irresistible, once found.

There's an elegant "solution" to the puzzle if you allow negative numbers of coconuts(!). The original pile has -4 coconuts; when the first man tosses the monkey a coconut, the pile is down to -5, but when he "takes" 1/5 of this he is actually adding a coconut, restoring the pile to -4 coconuts. Continuing this way, come morning there are still -4 coconuts; the monkey takes one and the men split up the remaining -5.

It's not obvious that this observation does us any good, but let's consider what happens if there is no monkey; each man just takes 1/5 of the pile he encounters, and in the morning there's a multiple of 5 coconuts left that the men can split. Since each man has reduced the pile by the fraction 4/5, the original number of coconuts must have been a multiple of 56 (which shrinks to 45 x 5 by morning).

All we need to do now is add our two pseudo-solutions, by starting with 56 – 4 = 15,621 coconuts. Then the pile reduces successively to 4 x 55 – 4 coconuts, 42 x 54 – 4, 43 x 53 – 4, 44 x 52 – 4, and 45 x 5 – 4. When the monkey gets his morning coconut, we have 45 x 5 – 5 coconuts, a multiple of 5, for the men to split. This is best possible because we needed 55 x k – 4 coconuts to start with, just to have an integer number come morning, and to get 45 x k – 5 to be a multiple of 5 we needed k to be a multiple of 5.

I emailed my solution as more concise.