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
mszew
13.11.2009 19:14
Notice that the sum of the two elements of an operation is invariant just because $ a+b=(a-1)+(b+1)$
If there is no possible step then $ a-b=0$ or $ a-b=1$ for all pairs of $ a,b$
but the sum of all elements keeps the same after each step and equal to $ 210$
then the last integers are $ (10,\cdots,10,11,\cdots,11)$ with ten $ 10$ and ten $ 11$.
kevinatcausa
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$).
samath
15.11.2009 05:36
It's easy to find an upper bound for the number of steps.
Let the numbers on the blackboard be $ a_1,a_2,\cdots a_{20}.$
Let $ S=\sum_{i=1}^{20} a_i^2.$ At the beginning, $ S_0=\sum_{i=1}^{20} i^2=2870$.
As we showed above, the final setup must be 10,10,...,11,11,..., giving $ S_{final}=10(10^2+11^2)=2210$.
After performing the operation, $ S_n=S_{n-1}-a^2-b^2+(a-1)^2+(b+1)^2=S_{n-1}-2(a-b)+2\le S_{n-1}-2$.
Therefore since the invariant decreases by 4 each time, we can perform the operation at most $ \frac{S_{final}-S_0}{2}=330$ times.
Seems like a lot of trouble to find a construction though.
Raja Oktovin
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.
gwy
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.