Chomp (Game with a Poisoned Chocolate Bar)

Question

In the game of Chomp, two players start with a chocolate bar, which is scored into an $a$ by $b$ array of squares (where $a\cdot b>1$). The square in the lower left is poisoned.

The players alternate turns. On their turn, a player chooses a square, then eats it, along with all of the squares which are either above it, to its right, or both. This continues until someone eats the poisoned square, wherein the non-poisoned player wins.

Here is an example of how the first two turns might go, where the "x" indicates the square that player chose:

Part 1: Show that the first player can win if she plays perfectly.

What if you have an $a\times\infty$ chocolate bar? This means that there are $a$ rows of squares, where each row continues infinitely to the right, and the left ends of the rows are all aligned. This grid still has a lower left corner, which is still poisoned. Some moves will require players to eat infinitely many squares, which we assume is possible.

Part 2: For which values of $a$ does the first player win on an $a\times\infty$ bar? Why?

Answer 1

Part 1: The first player wins on a rectangular board (of more than one square).

This is a classic nonconstructive strategy-stealing argument. Say to the contrary it was a second-player win. Then, the first player could "stall" by eating the single square in the corner, effectively becoming the second player and winning. Any move the opponent makes in response makes would have eaten this corner anyway, and so looks just like a first move, and so have a winning response to it.

Part 2: Who wins on $a \times \infty $?

For $a=1$:

The first player wins by eating all but the poisoned square.

For $a=2$:

The second player wins. By part 1, a player loses if they ever create a rectangle (except of just the poisoned square). So, the only potential non-losing starting move is to eat on the second row, leaving $n$ squares. To this, the second player leaves $n+1$ squares in the first row. The first player can never eat from the first row without creating a rectangle, and to any other move, the second player maintains the same shape with smaller $n$. Eventually, $n$ becomes $0$, and the first player must eat the poisoned square.

For $a>2$:

The first player wins by removing all but $2$ rows. Note that this observation would let us know a priori that at most one value of $a$ gives a second player win, since the first player can transform the bigger one into the smaller one.

Answer 2

For the purposes of this answer, I'll use "X.Y" to refer to a square X units to the right of, and Y units above, the bottom-left (poisoned) square.

I'll give my answer in the terms of various positions:

Position 0 (loss): only 0.0 (the poisoned square) remains - the active player must choose it, and thus loses.

Position 1 (win): only the first row or column of squares remains - the active player chooses 1.0 or 0.1, giving the other player Position 0.

Any board with $a$ = 1 or $b$ = 1 is an instance of Position 1, so the first player can win these cases as described above.

Position 2.1 (loss): only 0.0, 1.0, and 0.1 remain - the active player must choose 1.0 or 0.1, giving the other player Position 1.

Position 2.2 (loss): only 0.0, 1.0, 2.0, 0.1, and 0.2 remain - the active player must choose 1.0 or 0.1, giving the other player Position 1, or she must choose 2.0 or 0.2, allowing the other player to choose the other, leading to Position 2.1.

Position 2.x (loss): only 0.0 and an equal number of squares in the first row and first column remain. The fact that this is a losing position is provable via induction, using the explanations from Positions 2.1 and 2.2.

Position 3 (win): only 0.0 and an unequal number of squares in the first row and first column remain - the active player chooses the square that shortens the first row or first column so that they're equal in size, leading to Position 2.x.

Position 4 (win): Position 2.x, plus any other squares not in the first row or first column - the active player chooses 1.1, giving the other player Position 2.x.

Any board with $a$ = $b$ is an instance of Position 4, so the first player can win these cases as described above.

Hm, that's as far as I can see, for now. I know how I'd win a board with $a$ = 2, $b$ = 3 (pick the top-right corner, 2.1), but I'm having trouble proving the general case.

Answer 3

WIP: If you know the answers to some of the gaps in my attempt, feel free to share!

You must first calculate the number of remaining moves on the board. If a player is able to keep All Possible Moves (APM) to an even number by the time the board is reduced small enough, they will win!

For example, on a 2x2 board, there are 3 possible moves (1 individual block, and 2 2-blocks). Player 1 is then able to make the remainder of all possible moves (APM) into an even amount (2 moves left after taking 1,1), meaning that he can always take another move, keeping the number of moves left even until he takes the last move and wins.

The main issue with this problem is determining the initial number of possible moves on the board, and how each type of move will remove $X$ amount from APM. The player that keeps/makes the boards APM even on their turn, is the winner.

We can get APM of the board at the beginning by using $(X*Y) -1$

So for a 3x4 board, there are $3*4 -1 = 11$ possible moves.

This number is always odd, so you would think Player 1 should be able to make it even and keep it even, and force Player 2 to make it odd again!

The issue is, you keep APM even if it is already even, if the board is large enough. How large is large enough? Well, you need a minimum of a 4x1 rectangle, or a 2x2 box (area of units). Anything larger than this will also work! [($N*N$) or ($4*\frac{N}2[*1]$) where $N$ is even, or ($(4*N)*M$) ].

So now the issue becomes how many of these ($N*N$), ($4*\frac{N}2[*1]$) and ($(4*N)*M$) options there are left. We will call these KAE's (Keep APM's Even)

How we find that....I'm not sure atm.

But once we find it, if that number can remain even and the the APM can remain even after player one's turn, then player one should always be able to win!