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αd coins where d is an odd number, and let us argue by induction on α. If α=0 the game ends after a single move, that is, the move that eliminates the single odd column of d coins. Suppose now that we have proved that for α=k the game ends in at most N moves. If α=k+1, with the first move this column will be split into two columns with 2kd coins each, and to eliminate the coins of each column at most N moves will be needed. In total, the game will end after at most M=2N+1 moves. Finally, if initially there are m columns of coins on the table C1,…,Cm and to eliminate the coins of each of them at most N1,…,Nm moves are needed, the game will end after at most N1+⋯+Nm 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 m columns of coins, containing respectively n1,…,nm coins. Let A be the number of the ni that are divisible by 4, B the number of the ni that are divisible by 2 but not by 4, and let δ=1 if there are columns with an odd number of coins, δ=0 otherwise. Define as the value of the configuration the number δ+A+δAB.
The value of the configuration before the last move is 1 (δ=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, then A is odd. The player splits a column with a number of coins 4k into two columns with 2k coins each. Then δ remains equal to zero, while the number A becomes even (if k is even B increases by 1, if k is odd it decreases by 1);
- if δ=1 and A is even, the player removes the columns with an odd number of coins (only the parity of δ changes);
- if δ=1 and A is odd, then necessarily B is odd. In this case the player splits a column with 2d coins (d odd) into two columns with d coins (only the parity of B changes).
Proof of (b):
- if δ=0, then A is even. Splitting into two a column with 4k coins changes only the parity of A, while splitting into two a column with 2d coins (d odd) changes only the parity of δ;
- if δ=1, then A is odd and B is even. If the player removes the columns with an odd number of coins, only the parity of δ changes; if she splits a column with 4k coins into two columns with 2k coins, only the parity of A changes; if she splits a column with 2d coins (d odd) into two columns with d coins, only the parity of B changes.
The case in which there is a single column with 20082008 coins produces an odd game value (δ=0,A=1,B=0), so the previous reasoning proves that Francesca has a winning strategy in this case.