17
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is this for all sets of possible bananas? $\endgroup$ – awesomepi May 22 '14 at 15:58
  • $\begingroup$ ...The number of possible bananas is limited depending on N, N can be any natural number (except 1). $\endgroup$ – kaine May 22 '14 at 16:27
  • 2
    $\begingroup$ The way I remember it, concludes with the pirates waking up, finding a greatly diminished pile of bananas, each taking their share of $x$ bananas, and feeding the final banana to the monkey. That would give you a starting pint, but I'm not sure it's correct. $\endgroup$ – SQB May 23 '14 at 7:01
  • $\begingroup$ @SQB I did not remember it ending that way but that could be my bad memory. Mathematically though, I am pretty sure that would be the same as N+1 pirates so Ross's answer still applies. $\endgroup$ – kaine May 23 '14 at 12:52
  • $\begingroup$ @kaine it is not the same, since N+1 pirates would always divide by (N+1) here it is always a division by N, only it happens N+1 times with the waking up part. $\endgroup$ – Falco Aug 6 '14 at 11:22
19
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 100% correct. This is how I would have answered it. Note that after finding the negative solution $(1-N)$, every possible answer is $k*N^N-(1-N)$ for any integer value $k$ (even though negative answers are absurd). $\endgroup$ – kaine May 22 '14 at 16:18
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I like that you solved it for arbitrary m. $\endgroup$ – kaine Jan 15 '15 at 15:53
  • $\begingroup$ After read you reply, I realize my confusion was this part of Ross answer "The last pirate must have found N+1 bananas". That part isn't true even when he arrive the correct formula later. $\endgroup$ – Juan Carlos Oropeza Jan 15 '15 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.