Skip to main content
OlympiadHQ

Browse · MathNet

Print

36th Hellenic Mathematical Olympiad

Greece counting and probability

Problem

In the table are written the positive integers . John and Mary have the possibility to make the following move: They select two of the written numbers in the table, let and they replay them with the numbers and .

John asserts that after a finite number of such moves is possible to have in the table the numbers: . 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: Therefore we conclude that after every application of a move the difference of the sum minus the sum is a multiple of , that is So, the sums and when divided by give the same remainder. Since In case we find the numbers , then their sum will be Therefore is not possible to find the numbers in the table, and so Mary is right.
Final answer
Mary is right.

Techniques

Invariants / monovariantsModular Arithmetic