Maths Olympiad Prep

Library / /17 of 27

Combinatorics Difficulty 8.3 Shortlist Prove it Saudi Arabia

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.

Solution

Note that (a−b)2+(a+b)2=2(a2+b2)(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
n2+(n+1)2+⋯+(n+1999)2=2000n2+1999⋅2000n+1999⋅2000⋅39996, n^2 + (n+1)^2 + \dots + (n+1999)^2 = 2000n^2 + 1999 \cdot 2000n + \frac{1999 \cdot 2000 \cdot 3999}{6},
which is congruent to 88 modulo 1616. Obviously, when we multiply this sum by 22, we will obtain a number divisible by 1616, thus, we will never have consecutive numbers again, which is what we need to show. □\square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.