IMO 2012 Shortlist C1

Category: Combinatorics

Problem

Several positive integers are written in a row. Iteratively, Alice chooses two adjacent numbers x and y such that x > y and x is to the left of y, and replaces the pair (x,y) by either (y + 1,x) or (x − 1,x). Prove that she can perform only finitely many such iterations. Solution 1. Note first that the allowed operation does not change the maximum M of the initial sequence. Let a1,a2,...,an be the numbers obtained at some point of the process. Consider the sum S = a1 + 2a2 + ··· + nan. We claim that S increases by a positive integer amount with every operation. Let the operation replace the pair (ai,ai+1) by a pair (c,ai), where ai > ai+1 and c = ai+1+1 or c = ai−1. Then the new and the old value of S differ by d = (ic+(i+1)ai)−(iai+(i+1)ai+1) = ai−ai+1+i(c−ai+1). The integer d is positive since ai − ai+1 ≥ 1 and c − ai+1 ≥ 0. On the other hand S ≤ (1+2+···+n)M as ai ≤ M for all i = 1,...,n. Since S increases by at least 1 at each step and never exceeds the constant (1+2+···+n)M, the process stops after a finite number of iterations. Solution 2. Like in the first solution note that the operations do not change the maximum M of the initial sequence. Now consider the reverse lexicographical order for n-tuples of integers. We say that (x1,...,xn) < (y1,...,yn) if xn < yn, or if xn = yn and xn−1 < yn−1, or if xn = yn, xn−1 = yn−1 and xn−2 < yn−2, etc. Each iteration creates a sequence that is greater than the previous one with respect to this order, and no sequence occurs twice during the process. On the other hand there are finitely many possible sequences because their terms are always positive integers not exceeding M. Hence the process cannot continue forever. Solution 3. Let the current numbers be a1,a2,...,an. Define the score si of ai as the number of aj’s that are less than ai. Call the sequence s1,s2,...,sn the score sequence of a1,a2,...,an. Let us say that a sequence x1,...,xn dominates a sequence y1,...,yn if the first index i with xi 6= yi is such that xi < yi. We show that after each operation the new score sequence dominates the old one. Score sequences do not repeat, and there are finitely many possibilities for them, no more than (n − 1)n . Hence the process will terminate. Consider an operation that replaces (x,y) by (a,x), with a = y + 1 or a = x − 1. Suppose that x was originally at position i. For each j < i the score sj does not increase with the change because y ≤ a and x ≤ x. If sj decreases for some j < i then the new score sequence dominates the old one. Assume that sj stays the same for all j < i and consider si. Since x > y and y ≤ a ≤ x, we see that si decreases by at least 1. This concludes the proof. Comment. All three proofs work if x and y are not necessarily adjacent, and if the pair (x,y) is replaced by any pair (a,x), with a an integer satisfying y ≤ a ≤ x. There is nothing special about the “weights” 1,2,...,n in the definition of S = Pn i=1 iai from the first solution. For any sequence w1 < w2 < ··· < wn of positive integers, the sum Pn i=1 wiai increases by at least 1 with each operation. Consider the same problem, but letting Alice replace the pair (x,y) by (a,x), where a is any positive integer less than x. The same conclusion holds in this version, i. e. the process stops eventually. The solution using the reverse lexicographical order works without any change. The first solution would require a special set of weights like wi = Mi for i = 1,...,n. Comment. The first and the second solutions provide upper bounds for the number of possible operations, respectively of order Mn2 and Mn where M is the maximum of the original sequence. The upper bound (n − 1)n in the third solution does not depend on M.20