Saudi Arabian IMO Booklet

Question

2000 consecutive integers (not necessarily positive) are written on the board. A student takes several turns. On each turn, he partitions the 2000 integers into 1000 pairs, and substitutes each pair by the difference and the sum of that pair (note that the difference does not need to be positive as the student may choose to subtract the greater number from the smaller one; in addition, all the operations are carried simultaneously). Prove that the student will never again write 2000 consecutive integers on the board.

Accepted Answer

Note that (a-b)^2 + (a+b)^2 = 2(a^2 + b^2), so the sum of the squares of the numbers written on the board doubles on each turn. Note that n^2 + (n+1)^2 + + (n+1999)^2 = 2000n^2 + 1999 2000n + 1999 2000 39996, which is congruent to 8 modulo 16. Obviously, when we multiply this sum by 2, we will obtain a number divisible by 16, thus, we will never have consecutive numbers again, which is what we need to show.