Sunday, July 8, 2012

The coconut stack, the greedy monkey, and the thieves

I heard this funny small riddle from Sebastian Thrun on their (very good) Udacity A.I. course.

At sunset, p=5 thieves are on a beach next to a large coconut stack guarded by a monkey. The agree to go to sleep, share the coconut stack the next morning and go their different routes.
But they are all distrustful of one each other.

So little time after everybody is silent, but the monkey which does not and will sleep, and seems to be asleep, the first thieve wakes up, go to the coconut stack, take b=1 coconut to give to the monkey (in effect paying for its silence), takes a fraction s/p (s=fraction of a thieve's subjective fair share of the stack, irrespective of the planned sharing on the next morning=1) from the remaining coconuts and go hide it under a palm tree some way from the beach where everybody is lying. This way, ponders the first thieve, I am certain I will at least get my fair share of the coconuts. And on this pleasant thought, he goes back to sleep with the others.

A little later the second thieve wakes up too, unaware of what the first thieve did. He goes the coconut stack, gives b coconut to the monkey, takes a fraction s/p from the remaining coconuts, and go hide it under another palm tree in the neighborhood.

And so on, one by one, all the other thieves wake up, give b coconuts to the monkey, take and hide a fraction s of the remaining coconuts.  As the coconut stack is large - and humans see better in daytime - and they cannot see that the coconut stack is smaller when they approach it at night as it was at sunset.

At dawn all p thieves wake up and give b coconuts to the monkey and equally share the remaining coconuts.

Coconuts cannot be split (without an axe, and even then their water would be lost..)

How many coconuts are there in the stack before the night ?
How many coconut each of the thieves will get away with ?