# Division problem

Problem statement

Five sailors were cast away in an island, inhabited only by monkeys. To provide food, they collected all the coconuts that they could find. During the night, one of the sailors woke up and decided to take his share of the coconuts. He divided them into 5 equal piles and noticed that one coconut was left over, so he threw it to the monkeys; he then hid his pile and went to sleep. A little later a second sailor awoke and had the same idea as the first one. He divided the remainder of the coconuts into 5 equal piles, discovered also that one coconut was left over, and threw it to the monkeys. He then hid his share and went back to sleep. One by one the other three sailors did the same thing, each throwing one coconuts to the money. The next morning, all sailors looking sharp and ready for breakfast, divided the remaining pile of coconuts into five equal parts, and no coconuts was left over this time. Find the smallest number of coconuts in the original pile.

My solution was, each time a sailer take his share, I recalculate the number of coconut:

1. $n = 5\cdot q_0 + 1$ $\to$ # left = $\frac{4}{5}\cdot q_0 = \frac{4}{5}\cdot \frac{n - 1}{5}$

2. $\frac{4}{5}\cdot q_0 = 5 \cdot q_1 + 1 \to$ # left $= \frac{4}{5}\cdot q_1 ....$

Continuing this process, I ended up with a very strange fraction:

$$\frac{(256\cdot n - 464981)}{1953125}$$

Then I set this fraction to $5\cdot k$, since the last time # coconuts is divisible by $5$, to solve for $n$.
Am I in the right direction? Any hint would greatly appreciated.

Thanks,
Chan

-
Another monkey question! Are we going to be seeing a "monkeys" tag soon? :) – Pete L. Clark Feb 7 '11 at 5:51

You wrote that $n = 5q_0 + 1$, so then the first sailor threw away a coconut, and kept $q_0$ coconuts. The remaining number of coconuts is $4q_0$!

So then you write:

$$n = 5q_0 + 1$$ $$4 q_0 = 5q_1 + 1$$ $$4 q_1 = 5q_2 + 1$$ $$4 q_2 = 5q_3 + 1$$ $$4 q_3 = 5q_4 + 1$$ $$4 q_4 = 5q_5$$

Now you know that $q_5 > 0$, so $n$ will be smallest when $q_5 = 1$. (Of course if they had nothing for breakfast, do the following with $q_0 = 0$).

You must also consider that when the fifth sailor was taking his share, after throwing away a coconut, the remaining number of coconuts was divisible by $5$. So

$$q_4 = \frac{5q_5}{4}$$

must be an integer. Let's write $q_5 = 4k_0$. Then writing the equations backwards, and expressing $q_3$ with $q_{4}$ yields:

$$4 q_4 = 5q_5 = 20k_0 \text{ so } q_4 = 5k_0$$ $$4 q_3 = 5q_4 + 1 = 5^2k_0 +1$$

Again you must make sure that $\frac{5^2k_0 +1}{4}$ is an integer. Continue on until you reach $n$. You will be reexpressing the $k_0$ from here on (that's why I added the subscript).

-
@milcak: Thanks a lot for your hint. I'm happy because this is the first time I feel like I was on track ^_^! – Chan Feb 7 '11 at 7:00
@Chan you probably even did the backwards direction correctly, but the mistake in the begginning created that nasty fraction. Try it now, if you need any additional hint let me know – milcak Feb 7 '11 at 7:04
@milcak: I ended up with this equation 256n - 5^6k0 = 2101. Is it strange? Then now I have to solve for n in term of k0? I lost again :(. – Chan Feb 7 '11 at 8:14
What I meant to say, is that you have to establish what form $k_0$ is in order to have $\frac{5^2k_0 +1}{4}$ always an integer, for example $k_0 = ak_1 + b$ for some $a,b$. Then you will have $q_3$ equal to some expression containing $k_1$. Then you go up a step - get $q_2$ equal to some expression containing $k_2$ etc. In the end you will have $n$ equall to some expression containing $k_4$, then set $k_4 = 1$ to get the lowest number of coconuts. – milcak Feb 7 '11 at 16:40
@micak: Thanks again, but I don't understand how k4 = 1 will yield the least number of coconut. Could you explain this? – Chan Feb 7 '11 at 16:49

You asked for a hint, so I won't give the full answer:

Step (1): Realize that if K is an answer, so is K + n*5^(5+1) for any n. Step (2): The hint for this step will probably give the whole thing away so it is withheld Step (3):

-
Thanks! But I'm not sure I understand your hint. You said: K + n*5^(5+1) for any n, this is not an equation, so how could I find K? – Chan Feb 7 '11 at 6:14