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 3 of 5: Choose a move decreasing

X

Previous step Next step

d_{i+1}<0,\qquad d_1+\cdots+d_i>0

Detailed analysis

Take the first $i$ with $d_{i+1}<0$ . If the prefix $d_1+\cdots+d_i$ is positive, transfer one coin from person $i$ to person $i+1$ ; its absolute value drops by one and no other term changes. If that prefix is not positive, minimality forces $d_1=\cdots=d_i=0$ .