Browse · MathNet
Print36th 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?
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