0
$\begingroup$

Well, first let me make this clear: I'm actually not sure about the background of the game, whether it was really posed (and solved) by Zermelo. But I'll state the game anyway (perhaps someone can inform me about it):

Arrange m$\times$n stones as an m$\times$n matrix A. The rule is: two players take turns to choose a stone in A; if A(i,j) is chosen, then it and all the stones to its northeast are removed. Specifically, the submatrix

A(1,j), A(1,j+1), ... , A(1,n)

A(2,j), A(2,j+1), ... , A(2,n)

. . .

A(i,j), A(i,j+1), ... , A(i,n)

is removed. Whoever removes the last stone(s) loses the game.

Zermelo proved that first player has a winning strategy for m$\times$n$>$1.


One can easily generalize the stone matrix to 3 dimensions m$\times$n$\times$k, in which one removes stones to the northeast and "behind" the chosen stone. The question is, whether the first player still has a winning strategy?

$\endgroup$
1

1 Answer 1

3
$\begingroup$

By a strategy-stealing argument, the three-dimensional game is a win for the first player. (If the most northeast-rearward cell isn't a winning first move, the second player must have a winning response A(i,j,k). But then A(i,j,k) would be a winning move for the first player also.) See http://www.win.tue.nl/~aeb/games/chomp.html for more information.

$\endgroup$
1
  • 1
    $\begingroup$ Indeed, the strategy-stealing argument can be used in any dimensions! Although it gives no clue how the first player can win:( $\endgroup$
    – Eric
    Aug 3, 2011 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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