Game Of Placing Knights
题目
Alice and Bob take turns placing knights on an empty chessboard, Alice first. A knight may not go on an occupied square, or on a square attacked by any knight already on the board. The first player who cannot place a knight loses.
Which player has a winning strategy?
解析
先自己试一试,卡住了再打开提示。
提示 1
In games like this the second player can often win by copying. What kind of copy could Bob use?
提示 2
Try having Bob mirror each of Alice's knights across the horizontal line through the middle of the board. The key check is that Alice's newest knight never attacks the square Bob wants.
查看解析
Answer: Bob wins.
The strategy. Number the rows to . Whenever Alice places a knight in row , Bob places one in row , same column. After each of Bob's moves the board is symmetric about the line between rows and .
Why Bob's reply is always legal. Before Alice's move the board is symmetric, and her move is legal. Call her square and its mirror .
- is a different, empty square. because is odd, so . If were already occupied, its mirror would be occupied too, but Alice just placed a knight there legally.
- No earlier knight attacks . Mirroring preserves knight moves. If an earlier knight attacked , then 's mirror, also on the board, would attack , and Alice's move would have been illegal.
- Alice's new knight doesn't attack . and are in the same column, but a knight move always changes the column by or .
Conclusion. Bob always has a reply, and the game must end because the board fills up. So the player who first gets stuck is Alice, and Bob wins.
A variant: mirroring through the centre of the board, from to , also works. Those two squares differ by an odd amount in both row and column, but a knight move changes one coordinate by an odd amount and the other by an even amount.