跳到主要内容
← 返回题库
免费智力题中等

Game Of Placing Knights

考察公司GravitonSusquehanna International Group

题目

Alice and Bob take turns placing knights on an empty 8×88 \times 8 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 11 to 88. Whenever Alice places a knight in row rr, Bob places one in row 9−r9 - r, same column. After each of Bob's moves the board is symmetric about the line between rows 44 and 55.

Why Bob's reply is always legal. Before Alice's move the board is symmetric, and her move is legal. Call her square XX and its mirror X′X'.

  • X′X' is a different, empty square. r≠9−rr \ne 9 - r because 99 is odd, so X′≠XX' \ne X. If X′X' were already occupied, its mirror XX would be occupied too, but Alice just placed a knight there legally.
  • No earlier knight attacks X′X'. Mirroring preserves knight moves. If an earlier knight KK attacked X′X', then KK's mirror, also on the board, would attack XX, and Alice's move would have been illegal.
  • Alice's new knight doesn't attack X′X'. XX and X′X' are in the same column, but a knight move always changes the column by 11 or 22.

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 (r,c)(r, c) to (9−r,9−c)(9 - r, 9 - c), 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.