Alice and Bob are playing a game. An n×n checkerboard lies between them. Alice begins by marking a corner square, and thereafter the two of them take turns marking squares; each one they choose must be adjacent orthogonally to the last one chosen, so together they’re making a path around the board. When the path can’t continue (because no unmarked adjacent square is available), then the player who moved last wins. For which n can Alice devise a winning strategy? What if she has to start by marking a square adjacent to a corner, rather than the corner itself?
|
SelectClick for Answer |
If n is even, Bob can win by imagining the board covered with dominos, each domino covering two adjacent squares. Now whenever Alice marks a square, he simply marks the square that shares its domino; this strategy cannot fail (even if Alice is free to choose any square on the board, not just orthogonally adjacent ones!).
If n is odd, then there must be one square on the board that’s not covered by a domino, and Alice can win by imagining a tiling in which that square falls in a corner and making her first move there.
If Alice must begin with a square adjacent to a corner on a board with odd n, then Bob can win. Imagine that the board has the standard checkerboard coloring and that the corners are black, so Alice is making her first move by choosing a white square. There’s a tiling in which the uncovered square is black, and Bob can now win by completing these dominos. Alice can never select the uncovered square herself because all the squares that she chooses are white.
(From the 12th All Soviet Union Mathematical Competition, Tashkent, 1978, via Peter Winkler’s Mathematical Puzzles: A Connoisseur’s Collection, 2003.)
|
