
NT2 A group of $n>1$ pirates of different age owned total of 2009 coins. Initially each pirate (except for the youngest one) had one coin more than the next younger.

a) Find all possible values of $n$.

b) Every day a pirate was chosen. The chosen pirate gave a coin to each of the other pirates. If $n=7$, find the largest possible number of coins a pirate can have after several days.


## Solution:

a) If $n$ is odd, then it is a divisor of $2009=7 \times 7 \times 41$. If $n>49$, then $n$ is at least $7 \times 41$, while the average pirate has 7 coins, so the initial division is impossible. So, we can have $n=7, n=41$ or $n=49$. Each of these cases is possible (e.g. if $n=49$, the average pirate has 41 coins, so the initial amounts are from $41-24=17$ to $41+24=65$ ).

If $n$ is even, then 2009 is multiple of the sum $S$ of the oldest and the youngest pirate. If $S<7 \times 41$, then $S$ is at most 39 and the pairs of pirates of sum $S$ is at least 41 , so we must have at least 82 pirates, a contradiction. So we can have just $S=7 \times 41=287$ and $S=49 \times 41=2009$; respectively, $n=2 \times 7=14$ or $n=2 \times 1=2$. Each of these cases is possible (e.g. if $n=14$, the initial amounts are from $144-7=137$ to $143+7=150$ ). In total, $n$ is one of the numbers $2,7,13,41$ and 49 .

b) If $n=7$, the average pirate has $7 \times 41=287$ coins, so the initial amounts are from 284 to 290; they have different residues modulo 7. The operation decreases one of the amounts by 6 and increases the other ones by 1 , so the residues will be different at all times. The largest possible amount in one pirate's possession will be achieved if all the others have as little as possible, namely $0,1,2,3,4$ and 5 coins (the residues modulo 7 have to be different). If this happens, the wealthiest pirate will have $2009-14=1994$ coins. Indeed, this can be achieved e.g. if every day (until that moment) the coins are given by the second wealthiest: while he has more than 5 coins, he can provide the 6 coins needed, and when he has no more than five, the coins at the poorest six pirates have to be $0,1,2,3,4,5$. Thus, $n=1994$ can be achieved.
