Puzzle time - Coconuts and a monkey

[Doctor Phibes]

@Klaus said in Puzzle time - Coconuts and a monkey:

Any questions?

What is the airspeed velocity of an unladen swallow?

[Axtremus]

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

Seriously try your hand at it for real. But yes that’s the right number.

Don't see how Klaus' numerical answer can be correct.
Actually I don't think there is a solution at all.
It seems the problem is over-constraint.
Maybe there is some ambiguity in the problem that I don't understand.

"Five men and a monkey, marooned on an island, collect a pile of coconuts to be divided equally the next morning." ==> assuming they intend to divide the pile equally among the five men, then the number of coconuts in the initial pile would need to be a multiple of five. (Klaus' answer does not satisfy this criterion.)

"During the night, however, one of the men decides he'd rather take his share now. He tosses one coconut to the monkey and removes exactly 1/5 of the remaining coconuts for himself." ==> this means, from the initial number of coconuts in the initial pile, after subtracting one from that number, the remaining pile is still divisible by five. This does not seem possible, as there is no "multiple of five" that is still divisible by five after subtracting one.

[taiwan_girl]

@Axtremus said in Puzzle time - Coconuts and a monkey:

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

Seriously try your hand at it for real. But yes that’s the right number.

Don't see how Klaus' numerical answer can be correct.
Actually I don't think there is a solution at all.
It seems the problem is over-constraint.
Maybe there is some ambiguity in the problem that I don't understand.

"Five men and a monkey, marooned on an island, collect a pile of coconuts to be divided equally the next morning." ==> assuming they intend to divide the pile equally among the five men, then the number of coconuts in the initial pile would need to be a multiple of five. (Klaus' answer does not satisfy this criterion.)

"During the night, however, one of the men decides he'd rather take his share now. He tosses one coconut to the monkey and removes exactly 1/5 of the remaining coconuts for himself." ==> this means, from the initial number of coconuts in the initial pile, after subtracting one from that number, the remaining pile is still divisible by five. This does not seem possible, as there is no "multiple of five" that is still divisible by five after subtracting one.

Exactly. That was my think also!!!!

[Klaus]

@Axtremus said in Puzzle time - Coconuts and a monkey:

"Five men and a monkey, marooned on an island, collect a pile of coconuts to be divided equally the next morning." ==> assuming they intend to divide the pile equally among the five men, then the number of coconuts in the initial pile would need to be a multiple of five. (Klaus' answer does not satisfy this criterion.)

You have overlooked the "toss one coconut to the monkeys" parts.

The first guy gets 3124, the second 2499, then 1999, 1599, 1279 and finally each gets 1023.

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