it's the hardest problem in APMO 1997;most of our team's member get 0 the offical solution(the only solution i know too): http://www.kalva.demon.co.uk/apmo/asoln/asol975.html

I'm sorry but I can't open the link.Can you post the solution here please? Thanks.

Yes, sure : Kalva wrote: Label the people from 1 to n, with person i next to person i+1, and person n next to person 1. Let person i initially hold ci coins. Let di = ci - k. It is not obvious how many moves are needed. Clearly at least 1/2 ∑ |di| are needed. But one may need more. For example, suppose the starting values of di are 0, 1, 0, -1, 0. Then one needs at least 2 moves, not 1. Obviously ∑ di = 0, so not all di can be negative. Relabel if necessary so that d1 ≥= 0. Now consider X = |d1| + |d1 + d2| + |d1 + d2 + d3| + ... + |d1 + d2 + ... + dn-1|. Note first that X is zero iff all di are zero. Any move between i and i+1, except one between n and 1, changes X by 1, because only the term |d1 + d2 + ... + di| is affected. Thus if we do not make any moves between n and 1, then we need at least X moves to reach the desired final position (with all di zero). Assume X > 1. We show how to find a move which reduces X by 1. This requires a little care to avoid specifying a move which might require a person with no coins to transfer one. We are assuming that d1 ≥ 0. Take the first i for which di+1 < 0. There must be such an i, otherwise all di would be non-negative, but they sum to 0, so they would all have to be zero, contradicting X > 0. If d1 + ... + di > 0, then we take the move to be a transfer from i to i+1. This will reduce |d1 + ... + di| by 1 and leave the other terms in X unchanged, so it will reduce X by 1. If d1 + ... + di is not strictly positive, then by the minimality of i we must have d1 = d2 = ... = di = 0. We know that di+1 < 0. Now find the first j > i+1 such that dj ≥ 0. There must be such a j, otherwise we would have ∑ dm < 0. We have d1 + ... + dj-1 < 0, so a transfer from j to j-1 will reduce |d1 + ... + dj-1| and hence reduce X. Finally note that the move we have chosen leaves d1 ≥ 0. Thus we can repeat the process and reduce X to zero in X moves. We have proved that this procedure minimises the number of moves if we accept the restriction that we do not make any transfers between 1 and n. Thus the full algorithm is: calculate the effect of the transfers from 1 to n and from n to 1 on X. If either of these transfers reduces X by more than 1, then take the move with the larger reduction; otherwise, find a move as above which reduces X by 1; repeat.

That means the answer is X.Right?

The solution appears to be wrong. Here's a counterexample: Suppose $n = 9, N = 1$ and after relabeling that the people have, in order, 2, 0, 0, 1, 1, 1, 1, 3, 0 objects. The given algorithm will first make person 1 pass an object to person 2, and then have the people numbered 4 and above each pass an object to the previous person. (0) 2, 0, 0, 1, 1, 1, 1, 3, 0 (1) 1, 1, 0, 1, 1, 1, 1, 3, 0 (2) 1, 1, 1, 0, 1, 1, 1, 3, 0 (3) 1, 1, 1, 1, 0, 1, 1, 3, 0 (4) 1, 1, 1, 1, 1, 0, 1, 3, 0 (5) 1, 1, 1, 1, 1, 1, 0, 3, 0 (6) 1, 1, 1, 1, 1, 1, 1, 2, 0 (7) 1, 1, 1, 1, 1, 1, 1, 1, 1 But the optimal solution, which is not discovered because it involves passing objects to the border between person 1 and person $n$ from more than one person away, only requires 6 moves: (0) 2, 0, 0, 1, 1, 1, 1, 3, 0 (1) 1, 1, 0, 1, 1, 1, 1, 3, 0 (2) 1, 0, 1, 1, 1, 1, 1, 3, 0 (3) 0, 1, 1, 1, 1, 1, 1, 3, 0 (4) 0, 1, 1, 1, 1, 1, 1, 2, 1 (5) 1, 1, 1, 1, 1, 1, 1, 2, 0 (6) 1, 1, 1, 1, 1, 1, 1, 1, 1 The string of 1s can be extended arbitrarily in this counterexample; the optimal solution remains at 6 moves while the algorithm's solution becomes $n - 2$, which can obviously be arbitrarily big. The key failure in the solution is a bit vaguely phrased: if we "calculate the effect of the transfers from 1 to n and from n to 1 on X" and find one move that does decrease X by more than 1, there's no guarantee that there are any objects present that enable us to make that move. I'm assuming the algorithm simply gives up and goes to the next step to find a normal reduce-X-by-1 move. The algorithm might actually be correct if it moves an object across several people to make that decrease-X-by-more-than-1 move, partially because if there are so many people near the border between person 1 and person $n$ with 0 objects, then passing an object across them would also be standard reduce-X-by-1 moves. However, I don't know how to prove this. It's far from obvious that the reduction of X by more than 1 is used to its fullest potential and won't be affected by the intermediate moves. I think this question is very oddly phrased for a math olympiad problem, and it's hard to specify what a solution has to do to count as having solved it. For what it's worth, if this had been given as a programming problem, my algorithm would be as follows: Transform the problem into this isomorphic representation to make things easier: arrange the $nN$ objects in a circle and place labeled dividers between adjacent objects to represent the initial distribution of objects to people. Each person's share of objects is represented by the number of objects between two particular adjacent dividers. Then each transfer of objects is equivalent to moving one divider forward or backward one step in the circle, with the restriction that dividers cannot overtake one another (they can be in the same space between two objects, but their relative positions inside the space must still be preserved). Now the goal is to arrange the dividers so that they are equally spaced $N$ objects apart around the circle with the least number of moves. Positioning any one divider locks down the target positions of the others, so since there are $nN$ positions between objects, there are only $nN$ possible ending configurations. But in fact, we only need to consider at most $n$ of them, namely those ending configurations where at least one divider is not moved from its initial position. This is because if no dividers are correct in an ending configuration, the number of moves required to obtain it changes linearly if the ending configuration is rotated to the left or right. So we can rotate the ending configuration in one direction until one divider is in the correct position without increasing the number of moves required to obtain it. There is now a $O(n^2)$ solution: brute-force all possible ending configurations, determine the number of moves required to reach it by checking every divider, and take the minimum. But the calculation step can be optimized by noting that the number of moves required for any one divider changes linearly most of the time as the ending configuration is rotated, with only one "inversion" when its initial position crosses over its ending position. So we can record when the inversion occurs for each divider, presort this list of inversions, keep track of a delta during the rotation step that tells us how much to update the "total moves required" in $O(1)$, and only update the delta when we meet an inversion. Then we can check all possible ending configurations in an $O(n)$ sweep. This algorithm takes only $O(n \log n)$ time and is dominated by the cost of presorting the list of inversions.

I think changing the algorithm from finding the smallest $j$ such that $d_j \geq 0$ to smallest j such that $d_1+...+d_j \geq 0$ when $d_1 = .... = d_i$ fixes it.

We can view this problem as person $i$ giving $x_i$ objects to person $i+1$ ($x_i$ can be negative), where we want to minimize the cost $\sum_{i=1}^n |x_i|$. Since $a_i + x_{i - 1} - x_i = N$, we have $x_i = x_{i - 1} + a_i - N$. Thus if we fix $x_1$, the rest of $x_i$ are fixed as well. This allows us to rewrite the cost as $\sum_{i=1}^n |x_1 - b_i|$ for $b_i$ such that $|x_1 - b_i|=|x_i|$, which is minimized when $x_1$ is the median of all $b_i$. This algorithm also takes $O(n\log n)$ with the bottleneck being sorting the list of $b_i$ to find the median. By the way, this problem was given on a programming contest a couple years ago: http://usaco.org/index.php?page=viewproblem2&cpid=128

The solution is in the Example 8 of the 1st chapter of this book

solution from book Mathematical Olympiads 1997-1998: Problems and Solutions

Attachments:

I think my solution is wrong Label the people inthe circle clockwise by $i = 1, 2 , …,n$. Define $L_j = \sum |a_i - a_{i-1}|$ over all $i$ in the j-th step. We also define $a_i$ as the amount of objects the person $i$ has. It is almost trivial that $L$ can change only by $4$ and that $L$ is always divisble by 4. Now we can formulate the algorithm as follows: Make a transfer each step such that $L_j - L_{j+1} = 4$. If $L_j = 0$ for some natural number $j$, then stop. EDIT: Could someone give me a correction?

I have a bit different solution, thanks to the help of CANBANKAN Solution wrote: Consider the maximal $a_{j}$, note that either $a_{1}+a_{2}.....a_{j-1} < (j-1)k$ or $a_{j+1}+....a_{n} < (n-j)k$ or both, so if the side 2 is lesser or the side 1, keep giving coins from $a_{j}$ unless $a_{j} = k$, similarly keep repeating this process unless all of them become equal to $k$, this is minimal since the difference of the indices bigger than k, need to be distributed, no matter how we distribute it, the number of move remains the same.

official solutions

This discussion is kind of making my head spin, and I gave up on reading after a bit. Are any of these solutions even correct? I honestly can't understand why the algorithms in #4 and #10 are supposed to be optimal. I think one way to resolve my queries is by considering $t$ to be the median of $0, -d_1, -d_1 - d_2, \ldots, -d_1 - \ldots - d_n$; $r$ to be the number of passes completed from $A_n$ to $A_1$ (if $t$ is positive), signed by direction; and $s:=t - r$. Then, taking $$|s| + |s + d_1| + |s + d_1 + d_2| + \ldots + |s + d_1 + \ldots + d_n|$$to be our monovariant gives a direct measure of distance from desired state. Is this somehow equivalent to the above solutions? Am I just rambling incomprehensibly? I can't tell if I'm tired and confused, old and confused, or justifiably confused right now. Can somebody help me?