ETOOBUSY 🚀 minimal blogging for the impatient
More on monkeys and coconuts
TL;DR
Some add-ons to latest post Brute forcing “The monkey and the coconuts”.
In last post we saw that we could reduce the brute force attack first from 15625 candidates down to 1024, then down to one-fourth i.e. 256. This is already a factor of about 60, but of course we can do more.
In particular, for the basic puzzle we observed that the last division assigns L coconuts to each sailor, where L must be of the form L=4k−1.
So why stop here then?
Let’s rename L to L0, and let’s move on to the next step in the ladder, i.e. the amount of coconuts that are taken by the last sailor during the preliminar divisions that happen through the night. We will call this value L1 🙄
On the one hand, in the basic puzzle we can easily conclude that L1 must have the same shape as L0, i.e. be of the form:
L1=4k1−1On the other hand, we also know the exact relation between L0 and L1:
L1=(5L0+1)/44L1=5L0+15L0=4L1−1Putting these two together we can express L0 in terms of k1, let’s see where we get:
5L0=4(4k1−1)−1=16k1−5Now we can observe that the left hand side is divisible by 5, so the right hand side must be divisible by 5 too. As 16 is not divisible by 5, then k1 MUST be divisible by 5 itself, i.e.:
5L0=16⋅5k−5L0=16k−1This last relation is extremely interesting, because it tells us that we can iterate over one-sixteenth of the possible candidates between 1 and 1024, i.e. ranging 1≤k≤64. Even better times for a brute force attack from a human!
Well, the trend for the basic puzzle is set anyway… why even stop here? Doing the same for the following steps in the ladder brings us to further restrict the range of candidates:
L2→L0=64k−11≤k≤16L3→L0=256k−11≤k≤4L4→L0=1024k−11≤k≤1We don’t have to take any further step of course, because there’s no constraint for what comes out of L5.
Wait a minute… the last expression has one single candidate for k… giving L0=1023 that is precisely the solution to the puzzle!
Well… time and again some reasoning beats brute force!
After better reading the page on The monkey and the coconuts, it turns out that of course this approach was already described as a numerical approach. You can take a look at the page to see how a mix of a similar mechanism and some trial-and-error can be applied with the sieve approach, targeting Williams’s puzzle alternative.
Although, in this case… some brute force required.