N pirates steal their share of bananas to the benefit of a monkey

Question

The following is a type of logic / math puzzle I've yet to see on this site. I feel it belongs because the kernel of this problem can be reworked into other puzzles.

$N$ pirates find themselves marooned on an island with no food stores, no other people, and no animal life besides one monkey. There are, however, many banana trees. The pirates spend the entire day gathering bananas to tide them over as they work on a raft.

After they go to sleep, one pirate wakes up, decides he doesn't trust anyone else, and tries to take his even $(\frac{1}{N})^{\mathrm{th}}$ share of the bananas from the big pile. Finding one extra banana over an even split, he gives one to the monkey and takes $(\frac{1}{N})^{\mathrm{th}}$ of the remaining pile to hide.

After the first pirate finally falls asleep, a second pirate wakes up and decides the same thing but does not realise the other pirate had taken his share. Finding one extra banana over an even split, he gives one banana to the monkey and takes $(\frac{1}{N})^{\mathrm{th}}$ of the remaining pile to hide it.

All N pirates wake up over the night, do the same thing and every time they find one more banana than an even split, give one to the monkey, and take $(\frac{1}{N})^{\mathrm{th}}$ of the remaining pile.

When morning comes and all $N$ pirates wake up, they see the greatly diminished pile and a happy fat monkey.

The question is: how many bananas could there have been in the original pile for this to occur?

Answer 1

The basic idea is to work backwards.

The last pirate must have found $N+1$ bananas, because he had to find enough bananas remaining for at there to be least 1 banana in the pile left for each pirate. He took 1, fed 1 to the monkey, and left $N-1$. That $N+1$ means that the next to last pirate found $ \frac N{N-1}\cdot (N+1)+1$ and so on.

A cute trick is to recognize that there could have been

$-(N-1)$ bananas. Each pirate gives the monkey $1$, takes $-1$, and leaves the pile the same size as before. Since we need to divide it by $N$ for each pirate, the next solution is higher by $N^N$, so the minimal positive solution is $N^N-N+1$ bananas.

Answer 2

The solution is equivalent to solving the $N+1$ Diophantine equations

$B$ number of bananas
$n$ number of pirates
{$a_1, a_2, .... a_n$} how many banana get each pirate.
$m$ the banana for the monkey (for this case is 1).

$B = na_1+m$
$B-a_1-m = na_2+m$
$B-a_1-a_2-2m = na_3+m$
$\vdots$
$B-a_1-a_2-a_3-...-a_n-nm = na+m$

Which can be rewritten as

$B = na_1+m $
$(n-1)a_1 = na_2+m $
$(n-1)a_2 = na_3+m $
$\vdots$
$(n-1)a_{n-1} = na_n+m $
$(n-1)a_n = na+m.$

Since there are n+1 equations in the n+2 unknows you can found all solutions as:

$B=kn^{n+1}-m(n-1), $ where k is an arbitrary integer

so for k = 1 and m = 1

$B=n^{n+1}-(n-1) $

Note in this case the next morning after all pirate wake up will be enough bananas so each pirates get an even number with 1 banana remaining for the monkey.

Because that wasn't a requirement of the puzzle a small value of banana will still solve the problem.

$B=n^{n}-(n-1) $

Case n = 4
$B_a$ = 253

(1) take 63 monkey 1 remaining 189
(2) take 47 monkey 1 remaining 141
(3) take 35 monkey 1 remaining 105
(4) take 26 monkey 1 remaining 78
Next morning every pirate get 19 bananas and monkey get 2 bananas

$B_b$ = 1021

(1) take 255 monkey 1 remaining 765
(2) take 191 monkey 1 remaining 573
(3) take 143 monkey 1 remaining 429
(4) take 107 monkey 1 remaining 321
Next morning every pirate get 80 bananas and monkey get 1 banana

Answer 3

Number of bananas = 765
(1) take 191 monkey 1 remaining 573
(2) take 143 monkey 1 remaining 429
(3) take 107 monkey 1 remaining 321
(4) take 80 monkey 1 remaining 240
Next morning every pirate get 60 bananas equally.
But I don't know how exist the formula B= n^n+1-(n+1) for 765