12
$\begingroup$

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:

enter image description here

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?

$\endgroup$
  • $\begingroup$ "along with the squares which are either above it, to its right, or both." - do you mean only the adjacent squares? For example, if the grid is 3x3, with 1 at the top-left and 9 at the bottom-right, and the first player chooses square 8, which other squares can she also eat - 5, 9, or both 5 and 9? Or can she also eat 2, since it's "above" 8? How about 6, since it's both above and to the right of 8? $\endgroup$ – Aaron Jun 9 '15 at 3:42
  • 2
    $\begingroup$ @Aaron Not just the adjacent squares. Also, you must eat all of mentioned squares. For example, if you choose square number 8, you must eat squares numbered 2,3,5,6,8 and 9. $\endgroup$ – Mike Earnest Jun 9 '15 at 3:59
  • 1
    $\begingroup$ I think after a certain a*b bar size, both players will be poisoned with a sugar overdose... $\endgroup$ – Mark N Jun 9 '15 at 13:45
  • 2
    $\begingroup$ Note that to up the stakes in the game, players can replace the chocolate bar with chocolate chip cookies and the poisoned piece with an oatmeal raisin cookie. $\endgroup$ – Kevin Jun 9 '15 at 16:43
  • 2
    $\begingroup$ @Kevin you monster! $\endgroup$ – Aaron Jun 9 '15 at 18:28
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Doesn't your answer to Part 1 assume that a hypothetical winning strategy for the second player doesn't begin with that player choosing the top-right square? After the first player eats this square, that move is no longer available to the second player. $\endgroup$ – Aaron Jun 9 '15 at 18:27
  • 2
    $\begingroup$ @mmking It's $a \times \infty$; there is no upper right square. $\endgroup$ – xnor Jun 9 '15 at 19:20
  • 5
    $\begingroup$ @Aaron The second player can never take the upper right square, since any move of the first player causes it to disappear. $\endgroup$ – xnor Jun 9 '15 at 19:20
  • $\begingroup$ @MarkN The rows are infinite, so it leaves $a \times \infty$. I think you have it transposed. $\endgroup$ – xnor Jun 10 '15 at 16:12
  • $\begingroup$ @xnor. [when a = 3 we get] 3 Columns, with infinite rows, in which player 1 reduces it to 3 columns, 2 rows (according to a > 2). (Rows are left-right, column is up-down.) In which player 2 takes the top right corner piece, which can keep Player 1 unable to win? I am not sure I have it transposed :s $\endgroup$ – Mark N Jun 10 '15 at 16:32
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Also, just to make a point, it's kind of hard to force APM to be even and then odd, particularly when you get down to smaller sizes. For example, when you have a a rectangle with 2 in the first row and 3 in the second row, you can force the APM to be 2, but your opponent would just take the last two squares and win. $\endgroup$ – mmking Jun 9 '15 at 20:35
  • $\begingroup$ @mmking If you start with a 3x2 rectangle [APM 5 - KAE - 0], and Player 1 removed the top corner (giving you row of 2, row of 3), then Player 2 can't win? $\endgroup$ – Mark N Jun 9 '15 at 20:42
  • $\begingroup$ No, I mean, the board was bigger, and Player 2 removed the top corner. $\endgroup$ – mmking Jun 9 '15 at 20:43
  • $\begingroup$ @mmking Then I don't think Player 1 was playing optimally, or there must have been an odd number of KAE's to get Player 1 in this position? Try to figure out a situation that can lead to this where they both play optimally (and find the initial APM's and KAE's)...I have not been too rigorous with my answer, so there might be holes in it. $\endgroup$ – Mark N Jun 9 '15 at 20:45
  • $\begingroup$ In the 3x2 situation there is 1 KAE, but player 1 destroys it on his first turn. $\endgroup$ – Mark N Jun 9 '15 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.