Maths Olympiad Prep

Library / /38 of 136

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it Hong Kong

Five numbers 11, 22, 33, 44, 55 are written on a blackboard. A student may erase any two of the numbers aa and bb on the board and write the numbers a+ba+b and abab replacing them. If this operation is repeatedly performed, can the numbers 2121, 2727, 6464, 180180, 540540 ever appear on the board at the same time?

Solution

No. We consider the numbers modulo 33.
* If 3a,b3 \mid a, b, then 3a+b3 \mid a + b and 3ab3 \mid ab. The number of multiples of 33 remains unchanged.
* If 3a3 \mid a and 3b3 \nmid b, then 3a+b3 \nmid a + b and 3ab3 \mid ab. The number of multiples of 33 remains unchanged.
* If ab±1(mod3)a \equiv b \equiv \pm 1 \pmod{3}, then 3a+b3 \nmid a + b and 3ab3 \nmid ab. The number of multiples of 33 remains unchanged.
* If a1(mod3)a \equiv 1 \pmod{3} and b2(mod3)b \equiv 2 \pmod{3}, then 3a+b3 \mid a + b and ab2(mod3)ab \equiv 2 \pmod{3}. The number of multiples of 33 is increased by 11, and there is a number which is congruent to 22 modulo 33.
Now, note that 321,27,180,5403 \mid 21, 27, 180, 540 and 641(mod3)64 \equiv 1 \pmod{3}. If the 55 numbers can appear on the board at the same time, there must be an instant when the number of multiples of 33 changes from 33 to 44. This must be the last case in the above list, hence the 55 numbers are now congruent to 0,0,0,0,20, 0, 0, 0, 2 modulo 33 respectively. Afterwards, no matter which 22 numbers we choose, the new numbers are still congruent to 0,0,0,0,20, 0, 0, 0, 2 modulo 33 respectively. Therefore, it is impossible to generate 2121, 2727, 6464, 180180, 540540. This is a contradiction.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.