Maths Olympiad Prep

Library / /29 of 31

Combinatorics Difficulty 7.4 National Olympiad, round 2 Prove it Italy

Problem:

Francesca and Giorgia play the following game. On a table there are initially some columns of coins. Each column contains a certain number of coins, which may possibly vary from column to column. In turn, each player makes one and only one of the following possible moves:
- she chooses a column containing an even nonzero number 2k2k of coins and replaces it with two columns containing kk coins each;
- she removes from the table all the columns containing an odd number of coins.
In case it is not possible to make a move of the first type, the player will necessarily make one of the second type, and vice versa.
Francesca starts. Whoever takes the last coin from the table wins.

a. If initially there is a single column on the table, which contains 200820082008^{2008} coins, which player has a winning strategy?

b. For which initial configurations does Francesca have a winning strategy?

Solution

Solution:

Let us first verify that the game ends after a finite number of moves. Suppose first that initially there is a single column of coins, with 2αd2^{\alpha} d coins where dd is an odd number, and let us argue by induction on α\alpha. If α=0\alpha=0 the game ends after a single move, that is, the move that eliminates the single odd column of dd coins. Suppose now that we have proved that for α=k\alpha=k the game ends in at most NN moves. If α=k+1\alpha=k+1, with the first move this column will be split into two columns with 2kd2^{k} d coins each, and to eliminate the coins of each column at most NN moves will be needed. In total, the game will end after at most M=2N+1M=2N+1 moves. Finally, if initially there are mm columns of coins on the table C1,,CmC_{1}, \ldots, C_{m} and to eliminate the coins of each of them at most N1,,NmN_{1}, \ldots, N_{m} moves are needed, the game will end after at most N1++NmN_{1}+\cdots+N_{m} moves.

Observe then that the last move of the game must eliminate all the remaining coins; therefore before the last move there will be on the table only columns with an odd number of coins, and the player who happens to move when this occurs will win.

Suppose now that on the table there are mm columns of coins, containing respectively n1,,nmn_{1}, \ldots, n_{m} coins. Let AA be the number of the nin_{i} that are divisible by 44, BB the number of the nin_{i} that are divisible by 22 but not by 44, and let δ=1\delta=1 if there are columns with an odd number of coins, δ=0\delta=0 otherwise. Define as the value of the configuration the number δ+A+δAB\delta + A + \delta AB.

The value of the configuration before the last move is 11 (δ=1,A=0,B=0\delta=1, A=0, B=0) and we want to prove that Francesca has a winning strategy if and only if the value of the initial configuration is an odd number.

We will indeed prove that:

a. if before moving a player finds herself facing a configuration of odd value, then she will always be able to leave her opponent facing a configuration of even value;

b. if before moving a player finds herself facing a configuration of even value, then she will necessarily leave her opponent a configuration of odd value.

Assuming (a) and (b) have been proved, it is clear that, if the initial configuration has an odd value, Francesca's winning strategy will be to always leave her opponent a configuration of even value, while if the initial configuration has even value, then Francesca will leave Giorgia, after the first move, a configuration with odd value, and it will be Giorgia who has the winning strategy.

Proof of (a):
- if δ=0\delta=0, then AA is odd. The player splits a column with a number of coins 4k4k into two columns with 2k2k coins each. Then δ\delta remains equal to zero, while the number AA becomes even (if kk is even BB increases by 11, if kk is odd it decreases by 11);
- if δ=1\delta=1 and AA is even, the player removes the columns with an odd number of coins (only the parity of δ\delta changes);
- if δ=1\delta=1 and AA is odd, then necessarily BB is odd. In this case the player splits a column with 2d2d coins (dd odd) into two columns with dd coins (only the parity of BB changes).

Proof of (b):
- if δ=0\delta=0, then AA is even. Splitting into two a column with 4k4k coins changes only the parity of AA, while splitting into two a column with 2d2d coins (dd odd) changes only the parity of δ\delta;
- if δ=1\delta=1, then AA is odd and BB is even. If the player removes the columns with an odd number of coins, only the parity of δ\delta changes; if she splits a column with 4k4k coins into two columns with 2k2k coins, only the parity of AA changes; if she splits a column with 2d2d coins (dd odd) into two columns with dd coins, only the parity of BB changes.

The case in which there is a single column with 200820082008^{2008} coins produces an odd game value (δ=0,A=1,B=0\delta=0, A=1, B=0), so the previous reasoning proves that Francesca has a winning strategy in this case.

Want a route through all this instead of 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 translated into English from it; metadata (topic, difficulty) added by this project.