Olympiad Maths Prep

Library / /5 of 5

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
SnewSinitial=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=1009201913(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=3Sinitial33(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.

Looking for a route rather than 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.