Seven pirates wash ashore on a deserted island after their ship sinks. In order to survive, they gather as many coconuts as they can find and throw them into a central pile. As the sun sets, they all go to sleep.
One pirate wakes up in the middle of the night. Being the greedy person he is, this pirate decides to take some coconuts from the pile and hide them for himself. As he approaches the pile, though, he notices a monkey watching him. To keep the monkey quiet, the pirate tosses it one coconut from the pile. He then divides the rest of the pile into seven equally sized bunches and hides one of the bunches in the bushes. Finally, he recombines the remaining coconuts into a single pile and goes back to sleep. (Note that individual coconuts are very hard, and therefore indivisible.)
Later that night, a second pirate wakes up with the same idea. She tosses the monkey one coconut from the central pile, divides the pile into seven bunches, hides her bunch, recombines the rest, and goes back to sleep. After that, a third pirate wakes up and does the same thing. Then a fourth. Then a fifth, and so on until all seven pirates have hidden a share of the coconuts.
In the morning, the pirates look at the remaining central pile and notice that it has gotten quite small. They decide to split the pile into seven equal bunches and take one bunch each. (Note: The monkey does not get one this time.)
If there were N coconuts in the pile originally, what is the smallest possible value of N?
Solution
Originally there are $N$ coconuts. When the first pirate goes to sleep, there are $N_1$, and so on until finally the pirates evenly divide $N_7$ coconuts.
We know that $N_7$ is divisible by $7$. But it is also divisible by $6$, because it is what is left over after a pirate divides some coconuts into seven equal piles and takes one of the piles. So for some $M_7$::
\[N_7 = 6\times 7M_7\]$N_6$ is $N_7$ plus $\frac{N_7}{6}$ plus $1$. It too must be divisible by $6$, by the same reasoning. Since $N_7$ is itself divisible by 6, $\frac{N_7}{6}+1$, which is $7M_7+1$, must also be divisible by $6$. So $M_7$ must be $5$, modulo $6$ (i.e., one of $5$, $11$, $17$, \ldots). That is, $M_7$ is $5 + 6M_6$ for some $M_6$, and:
\[N_6 = \frac{7}{6}N_7 + 1 = \frac{7}{6} \times 42(5 + 6M_6) + 1 = 6(41 + 7^2M_6)\]By the same reasoning, $N_6/6 + 1$, which is $42 + 7^2M_6$, is divisible by $6$, and hence so is $7^2M_6$ and hence $M_6$ itself is some multiple $M_5$ of $6$, and:
\[N_5 = \frac{7}{6}N_6 + 1 = \frac{7}{6}\times 6(41 + 7^2\times 6M_5) + 1 = 6(48 + 7^3M_5)\]Continuing, $N_5/6 + 1$, which is $49 + 7^3M_5$, is divisible by $6$. Therefore $343M_5$ is $5$, modulo $6$, and since $343$ is $1$, modulo $6$, $M_5$ must be $5$, modulo 6. That is, $M_5$ is $5 + 6M_4$, for some $M_4$, and:
\[N_4 = \frac{7}{6}N_5 + 1 = \frac{7}{6} \times 6(48 + 7^3\times (5+6M_4)) + 1 = 6 (2057 + 7^4 M_4)\]Once more, $N_4/6 + 1$, which is $2058 + 7^4M_4$, is divisible by $6$ and hence $M_4$ is $0$, modulo 6. That is, $M_4$ is $6M_3$ for some $M_3$, and:
\[N_3 = \frac{7}{6} \times 6 (2057 + 7^6 \times 6M_3) + 1 = 6 (2400 + 7^5 M_3)\]Running short on new conjunctions, $N_3/6 + 1$, which is $2401 + 7^5M_3$, is divisible by $6$. Thus, $7^5M_3$ is $5$, modulo $6$. $7^5$ itself is $1$, modulo $6$, and so $M_3$ is $5$, modulo $6$; that is, $M_3$ is $5 + 6M_2$ for some $M_2$, and:
\[N_2 = \frac{7}{6} \times 6(2400 + 7^5(5 + 6M_2)) + 1 = 6 (100841 + 7^6 M_2)\]Going here again, $N_2/6 + 1$, which is $100842 + 7^6M_2$, is divisible by $6$. Thus, $M_2$ is divisible by $6$, and hence is $6M_1$, for some $M_1$, and:
\[N_1 = \frac{7}{6} \times 6 (100841 + 7^6 \times 6M_1) + 1 = 6(117648 + 7^7M_1)\]Finally (!), $N$ is $N_1 + N_1/6 + 1$, and it need not be divisible by $6$, because it did not come from any pirate’s meddling (thanks to Guy in the comments for this observation, which I initially missed). So:
\[N = \frac{7}{6} \times 6(117648 + 7^7M_1) + 1 = 823537 + 7^8\times M_1\]The smallest value for $N$, gotten by letting $M_1$ be $0$, is 823,537.