What is the Minimum Number of Coconuts in This Desert Island Problem?

[Ackbach]

Here is this week's University POTW. It is a special problem for me, because it was an interesting stepping-stone to my marriage. So there's a bit of personal interest for you.

-----

The Coconut Problem

On a desert island, 5 men and a monkey gather coconuts all day. At nighfall the men go to sleep, leaving the monkey to guard the stash.

The first man wakes up during the night. He divides the stash into 5 equal shares and gives the remaining coconut to the monkey. He takes his share and puts the remaining 4 shares back together in a pile.

The 2nd, 3rd, 4th, and 5th men each wake up separately in succession throughout the night and do the same as the 1st man, each unbeknownst to the others; they each divide the (remaining) pile of coconuts into 5 shares, giving the extra coconut to the monkey, take their share and return the rest of the coconuts to a big pile.

When they all awaken in the morning, the pile is a multiple of 5 coconuts. What is the minimum number of coconuts originally present?

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

No one answered this week's POTW. You can read my solution below.

Spoiler

Let $x$ be the starting number of coconuts. The first guy divides up the pile into five equal portions, but there's one left over, which he gives to the monkey. That means he took $(x-1)/5$ coconuts. $x-1$ is divisible by $5$; the pile that's left is $4/5$ of $x-1.$ So we have $4(x-1)/5$ coconuts left after the first guy is done. We can already see the pattern here: subtract one, the multiply by $4/5$. We'll get:

1. $4(x-1)/5$
2. $4(4(x-1)/5-1)/5$
3. $4(4(4(x-1)/5-1)/5-1)/5$
4. $4(4(4(4(x-1)/5-1)/5-1)/5-1)/5$
5. $4(4(4(4(4(x-1)/5-1)/5-1)/5-1)/5-1)/5$

This last one is equal to some multiple of $5$, so we'll say it's $5y$. If this is so, then simplification yields that

$x = (8404+15625y)/1024$, or $- 15625 y + 1024 x = 8404$. This is a Diophantine equation ($x$ and $y$ have to be integers). We reduce the problem down two steps as follows:

Solve

$- 15625 y_0 + 1024 x_0 = 1$. We can just multiply $y_0$ and $x_0$ by $8404$ to get the final solution.

In order to solve $- 15625 y_0 + 1024 x_0 = 1$ we solve
$15625 y_1 + 1024 x_1 = 1,$ and substitute $y_1 = - y_0$ as our answer.

Solving $15625 y_1 + 1024 x_1 = 1$ is a matter of Euclid's algorithm:

\begin{align*}
15625 &= 1024 * 15 + 265 \\
1024 &= 265 * 3 + 229 \\
265 &= 1 * 229 + 36 \\
229 &= 6 * 36 + 13 \\
36 &= 2 * 13 +10 \\
13 &= 1 * 10 + 3 \\
10 &= 3 * 3 + 1.
\end{align*}

Going backwards yields:

\begin{align*}
1 &= 1 * 10 - 3 * 3\\
1 &= -3 * 13 + 4 * 10\\
1 &= 4 * 36 - 11 * 13\\
1 &= -11 * 229 + 70 * 36\\
1 &= 70 * 265 - 81 * 229\\
1 &= - 81 * 1024 + 313 * 265\\
1 &= 313 * 15625 - 4776 * 1024
\end{align*}

Thus, the solution to $15625 y_1 + 1024 x_1 = 1$ is $y_1 = 313, x_1 = -4776.$ Therefore, $y_0 = -313, x_0 = -4776.$ These make $- 15625 y_0 + 1024 x_0 = 1.$ Multiplying by $8404$ gives a starting number of $x = -40137504$ coconuts, a manifest absurdity.

All is not lost, however. Suppose we add to $x$ and $y$ two numbers $v$ and $w$, respectively, such that the new numbers $y+w$ and $x+v$ still satisfy the equation, but $y+w$ and $x+v$ are both positive. If we plug this into the equation above, we get $-15625(y+w)+1024(x+v)=8404.$ Note that $x$ and $y$ are the number found before: $x = -40137504$ and $y = -2630452.$
Thus we obtain $-15625 w + 1024 v = 0.$ Thus, $v = 15625 w / 1024.$ We would need to pick $w$'s that render $v$ an integer, obviously. Any multiple of $1024$ will do. Let's pick the smallest $w$ such that $y+w$ is positive. That means $w > 2630452$. But remember that $1024|w$. This means $w = 2630656$. Note that $2630656 = 1024 * 2569$. With this $w$, we have $v = 40140625$. Check: is $x+v>0?$ Recall that $x = -40137504$. The answer is yes. So, we have that $y + w = 204$, and $x + v = 3121.$

My answer is that the starting amount is $3121$. The ending amount will be $1020$.