$n \times m$ individual cells. In each turn, one player breaks the bar along any vertical or horizontal line and the other player chooses which of the two parts to continue the game with. The player left with just one cell loses. Alice goes first in every game. If they both play optimally, who has the winning strategy for a game starting with: (a) $100\times101$ bar, (b) $101\times103$ bar, (c) $100\times102$ bar?
-
- Consider the game ‘
$21$’.$A$and$B$take turns counting up from$1.$At each turn, each player says either 1 or 2 consecutive numbers, and the next player must follow from there. The player that says$21$wins. If$A$starts, who has the winning strategy? (Hint: consider working from$21$backwards.)
- Consider the game ‘
-
Have you tried playing the game with simpler dimensions?
-
Why not fix one dimension and change the other?
-
Consider an
$n\times 1$chocolate bar. -
How does the parity of
$n$affect the outcome? -
Could you use similar reasoning for the general
$n \times m$game? -
Consider the different possible parity combinations of
$n$and$m.$ -
From which such parity combination can you force your opponent to play such that you’re guaranteed to return to the original combination?
-
Remember to use results you’ve already shown.
-
Consider the
$even \times even$case. When is it unavoidable for one player to give the other a winning position? How do they get there?
-
First, let’s consider the
$n\times 1$game. We can easily see that$n=1$is a losing position, while$n=2$is winning. After a few examples like this, we conjecture that$n$being even is the victory condition. We can see that inductively: Alice can split an even number into two odd numbers, forcing Bob to split an odd number. An odd number can only be split into an even and an odd, so Alice can always pick the even number. Eventually we get to the base case$2\times1,$which is a win for Alice.Now we’ll consider the multi-dimensional cases
$n \times m,$starting with the$even \times odd$case (which is the same as the$odd \times even$case by symmetry). We can apply the same argument as earlier - Alice can always split along the even edge to force Bob into an$odd \times odd$position, so Alice can always choose to go back to$even \times odd.$Eventually Bob is forced into$odd \times odd,$where one side is of length$1,$which from earlier, we know is a losing position. Hence$even \times odd$and$odd \times even$are winning positions, while$odd \times odd$is a losing position. So we can immediately answer that (a) is a winning position and (b) is a losing position for Alice.Finally, we consider the
$even \times even$case. Neither player will want to give the other the winning$odd \times even$position, but this is unavoidable at$2\times2,$so this is a losing position. The longest the players can maintain an$even \times even$position depends on how many times we can subtract 2 from each dimension before getting to$2\times2.$Therefore the question becomes whether we need to subtract 2 an even or an odd number of times before getting to$2\times2.$Hence we can divide both dimensions by 2 to solve the problem. In the case of (c) dividing by 2 gives us$50 \times 51,$which means we can subtract 2 an odd number of times. Hence (c) is also a winning position for Alice.