Instructions: Start with some number of tiles in between the two players. The players take turns taking either 1 or 2 tiles from the pile. The last player to take a tile wins.

Let $n$ is the number of tiles at the start.

If $n = 1$, the first player takes the one tile and wins immediately.

If $n = 2$, the first player takes the two tiles and wins immediately.

If $n = 3$, the first player takes 1 or 2 tiles, leaving behind 2 or 1 tiles, respectively. The second player takes the remaining tile(s) and wins.

If $n = 4$, the first player takes one tile, leaving three tiles behind. As we saw in the $n = 3$ case, this means the second player will lose.

If $n = 5$, the first player takes two tiles, leaving three tiles behind. As we saw in the $n = 3$ case, the second player loses.

If $n = 6$, the first player takes 1 or 2 tiles, leaving behind 5 or 4 tiles, respectively. As we saw in the $n = 4$ or $n = 5$ cases, the second player wins either way.

If $n = 7$, the first player takes 1 tile, leaving behind 6 tiles. As we saw in the $n = 6$ case, the second player loses.

Proposition: Let $n$ be the number of tiles. If $n \equiv 1 \,\, (\mathrm{mod} \,\, 3)$ or $n \equiv 2 \,\, (\mathrm{mod} \,\, 3)$, the player whose turn it is wins. If $n \equiv 0 \,\, (\mathrm{mod} \,\, 3)$, the player whose turn it is loses.

Proof. Let $P(n)$ denote the statement that the player whose turn it is wins if $n \equiv 1 \,\, (\mathrm{mod} \,\, 3)$ or $n \equiv 2 \,\, (\mathrm{mod} \,\, 3)$ and the player whose turn it is loses if $n \equiv 0 \,\, (\mathrm{mod} \,\, 3)$. We’re trying to prove this statement for all $n \geq 1$. We will prove this statement by inducting on $n$.

Base case(s). If $n = 1$, the first player takes the one tile and wins. If $n = 2$, the first player takes the two tiles and wins.

Inductive step. Suppose that $P(k)$ is true for all $k < n$. Our goal is to prove that $P(n)$ is true. We will consider three cases, depending on the remainder when $n$ is divided by 3.

Case 1: Suppose that $n \equiv 0 \,\, (\mathrm{mod} \,\, 3)$. The first player can take either one or two tiles. If they take 1 tile, the number of tiles remaining is congruent to 2 modulo 3, so by the inductive hypothesis the second player wins, meaning that the first player loses. If they instead take 2, the number of tiles left is congruent to 1 modulo 3, so by the inductive hypothesis the second player wins, meaning the first player loses.

Case 2: Suppose that $n \equiv 1 \,\, (\mathrm{mod} \,\, 3)$. The first player can take one tile. Then the number of tiles remaining is congruent to 0 modulo 3. Then, by the inductive hypothesis, the second player loses, meaning that the first player wins.

Case 3: Suppose that $n \equiv 2 \,\, (\mathrm{mod} \,\, 3)$. The first player can take two tiles, leaving behind a number of tiles which is congruent to 0 modulo 3. Then, by inductive hypothesis, the second player loses, meaning that the first player wins.

In all cases $P(n)$ is true.