No stalemate in a modified version of Martin Gardner's game of Chomp?

90 Views Asked by At

Reference: Martin Gardner's game Chomp (from Mathematical Games, in Scientific American).

In my game of Free Chomp the start is a non-empty finite or infinite polyomino in the Cartesian plane, with corners of its sub-squares on points with integer co-ordinates.

A move consists of removing all the part of the polyomino that lies in any open 1/4-plane whose edges are parallel to the co-ordinate axes, and whose corner has integer co-ordinates. A move must remove at least one of the sub-squares of the polyomino, and if the move does not remove all of it, then what remains must be a connected set, i.e. must still be a polyomino.

There are 2 players, and the player who removes the last piece of the polyomino loses.

QUESTION: Can a stalemate position exist, where a player is required to move but has no legal move?

It seems not, but I have been unable to prove it. Of course if the remaining polyomino is a subset of a 1/4-plane there is always the losing move of removing all of it.

1

There are 1 best solutions below

0
On BEST ANSWER

Consider an infinite polyomino that starts at the origin and goes out to infinity along a spiral path. There is then no legal move, since removing any 1/4-plane will disconnect the polyomino (each turn of the spiral that is sufficiently far from the origin will become its own connected component).

More generally, you can construct a similar example if you replace 1/4-planes by any other countable collection of unbounded co-unbounded subsets of the plane. Just draw a polyomino that forms a simple path and crosses in and out of each set in your collection one by one, so that removing any of the sets will disconnect the path (it is possible to do this since each of the sets is unbounded and co-unbounded).