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

Questions:

How many coconuts are there in the stack before the night ?

How many coconut each of the thieves will get away with ?

Solution for any p, any s, b=1

Let

• m(0) be the initial number of coconuts
• m(i, for i from 1 to p) the number of coconuts left in the stack after thieve i
• c(i, for i from 1 to p) be the number of coconuts hidden by thieve i during the night
• c(p+1) the number of coconuts receive by each thieve openly on the next morning

The first thieve takes c(1):
$\frac{p}{s}c(1)+1 = m(0)$

The number of coconuts left after him is:
$m(1) = (\frac{p}{s}-1)c(1)$

The second thieve takes c(2):

$\frac{p}{s}c(2)+1 = m(1) = (\frac{p}{s}-1)c(1)$

Equally we have for all i from 2 to p:
$\frac{p}{s}c(i)+1 = m(i-1) = (\frac{p}{s}-1)c(i-1)$

Adding  $\frac{p}{s}-1$ on both sides of all these equations 
$\frac{p}{s}(c(i)+1) = m(i-1) = (\frac{p}{s}-1)(c(i-1)+1)$ i.e. for all i from 2 to p:
$c(i)+1 = \frac{s}{p}(\frac{p}{s}-1)(c(i-1)+1)$

Combining these equations, for all i from 1 to p-1:

$c(p)+1 = (\frac{p-s}{p})^{p-i}(c(i)+1)$

And in the case i=p-1:
$c(p)+1 = \frac{(p-s)^{p-1}}{p^p}(s*(m(0)-1)+p)$

Obviously for the final sharing s = 1:

$p*(p+1)+1 = m(p) = (p-1)*c(p)$

i.e. after adding (p-1)

$c(p+1)+1 = \frac{p-1}{p}(c(p)+1)$

Finally:

$c(p+1)+1 = \frac{(p-1)(p-s)^{p-1}}{p^{p+1}}(p+s(m(0)-1))$ $c(p)+1 = \frac{(p-s)^{p-1}}{p^p}(p+s(m(0)-1))$ $(...)$ $c(2)+1 = \frac{p-s}{p^2}(p+s(m(0)-1))$ $c(1) = s\frac{m(0)-1}{p}$
c(i+1) for all i from 1 to p+1 being an integer is the same as the right hand side above being an integer.
This is what defines m(0).

Solution for any p=5, s=1, b=1

The right hand side of the equation defining c(6)+1 is:

$\frac{2^{10}}{5^6}(4+m(0))$

2 and 5 being prime, m(0) must be:

$m(0) = k*5^6-4$ with k any integer

Conversely, all c(i) for i from 1 to 5 are integers because m(0)+4 can be divided by $5^i$ for any i from 1 to 5.

The smallest positive m(0) is 15621 (for k = 1).

All solutions

Below is the general - computer intensive - solution for any {p,s,b}.

(You need to download the CDF plugin)