APMO 97/5 solution

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?

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₁ ≥= 0. Now consider X = |d₁| + |d₁ + d₂| + |d₁ + d₂ + d₃| + ... + |d₁ + d₂ + ... + 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₁ + d₂ + ... + 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₁ ≥ 0. Take the first i for which d_i+1 < 0. There must be such an i, otherwise all d_i would be non-negative, but they sum to 0, so they would all have to be zero, contradicting X > 0. If d₁ + ... + d_i > 0, then we take the move to be a transfer from i to i+1. This will reduce |d₁ + ... + d_i| by 1 and leave the other terms in X unchanged, so it will reduce X by 1. If d₁ + ... + d_i is not strictly positive, then by the minimality of i we must have d₁ = d₂ = ... = d_i = 0. We know that d_i+1 < 0. Now find the first j > i+1 such that d_j ≥ 0. There must be such a j, otherwise we would have ∑ d_m < 0. We have d₁ + ... + d_j-1 < 0, so a transfer from j to j-1 will reduce |d₁ + ... + d_j-1| and hence reduce X. Finally note that the move we have chosen leaves d₁ ≥ 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