Maths Olympiad Prep

Library / Hellenic Mathematical Olympiad /54 of 57

Hellenic Mathematical Olympiad

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Greece

In the table are written the positive integers 1,2,3,…,20181, 2, 3, \ldots, 2018. John and Mary have the possibility to make the following move:
They select two of the written numbers in the table, let α,β\alpha, \beta and they replay them with the numbers 5α−2β5\alpha - 2\beta and 3α−4β3\alpha - 4\beta.

John asserts that after a finite number of such moves is possible to have in the table the numbers: 3,6,9,…,60543, 6, 9, \ldots, 6054. Mary answer that this is not possible. Who is right?

Solution

We observe that after a move the sum of the numbers in the table have a change equal to the difference:
(5α−2β)+(3α−4β)−(α+β)=7(α−β) (5\alpha - 2\beta) + (3\alpha - 4\beta) - (\alpha + \beta) = 7(\alpha - \beta)
Therefore we conclude that after every application of a move the difference of the sum SnewS_{\text{new}} minus the sum SinitialS_{\text{initial}} is a multiple of 77, that is
Snew−Sinitial=mult. 7. S_{\text{new}} - S_{\text{initial}} = \text{mult. }7.
So, the sums SnewS_{\text{new}} and SinitialS_{\text{initial}} when divided by 77 give the same remainder. Since
Sinitial=1+2+⋯+2018=1009⋅2019≡1⋅3(mod7)≡3(mod7). S_{\text{initial}} = 1 + 2 + \dots + 2018 = 1009 \cdot 2019 \equiv 1 \cdot 3 \pmod{7} \equiv 3 \pmod{7}.
In case we find the numbers 3,6,9,…,60543,6,9,\ldots,6054, then their sum will be
Snew=3+6+⋯+6054=3⋅Sinitial≡3⋅3(mod7)≡2(mod7). S_{\text{new}} = 3 + 6 + \dots + 6054 = 3 \cdot S_{\text{initial}} \equiv 3 \cdot 3 \pmod{7} \equiv 2 \pmod{7}.
Therefore is not possible to find the numbers 3,6,9,…,60543, 6, 9, \ldots, 6054 in the table, and so Mary is right.

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.