# 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?

×