A chocolate bar is divided into an m x n grid and one of the corner pieces is poisoned. In the chocolate bar game, two players take turns alternately dividing the chocolate into two pieces and choosing which of the pieces to eat. The players may only break the chocolate bar along a single grid line. The person who is forced to take the poisoned piece loses. For which values of m, n, does
(a) the first player have a winning strategy? (b) the second player have a winning strategy?
Prove your conjecture by induction. Hint: set k = min{m,n} and use induction on k.
Edit: This is an assignment question. I managed to reduce the question down into base cases of a 2x2 grid (where player 2 wins), a 2 x m grid where m >= 3 (player 1 wins), and a 3 x m grid where m >= 3 (player 2 wins). The loser for the larger grids can be determined by whoever is the last player to reduce the grid to 3 x m. The problem is I am unable to show this using an induction proof.
Because this question has the combinatorial game theory tag, I'm going to assume that both players are told before the game starts which corner is the poison corner. We'll prove the following claim by induction:
Claim: For an $n\times m$ chocolate bar, player one can force a win if $m\ne n$, and player two can force a win if $m=n$.
Base Case: If the chocolate bar is $1\times1$ then player one loses. If the chocolate bar is $1\times m$ for $m>1$, or $n\times1$ for $n>1$, then player one can force a win by eating everything except the poison square. We've shown that the claim holds when $n=1$ or when $m=1$.
Inductive Case: Let's suppose that we've proved the claim for every $a\times b$ chocolate bar where all three of the following hold: (1) $a\le n$, (2) $b\le m$, and (3) either $a<n$ or $b<m$ (or both). We will show that this implies that the claim also holds for an $n\times m$ chocolate bar.
Suppose $m\ne n$, and let $k=\text{min}\{m,n\}$. Then player one can force a win by eating enough rows or columns to produce a $k\times k$ chocolate bar. By doing so, player one will be playing second in a $k\times k$ version of the game, and by induction $k\times k$ is a win for the second player. Hence player one can win by eating enough rows or columns so that $k\times k$ is left over.
Suppose $m=n$. No matter what player one does, the new game will be $k\times m$ for some $k<m$ or $n\times k$ for some $k<n$. In either case, it follows by induction that the first player can force a win in this situation, and since player two will be the next to play, player two can force a win.
We've shown that if we assume the claim holds for any $a\times b$ chocolate bar with $a\le n$, $b\le m$, and either $a<n$ or $b<m$, then the claim also holds for an $n\times m$ chocolate bar. This completes the proof by induction.