Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
This game is called Chomp, and one place to start is en.wikipedia.org/wiki/Chomp . –  Kevin Buzzard Aug 3 '11 at 12:36
    
Thank you Kevin! –  user16033 Aug 3 '11 at 12:42

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Indeed, the strategy-stealing argument can be used in any dimensions! Although it gives no clue how the first player can win:( –  user16033 Aug 3 '11 at 13:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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