Chomp

The game Chomp is a game played by two players with a piece of "chocolate", which can be modeled as a set of squares \((r_i, c_i)\) where \(r_i, c_i \ge 0\) for all squares. Starting from the first player, each player in turn selects one square \((r_p, c_p)\) and eats (removes) it along with all pieces with coordinates at least equal to it; that is, all squares \((r,c)\) where \(r \ge r_p, c \ge c_p\). The player that makes the last move loses.

The picture shows a sample game on a \(3 \times 3\) board with lower-right piece removed (first diagram). The first player makes the move \((0,2)\), eating it along with the piece below it (second diagram). The second player makes the move \((1,0)\), which leaves a \(1 \times 2\) rectangle (third diagram). The first player then moves on \((0,1)\), forcing the second player to take the remaining block and thus lose.

Suppose the players play a game of Chomp on an \(m \times n\) rectangular block of chocolate. Among all such games where \(1 \le m,n \le 10\), how many games are won by the first player?

×

Problem Loading...

Note Loading...

Set Loading...