
5. They were $n$ fishermen and they caught $r_{0}$ fishes together and put them in the fish tank. They come one by one to take their part of the catch. Everyone thinks he is the first one at the tank and after letting one fish free he takes exactly $1 / n$ of the current number of fishes in the tank. Determine the smallest possible $r_{0}$ (depending on $n \geqslant 2$ ) if everyone takes home at least one fish.


Solution. Let us denote $r_{k}$ the number of fishes in the tank after the $k$-th fisherman took his fishes, $k=1,2, \ldots, n$.

These numbers are determined by $r_{0}$ and the reccurence formula

$$
r_{k+1}=\frac{n-1}{n}\left(r_{k}-1\right) \quad(k=0,1, \ldots, n-1) .
$$

For convenience, we rewrite the formulas as

$$
r_{k+1}=q \cdot r_{k}+d, \quad \text { kde } \quad q=\frac{n-1}{n} \quad \text { a } \quad d=\frac{1-n}{n} \text {. }
$$

First, we derive the explicit expression of the sequence given by the linear recurrence formula $r_{k+1}=q \cdot r_{k}+d(q, d=$ const.). For $q=1$ it is just an arithmetic progression, for $q \neq 1$ we have

$$
\begin{aligned}
& r_{1}=q r_{0}+d, \\
& r_{2}=q r_{1}+d=q\left(q r_{0}+d\right)+d=q^{2} r_{0}+(q+1) d, \\
& r_{3}=q r_{2}+d=q\left(q^{2} r_{0}+(q+1) d\right)+d=q^{3} r_{0}+\left(q^{2}+q+1\right) d, \\
& r_{4}=q r_{3}+d=q\left(q^{3} r_{0}+\left(q^{2}+q+1\right) d\right)+d=q^{4} r_{0}+\left(q^{3}+q^{2}+q+1\right) d,
\end{aligned}
$$

and we get the expression

$$
r_{k}=q^{k} r_{0}+\left(q^{k-1}+q^{k-2}+\cdots+q+1\right) d=q^{k}\left(r_{0}+\frac{d}{q-1}\right)-\frac{d}{q-1} .
$$

Thus

$$
r_{k}=q^{k} r_{0}+\frac{\left(q^{k}-1\right) d}{q-1}=q^{k}\left(r_{0}+\frac{d}{q-1}\right)-\frac{d}{q-1} .
$$

In our case

$$
\frac{d}{q-1}=\frac{(1-n) / n}{(n-1) / n-1}=n-1
$$

and

$$
r_{k}=\frac{(n-1)^{k}\left(r_{0}+n-1\right)}{n^{k}}-n+1 \quad(k=0,1,2 \ldots, n) .
$$

Since the numbers $(n-1)^{k}$ and $n^{k}$ are relatively prime, the values $r_{k}$ are integer if and only if the number $r_{0}+n-1$ is divisible by $n^{k}$, for all $k=0,1,2, \ldots, n$, that is by $n^{n}$. Hence there exists an integer $j$ such that $r_{0}+n-1=j \cdot n^{n}$, which is $r_{0}=j \cdot n^{n}-n+1$, and we can express $r_{k}$ as

$$
r_{k}=j \cdot(n-1)^{k} \cdot n^{n-k}-n+1 \quad(k=0,1,2 \ldots, n)
$$

Now we are searching for the least integer $j \geqslant 1$ such that all $r_{k}$ are positive. Since these numbers form a decreasing sequence, the smallest one is $r_{n}=j \cdot(n-1)^{n}-n+1$, which is for $n \geqslant 3$ positive already for $j=1\left(r_{0}=n^{n}-n+1\right)$, while for $n=2$ the least $j$ is equal to $2\left(r_{0}=2 \cdot 2^{2}-1=7\right)$.

Conclusion: The least possible $r_{0}$ is 7 for $n=2$ and $r_{0}=n^{n}-n+1$ for $n \geqslant 3$.
