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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Aug 3, 2011 at 13:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .