Puzzle time - Coconuts and a monkey
-
Seriously try your hand at it for real. But yes that’s the right number.
"You never know what worse luck your bad luck has saved you from."
-Cormac McCarthy -
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
-
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.
@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)
-
@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.
-
@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!!!!
-
@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:
"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
-
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
@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.
"You never know what worse luck your bad luck has saved you from."
-Cormac McCarthy -
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.
