9th APMO 1997 Problem 5 n people are seated in a circle. A total of nk coins are distributed amongst the people, but not necessarily equally. A move is the transfer of a single coin between two adjacent people. Find an algorithm for making the minimum number of moves which result in everyone ending up with the same number of coins?
Problem 1180
Official solution
Label the people from 1 to n, with person i next to person i+1, and person n next to person 1. Let person i initially hold c i coins. Let d i = c i - k. It is not obvious how many moves are needed. Clearly at least 1/2 ∑ |d i | are needed. But one may need more. For example, suppose the starting values of d i are 0, 1, 0, -1, 0. Then one needs at least 2 moves, not 1. Obviously ∑ d i = 0, so not all d i can be negative. Relabel if necessary so that d 1 ≥= 0. Now consider X = |d 1 | + |d 1 + d 2 | + |d 1 + d 2 + d 3 | + ... + |d 1 + d 2 + ... + d n-1 |. Note first that X is zero iff all d i are zero. Any move between i and i+1, except one between n and 1, changes X by 1, because only the term |d 1 + d 2 + ... + d i | is affected. Thus if we do not make any moves between n and 1, then we need at least X moves to reach the desired final position (with all d i zero). Assume X > 1. We show how to find a move which reduces X by 1. This requires a little care to avoid specifying a move which might require a person with no coins to transfer one. We are assuming that d 1 ≥ 0. Take the first i for which d i+1 0. If d 1 + ... + d i > 0, then we take the move to be a transfer from i to i+1. This will reduce |d 1 + ... + d i | by 1 and leave the other terms in X unchanged, so it will reduce X by 1. If d 1 + ... + d i is not strictly positive, then by the minimality of i we must have d 1 = d 2 = ... = d i = 0. We know that d i+1 i+1 such that d j ≥ 0. There must be such a j, otherwise we would have ∑ d m < 0. We have d 1 + ... + d j-1 < 0, so a transfer from j to j-1 will reduce |d 1 + ... + d j-1 | and hence reduce X. Finally note that the move we have chosen leaves d 1 ≥ 0. Thus we can repeat the process and reduce X to zero in X moves. We have proved that this procedure minimises the number of moves if we accept the restriction that we do not make any transfers between 1 and n. Thus the full algorithm is: calculate the effect of the transfers from 1 to n and from n to 1 on X. If either of these transfers reduces X by more than 1, then take the move with the larger reduction; otherwise, find a move as above which reduces X by 1; repeat. 9th APMO 1997 © John Scholes [email protected] 11 Apr 2002