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 5 of 5: Compare the wraparound move and iterate

Previous step Next step

X\to0

Detailed analysis

Repeat the decreasing move until $X=0$ if no wraparound move is better. Also compute the change in $X$ for transfers across edge $n,1$ in both directions; if either decreases $X$ by more than one, use the direction with the larger decrease. Every move is legal and $X$ strictly decreases, so the process terminates at equal holdings and is minimal by the potential argument.