Chomp ∞

The first player wins for all $n \neq 2$ .

For $n=1$ , this is trivial; the first player moves to $(0,1)$ , leaving a $1 \times 1$ block for the second player.

Now, observe how for $n=2$ the first player always loses. We proceed by induction, showing that boards in the form of $2 \times k$ with the lower-right corner missing is a loss for the player to move, and then show how the second player can always force this to happen, thus making sure that the second player is not the last to make a move.

First, boards in the form of $2 \times k$ with the lower-right corner missing is a loss for the player to move.

We prove this by strong induction. For $k=1$ , the board is simply a $1 \times 1$ rectangular block, which is a loss for the player to move. Suppose that we have proven the claim for all $k < m$ ; now we want to prove the claim for $k=m$ .

There are three kinds of possible moves for the player to move, all losing:

• $(0,0)$ is trivially suicidal.
• $(0,c)$ for $c > 0$ is responded by $(1,c-1)$ , thus reducing to the case $k=c$ . Since $c < m$ , this is a loss for the player to move by induction hypothesis.
• $(1,c)$ is responded by $(0,c+1)$ , thus reducing to the case $k=c+1$ . Since $c < m-1$ , we have $k = c+1 < m$ , and thus this is a loss for the player to move by induction hypothesis.

Thus in all cases, the player to move loses for all $k$ .

But $2 \times \omega$ is just a special case of this, whose analysis follows exactly like above:

• $(0,0)$ is trivially suicidal.
• $(0,c)$ for $c > 0$ is responded by $(1,c-1)$ , thus reducing to the case $k=c$ which loses for the first player (for being the player to move).
• $(1,c)$ is responded by $(0,c+1)$ , thus reducing to the case $k=c+1$ which loses for the first player (for being the player to move).

Thus $2 \times \omega$ loses for the first player.

And now $n \times \omega$ for $n \ge 3$ wins for the first player, which can simply play on $(2,0)$ , reducing it to the case $2 \times \omega$ .