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 4 of 5: Handle the zero-prefix case

Previous step Next step

d_j\ge0,\qquad d_1+\cdots+d_{j-1}<0

Detailed analysis

In the zero-prefix case, choose the first $j>i+1$ with $d_j\ge0$ . Such a $j$ exists because the total deviation is zero. Transfer one coin from $j$ to $j-1$ ; the negative prefix through $j-1$ moves one unit toward zero, so $X$ decreases by one. The chosen move keeps $d_1\ge0$ .