# A matchstick game

On the table there is a $9\times9$ grid made of matchsticks, so that each of the $81$ little squares is bordered by exactly four matchsticks. Alice and Bob play the following game.

• Alice and Bob move alternatingly. Alice makes the first move.
• In every move, the active player removes one matchstick from the grid.
• The player who destroys the last little square wins the game. (A little square is destroyed, once it is bordered by at most three matchsticks.)

Question: Which player is going to win this game? (As usual, we assume that Alice and Bob both use optimal strategies.)

Fixing some problems with Oray's solution, the winner is

Bob.

Because

For every position that is not winnable immediately or two separated squares, the current player can always stall so that the other player can't win in the next turn. But the unstallable position has an even number of matchsticks, so it's always Alice who is forced to hand over the game by destroying one of the squares.

Bob's strategy has to leave 2 squares left which are not connected to each other while Alice strategy would be leaving 2 squares together. Because Alice and Bob will continue destroying matchsticks until 2 squares left and none of them will attempt to touch the matchsticks which constitute these last two squares. The reason is if any removes a matchsticks from any of the last square's matchstick the other one will win automatically.

The tricky part would be if the last squares are separated or not. If they are separated there will continue removing until 8 matchsticks left and Alice would have to remove a stick from a square and Bob will win automatically. On the other hand, if two squares are together, the number of matchsticks left will be 7 and Bob would take a matchstick from the last two squares and Alice will win.

For this Alice will always try to remove a matchstick for the square separated from the other squares while Bob will try otherwise. Since Bob will have lots of options to make squares separated Bob will win if he removes matchsticks optimally. Let say there are 4 squares left next to each other like a bigger square; This is actually the best case for Alice to win this game but unfortunately Bob will not attempt to remove any matchstick from this square in optimal case and Alice will have to remove a matchstick from this square while the other matchsticks are removed. So the game becomes like 2x2 and Alice still plays next. So Alice would have to remove a matchstick and 3 squares left, whichever square is destroyed, Alice will destroy the diagonal square and will make two squares separated and win!

In short, whoever starts as the second will win this game or BOB!

• The problem ffao refers to is that Alice doesn't want to leave 2 adjacent squares anymore than Bob does. Leaving two adjacent squares (and all others broken) gives the win to the other player, no matter who you are. Both players will leave 2 nonadjacent squares until all other matches are removed. Mar 28, 2016 at 14:09