No Knights Attack

Probability Level 1

Andrew and Benjamin are playing a game on an $8 \times 8$ chessboard. Each turn, they place a knight in a position that isn't threatened by other knights that are already on the board. The first person who is unable to place a knight loses the game.

As an explicit example, the board above shows a possible sequence of 5 turns, where all the squares that are threatened by other knights are marked with red X's.

If Andrew goes first, who will win this game?

Andrew Benjamin

1 solution

Brian Moehring
Feb 1, 2017

The key to this problem is to notice something rather innocuous: The center of the board lies at the corner of four squares

This implies two facts:

Every square can be paired with a second square so that the two are symmetric about the center of the board.
Knights on these paired squares cannot attack one another.

Once you notice that, Benjamin's strategy is apparent. When Andrew plays a knight on a square, Benjamin finds that square's pair across the center of the board and plays his knight there. Using this strategy, Benjamin can guarantee that the board will always have $180^{\circ}$ symmetry on Andrew's turn. Therefore, if a square is available to play on Andrew's turn, its pair would also be a valid play on Andrew's turn, and since a knight on a square cannot attack a knight on its paired square, the pair will still be a valid play on Benjamin's turn.

Since Benjamin will always have a valid move in response to any move Andrew makes, the game must end with Andrew not being able to play, so Benjamin wins .

As a side-note that I found interesting, the generality of the strategy actually solves the corresponding knight game for every rectangular $m\times{n}$ board as long as $m$ and $n$ have the same parity. When one is even and the other odd, however, I have no clue who would win (so if anyone knows, I'd love to hear!)

Brian Moehring - 4 years, 4 months ago

The same (suitably modified) argument works.

Calvin Lin Staff - 4 years, 4 months ago

Huh... yeah, you're right. You just have to use reflective symmetry instead of rotational symmetry, and it gives you strategies for all $m\times n$ boards with at least one of $m,n$ even.

Brian Moehring - 4 years, 4 months ago

Clearly Andrew will win the game played on a 1 x n board when n is odd. Seems like he'd also be able to win the game on any m x n board when both are odd if his first move would be to claim the center square and then he used a symmetry strategy for the rest of the game.

Richard Desper - 4 years, 3 months ago

Certainly. On a rectangular $m \times n$ board, Andrew will win if and only if the product $mn$ is odd.

Brian Moehring - 4 years, 3 months ago

The problem is stated as if it does not matter what strategy is used, that exactly one player is assured to win once it is determined who goes first. Thus one can use this knowledge and choose any strategy to play one game through and determine the winner. I chose that Andrew and Benjamin both use the strategy of always playing on white squares until all white squares are filled. Benjamin obviously wins because there are an even number of white squares and once all white squares are occupied, all black squares are threatened.

The problem would be more challenging if one included a possibility such as "cannot be determined" among the answers.

george palen - 3 years, 1 month ago

In a finite combinatorial game , there is always a winner. So, arguably "cannot be determined" would be a red herring and doesn't add significantly to the problem.

Calvin Lin Staff - 3 years, 1 month ago

The original problem did not mention that each player would optimize their strategy. In many finite combinatorial games, take your Tic-tac-toe as the easy example, it is readily apparent that the strategy used by the two players affects the outcome of the game. Since the problem made no mention of optimization of strategy, the problem solver could assume that strategy made no difference in the outcome and therefore pick the easiest strategy for analysis. This is why I think that that wording such as "...if both players optimize their strategy..." or a possible answer of "cannot be determined, (depends upon player strategy)" might be appropriate.

george palen - 3 years, 1 month ago

No Knights Attack

1 solution

0 pending reports