4. Two players, $A$ (first player) and $B$, take alternate turns in playing a game using 2016 chips as follows: the player whose turn it is, must remove $s$ chips from the remaining pile of chips, where $s \in\{2,4,5\}$. No one can skip a turn. The player who at some point is unable to make a move (cannot remove chips from the pile) loses the game. Who among the two players can force a win on this game?
Solution: We call the remaining number of chips a winning position if there exists at least one move such that the player (whose turn it is) can force a win. The remaining number of chips is a losing position if any move by the player will give the opponent a chance to force a win, or a winning position. Thus, the number of chips is a winning position if there is a move that will give the opponent a losing position.
- Clearly, 0 and 1 are losing positions: you cannot make any legal move here.
- However, 2, 4 and 5 are winning positions: take all the remaining chips and win.
- 3 is a winning position: the only move you can make is to remove 2 chips, leaving your opponent with 1 chip, so he loses.
- $6=5+1$ is also a winning position: take 5 chips, causing your opponent to lose.
- 7 and 8 are losing positions: any move will give the opponent a winning position: $7=2+5=4+3=5+2$ and $8=2+6=4+4=5+3$.
- Positions 9 to 13 are winning positions since you can bring the game to a losing position: $9=2+7,10=2+8,11=4+7,12=5+7,13=5+8$.

We conjecture that for nonnegative integers $k, 7 k$ and $7 k+1$ are losing positions and $7 k+2,7 k+3,7 k+4,7 k+5$ and $7 k+6$ are winning positions. We have shown this to be true when $k=0$ and when $k=1$. Now we proceed by mathematical induction. We assume that $7 k$ and $7 k+1$ are losing positions and $7 k+2,7 k+3,7 k+4,7 k+5$ and $7 k+6$ are winning positions, where $k \geq 0$. We want to show that $7 k+7$ and $7 k+8$ are losing positions while $7 k+9,7 k+10,7 k+11,7 k+12,7 k+13$ are winning positions.
- $7 k+7$ and $7 k+8$ are losing positions since any move will yield a winning position: $7 k+7=2+(7 k+5)=4+(7 k+3)=5+(7 k+2)$ and $7 k+8=2+(7 k+6)=$ $4+(7 k+4)=5+(7 k+3)$.
- $7 k+9$ is a winning position: $7 k+9=2+(7 k+7)$.
- $7 k+10$ is a winning position: $7 k+10=2+(7 k+8)$.
- $7 k+11$ is a winning position: $7 k+11=4+(7 k+7)$.
- $7 k+12$ is a winning position: $7 k+12=4+(7 k+8)$.
- $7 k+13$ is a winning position: $7 k+13=5+(7 k+8)$.

Since $2016=7(288)+0,2016$ is a losing position. Thus, the second player can force a win under this game.