The integers $ 1,2,\dots,20$ are written on the blackboard. Consider the following operation as one step: choose two integers $ a$ and $ b$ such that $ a-b \ge 2$ and replace them with $ a-1$ and $ b+1$. Please, determine the maximum number of steps that can be done. Yudi Satria, Jakarta
Problem
Source: Indonesia IMO 2010 TST, Stage 1, Test 4, Problem 1
Tags: invariant, combinatorics proposed, combinatorics
13.11.2009 19:14
13.11.2009 23:45
Is this really enough to answer the question as written? Not all paths leading to the same configuration have the same length (for example, if we replace $ 20$ by $ 6$ we can get to the final configuration by $ 123456 \rightarrow 223455 \rightarrow 233445 \rightarrow 333444$ ($ 3$ steps) or $ 123456 \rightarrow 124455 \rightarrow 224445 \rightarrow 233445 \rightarrow 333345 \rightarrow 333444$ ($ 5$ steps) or possibly longer paths. It's not clear from the final configuration what the longest possible path is, though you can get an upper bound by looking at the sums of the squares of the elements (replacing $ (a,b)$ by $ (a - 1, b + 1)$ reduces the sum of the squares by $ a^2 + b^2 - (a - 1)^2 - (b + 1)^2 = 2(a - b) - 2 \geq 2$).
15.11.2009 05:36
It's easy to find an upper bound for the number of steps.
Seems like a lot of trouble to find a construction though.
15.11.2009 05:58
Yes, the answer is $ 330$. Some contestants got $ 7$ by just showing the construction, with some explanation, which is actually not complete.
17.11.2009 08:18
The construction is as follows: (1) We start with the sequence 1-20. Operate on these pairs in order: (1,3) (2,4) (3,5) ... (18, 20). This transforms the sequence into 2-19+2,19 (that is the sequence from 2 to 19, and an extra 2 and 19). Essentially, what it does is to pull a "1" from the "20" and add it to the "1", leaving everything else intact. (2) Now since we have 2-19+2,19, the sequence 2-19 is just similar to 1-20, and if we apply the same operations, we get 3-18+2,3,18,19. Do this iteratively and finally we get 10-11+2,3,...19, i.e. 10,11+2-19. Thus, starting from 1-20, we get 10,11+2-19 with all the above operations. (3) Since 2-19 is similar to 1-20, if we apply all the above operations on it, we should get 10,10,11,11+3-18. Do this iteratively we will eventually get 10,10...11,11,...11. Since each of the above operations involve x and x+2 for some x, it must be maximum in terms of the number of operations to get the last configuration.