Consider the following game Chomp: A rectangular array of (m times n) dots is given, in (m)
Question:
Consider the following game Chomp: A rectangular array of \(m \times n\) dots is given, in \(m\) rows and \(n\) columns, like \(3 \times 4\) in the next picture on the left. A dot in row \(i\) (from the top) and column \(j\) (from left) is named \((i, j)\). A move consists in picking a dot \((i, j)\) and removing it and all other dots to the right and below it, which means removing all dots \(\left(i^{\prime}, j^{\prime}\right)\) with \(i^{\prime} \geq i\) and \(j^{\prime} \geq j\), as shown for \((i, j)=(2,3)\) in the middle picture, resulting in the picture on the right:
Player I is the first player to move, players alternate, and the last player who removes a dot loses.
One can think of these dots as (real) cookies: a move is to eat a cookie and all those to the right and below it, but the top left cookie is poisoned.
In the following questions, do not rush into any quick and false application of Nim values. Part (c) has an elegant but tricky answer.
(a) Assuming optimal play, determine the winning player and a winning move for Chomp of size \(2 \times 2\), size \(2 \times 3\), size \(2 \times n\), and size \(m \times m\), where \(m \geq 3\). Justify your answers.
(b) As it is described here, Chomp is a misère game where the last player to make a move loses. Suppose we want to play the same game but so that the normal play convention applies, where the last player to move wins. How should the array of dots be changed to achieve this? (Normal play with the array as given would be a boring game, with the obvious winning move of taking the top left \(\operatorname{dot}(1,1)\).
(c) Show that when Chomp is played for a game of any size \(m \times n\), player I can always win (unless \(m=n=1\) ).
Step by Step Answer: