game theory, parity, understanding invariant
Two players play a game on n piles. Let us characterize the player into two categories
even player and
odd player. The
even player selects a pile and remove some even number of coins from it. Similarly,
odd player can only remove odd number of coins. The player who is not able to make a move loses. You have to tell who will win the game depending on who takes the first turn?
Understand the simplest example
Let us check the smallest example n = 1.
If the pile contains odd number of coins
oddplayer plays first, he will win.
evenplayer plays first, he will lose. It is due to the fact that he can’t take all the coins of the pile as the total number of coins in the pile are odd. So, the number of coins left after his move will always be odd. In the next turn, the
oddplayer will remove the entire pile left and win the game.
odd player will win the game regardless of whether he plays first or second.
If the pile contains even number of coins
evenplayer plays first, he will win in the very first move.
oddplayer plays first, he will win. He will remove all but one coins from the pile. As the pile contains even number of coins, he can do so. Now, the pile will contain only 1 coin, on which the
evenplayer won’t be able to make any move.
Let us make more observations
From the previous example, we have realized that if a pile contains odd number of coins, then the
even player can’t make the number of coins in the pile to be even. In general, you can realize that for a
even player it is impossible to change the parity of the number of coins of the pile. But, for an
odd player, it is quite easy to change the parity.
This makes us to make the following important claim.
Claim : If there is a pile containing odd number of coins, then the
odd player will always win regardless of whether he takes first turn or not.
Proof : It is impossible for even player to make last move on it, because he can’t change the parity of pile from odd to even in his move. Also, the odd player will also not make any move in this pile until the last. The odd player can make moves in the other remaining piles (whether they be even or odd), he can always make moves in those. Finally, if it is
odd player’s turn, he will remove this entire pile. If, it is
even player’s turn, he has no option other than to remove some even number of coins, after that pile will contain odd number of coins and in the next turn
odd player will win by removing the entire pile.
Towards the full solution
Previous observation suggest that it is very important for the
odd player to have some odd pile. If he has one such odd pile, he will win.
odd player moves first, then he can always make a pile odd. He will choose some even pile and remove 1 coin from it.
even player moves first, then if he can’t win in the first move, then he can never win, because now the turn of
odd player comes and he will win the game. The
even player can win in the first move, if and only if there is only one pile containing even number of coins.
if n == 1 and pile is even and starting player is even): print `even player won` else print `odd player won`