Maths Olympiad Prep

Library / IMO Hk TST /33 of 119

IMO Hk TST

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 3∣a,b3 \mid a, b, then 3∣a+b3 \mid a + b and 3∣ab3 \mid ab. The number of multiples of 33 remains unchanged.
* If 3∣a3 \mid a and 3∤b3 \nmid b, then 3∤a+b3 \nmid a + b and 3∣ab3 \mid ab. The number of multiples of 33 remains unchanged.
* If a≡b≡±1(mod3)a \equiv b \equiv \pm 1 \pmod{3}, then 3∤a+b3 \nmid a + b and 3∤ab3 \nmid ab. The number of multiples of 33 remains unchanged.
* If a≡1(mod3)a \equiv 1 \pmod{3} and b≡2(mod3)b \equiv 2 \pmod{3}, then 3∣a+b3 \mid a + b and ab≡2(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 3∣21,27,180,5403 \mid 21, 27, 180, 540 and 64≡1(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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.