Problem 5

n

people are seated in a circle. A total of

nk

coins are distributed among them, not necessarily equally. A move transfers one coin between two adjacent people. Find an algorithm using the minimum number of moves that leaves everyone with the same number of coins.

Step 1 of 5: Encode the imbalance

Previous step Next step

d_i=c_i-k,\qquad\sum_{i=1}^nd_i=0

Detailed analysis

Label people cyclically, let $c_i$ be the initial coin count, and set $d_i=c_i-k$ . Since the total is $nk$ , $\sum_{i=1}^nd_i=0$ . Relabel so that $d_1\ge0$ .