### 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, the`odd`

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 the`even`

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`
```