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 2 of 5: Define the prefix-sum potential

Previous step Next step

X=\sum_{i=1}^{n-1}\left|\sum_{j=1}^id_j\right|

Detailed analysis

Set $X=\sum_{i=1}^{n-1}|d_1+\cdots+d_i|$ . It is zero exactly when all $d_i$ are zero. A move across edge $i,i+1$ for $i<n$ changes only the $i$ th prefix sum, and hence changes $X$ by one.