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

Solutions Collecting From Web of "Division problem"

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

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