Puzzle time - Coconuts and a monkey
-
Seriously try your hand at it for real. But yes that’s the right number.
-
I will have to think this, but looking at it quickly, each time the number of coconuts would have to be divided by 5. It couldn’t because each time you throw to monkey, it makes an non five number.
Hmmmmm.
🧐Interesting to think
-
-
@kluurs said in Puzzle time - Coconuts and a monkey:
You know he just assigned the problem to his strudents and then went back to struggling with performing the Fröhlicher Landmann with both hands.
LOL
Actually, I performed it as "Angry Farmer who comes home drunk and beats his wife and kids".
-
@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.
So you want me to actually think?
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).
Based on that idea, one can combine all the information given in the puzzle into a huge equation which however only has a single variable, namely the number of coconuts x. The result is the number of coconuts from the sentence quoted above, y.
When doing it in the most straightforward way, the equation gets very long and quite repetitive. It looks like this:
y = 0.2(x - 0.2(x-1) - 0.2(x-0.2(x-1)-2) - 0.2(x-0.2(x-1)-0.2(x-0.2(x-1)-2)-3)-0.2(x-0.2(x-1)-0.2(x-0.2(x-1)-2)-0.2(x-0.2(x-1)-0.2(x-0.2(x-1)-2)-3)-4)-0.2(x - 0.2(x-1) - 0.2(x-0.2(x-1)-2) - 0.2(x-0.2(x-1)-0.2(x-0.2(x-1)-2)-3)-0.2(x-0.2(x-1)-0.2(x-0.2(x-1)-2)-0.2(x-0.2(x-1)-0.2(x-0.2(x-1)-2)-3)-4)-5)-6)
This can be simplified (multiplying everything out) to:
y = 0.2(0.32768x-3.68928)
To turn this into a true linear Diophantine equation (with integer coefficients), this can be rewritten as:
32768x - 500000y = 368928
According to Bézout's identity, this equation has an integer solution if the greatest common divisor of 32768 and 500000 (which is 32) divides 368928. This is true hence a solution exists.
Such a linear Diophantine equation can be solved using a variant of the Euclid algorithm for greatest common divisor described here. Applying that method to the equation above yields the solution space
x = -55062504 + k*15625
y = -3608577 + k * 1024The smallest x that is positive is for k = 3525:
-55062504 + 3525 * 15625 = 15621.This is the result I already posted above.
Add or subtract 15625 ad libitum for other solutions.
Any questions?
(Presumably there's a way simpler solution that I don't see, but I think at least it is a solution)
-
@Klaus said in Puzzle time - Coconuts and a monkey:
Any questions?
What is the airspeed velocity of an unladen swallow?
-
@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.
-
@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!!!!
-
@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.
-
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
DON’T let them eat cake.
- RFK Jr -
@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/5OK, 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).
-
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.
-
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.
-
@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.
-
That r(0..5) are integers is given in the problem definition.
-
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.
-
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
-
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.
