Browse · MathNet
PrintAustrian Mathematical Olympiad
Austria counting and probability
Problem
Initially, the numbers are written on a blackboard. Trixi and Nana play a game, taking alternate turns. Trixi plays first.
The player whose turn it is chooses two numbers and , erases both, and writes their (possibly negative) difference on the blackboard. This is repeated until only one number remains on the blackboard after moves. Trixi wins if this number is divisible by , otherwise Nana wins.
Which of the two has a winning strategy?
(Birgit Vera Schmidt)
The player whose turn it is chooses two numbers and , erases both, and writes their (possibly negative) difference on the blackboard. This is repeated until only one number remains on the blackboard after moves. Trixi wins if this number is divisible by , otherwise Nana wins.
Which of the two has a winning strategy?
(Birgit Vera Schmidt)
Solution
We will prove that Nana has a winning strategy.
The only relevant property of all numbers in the game is their residue modulo . Therefore, we will call all numbers , or according to their residue, and we will also call s and s non-zeros.
We observe that each move either does not change the number of non-zeros (if one or two zeros are involved in the move) or decreases the number of non-zeros by or (if no zero is involved in the move).
Nana can play arbitrarily for a long time while the number of non-zeros decreases, until that number reaches , , or at the start of her move. This has to happen because it is not possible to go from or more non-zeros to non-zeros in two moves, and Trixi certainly cannot win as long as there are non-zeros on the blackboard.
If the number of non-zeros is , then Nana will avoid decreasing the number of non-zeros by using one or two zeros to force Trixi to decrease the number to or . This has to happen because Trixi always starts a move with an even quantity of numbers, so she is the first one without zeros as long as there are non-zeros.
If the number of non-zeros is , then two of them have the same value. Nana chooses these two and replaces them with zero. This leaves one non-zero which can change between and , but never be removed until the end. So Nana wins.
If the number of non-zeros is , and they are distinct, then Nana replaces them with their difference which again can never become zero.
If the number of non-zeros is and they have the same value, then Nana will use one of them and a to convert them to . This is possible because Nana always starts her move with an odd quantity of numbers, so she certainly has an available . If Trixi uses , she will lose since the last non-zero cannot be converted to zero. She also cannot use two zeros, because then Nana is in the previous case and wins. So Trixi has to convert one of them with an additional to present Nana with two equal non-zeros. However, Nana can repeat her move until Trixi has not zeros left to do so. So Trixi will eventually be forced to use and loses.
If there is just one non-zero left, Nana can play arbitrarily because this single non-zero will remain until the end of the game.
(Theresia Eisenkölzl) □
The only relevant property of all numbers in the game is their residue modulo . Therefore, we will call all numbers , or according to their residue, and we will also call s and s non-zeros.
We observe that each move either does not change the number of non-zeros (if one or two zeros are involved in the move) or decreases the number of non-zeros by or (if no zero is involved in the move).
Nana can play arbitrarily for a long time while the number of non-zeros decreases, until that number reaches , , or at the start of her move. This has to happen because it is not possible to go from or more non-zeros to non-zeros in two moves, and Trixi certainly cannot win as long as there are non-zeros on the blackboard.
If the number of non-zeros is , then Nana will avoid decreasing the number of non-zeros by using one or two zeros to force Trixi to decrease the number to or . This has to happen because Trixi always starts a move with an even quantity of numbers, so she is the first one without zeros as long as there are non-zeros.
If the number of non-zeros is , then two of them have the same value. Nana chooses these two and replaces them with zero. This leaves one non-zero which can change between and , but never be removed until the end. So Nana wins.
If the number of non-zeros is , and they are distinct, then Nana replaces them with their difference which again can never become zero.
If the number of non-zeros is and they have the same value, then Nana will use one of them and a to convert them to . This is possible because Nana always starts her move with an odd quantity of numbers, so she certainly has an available . If Trixi uses , she will lose since the last non-zero cannot be converted to zero. She also cannot use two zeros, because then Nana is in the previous case and wins. So Trixi has to convert one of them with an additional to present Nana with two equal non-zeros. However, Nana can repeat her move until Trixi has not zeros left to do so. So Trixi will eventually be forced to use and loses.
If there is just one non-zero left, Nana can play arbitrarily because this single non-zero will remain until the end of the game.
(Theresia Eisenkölzl) □
Final answer
Nana
Techniques
Invariants / monovariantsGames / greedy algorithms