The persons $P_1, P_2, . . . , P_{n-1}, P_n$ sit around a table, in this order, and each one of them has a number of coins. In the start, $P_1$ has one coin more than $P_2, P_2$ has one coin more than $P_3$, etc., up to $P_{n-1}$ who has one coin more than $P_n$. Now $P_1$ gives one coin to $P_2$, who in turn gives two coins to $P_3 $ etc., up to $ Pn$ who gives n coins to $ P_1$. Now the process continues in the same way: $P_1$ gives $n+ 1$ coins to $P_2$, $P_2$ gives $n+2$ coins to $P_3$; in this way the transactions go on until someone has not enough coins, i.e. a person no more can give away one coin more than he just received. At the moment when the process comes to an end in this manner, it turns out that there are two neighbours at the table such that one of them has exactly five times as many coins as the other. Determine the number of persons and the number of coins circulating around the table.
Problem
Source: Nordic Mathematical Contest 2000 #2
Tags: combinatorics, Integer sequence
04.10.2017 15:04
Note that since whenever a person receives coins, they immediately pass all of them plus one coin on, we'll instead simplify the problem. Each person pools one coin to the middle of the table, starting from $P_1, P_2, P_3, \ldots$. At the moment someone cannot pool a coin, they take all the pooled coins and the process ends. It's easy to see that this is equivalent to the problem; at any time, the pool is exactly the amount of coins passed to the next person. Suppose at the beginning $P_n$ has $a$ coins. At the end, clearly $P_n$ will be the first person to run out of coins (since everyone else has more than them, and each person gives one coin every round). When $P_n$ needs to give one more coin, we have finished $a$ complete rounds of all $n$ people contributing, plus one incomplete round of all but $P_n$ contributing. Thus the pool has $(a+1)n - 1$ coins. $P_n$ takes them all; every other person $P_k$ has $n-1-k$ coins. Now, any two neighbors not involving $P_n$ have exactly one coin difference, and so they cannot be the two people referred in the problem. Then, $P_{n-1}$ has zero coins, so cannot be involved either. This leaves $P_n$ and $P_1$; $P_n$ has $(a+1)n - 1$ coins, and $P_1$ has $n-2$ coins. We will investigate the two cases: $(a+1)n - 1 = 5(n-2)$. Then simplifying, $(4-a)n = 9$. Since we know $a \ge 0$ (it's the number of coins $P_n$ had initially) and $n \ge 2$ (we assume there are at least two people in order for there being neighbors), the only solutions are $(a,n) = (1,3), (3,9)$. $5 \cdot ((a+1)n-1) = n-2$. Then simplifying, $(5a+4)n = 3$. Since $a \ge 0$, we have $5a+4 \ge 4$, but then $0 < n < 1$ so we don't have any solution. Thus the two solutions are $(a,n) = (1,3), (3,9)$. The number of coins is simply $an + \binom{n}{2}$, which is 6 in the first case and 63 in the second case. We have two solutions: either there are 3 people and 6 coins, or 9 people and 63 coins.