PROBLEM LINK:
Author: Alei Reyes
Tester: Hasan Jaddouh
Editorialist: Praveen Dhinwa
DIFFICULTY:
cakewalk
PREREQUISITES:
game theory, parity, understanding invariant
PROBLEM:
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?
EXPLANATION:
Understand the simplest example
Let us check the smallest example n = 1.
If the pile contains odd number of coins
- If
odd
player plays first, he will win. - If
even
player 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, theodd
player will remove the entire pile left and win the game.
So, odd
player will win the game regardless of whether he plays first or second.
If the pile contains even number of coins
- If
even
player plays first, he will win in the very first move. - If
odd
player 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 theeven
player 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.
If the odd
player moves first, then he can always make a pile odd. He will choose some even pile and remove 1 coin from it.
If the 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.
Pseudo Code
if n == 1 and pile[1] is even and starting player is even):
print `even player won`
else
print `odd player won`