免费智力题中等

Game Of Chords

考察公司Citadel

There are $40$ points spaced evenly around a circle. Alice and Bob take turns drawing a chord between two of the points. A new chord may share an endpoint with an existing chord, but it may not cross one inside the circle. Alice goes first, and whoever cannot draw a legal chord loses. With perfect play, who wins?

解析

先自己试一试，卡住了再打开提示。

提示 1

Look for a first move that makes the board symmetric.

提示 2

Alice opens with a diameter. Can she then copy every move Bob makes?

查看解析

Alice wins by copying.

Move 1. With $40$ evenly spaced points, every point has an opposite point, so Alice draws a diameter $D$ . Reflecting in $D$ sends the $40$ points to themselves, and the board is now symmetric.

Every later move. Whenever Bob draws a chord $c$ , Alice draws its mirror image $c'$ in $D$ . This is always legal:

$c$ lies on one side of $D$ . It cannot cross $D$ inside the circle, so it sits in one half (it may touch an end of $D$ ).
$c'$ is new. $c'$ sits in the other half, so $c' \neq c$ . Before Bob's move the board was symmetric, so if $c'$ were already drawn, $c$ would have been too, and it wasn't.
$c'$ crosses nothing. Reflection maps the board before Bob's move onto itself, and $c$ crossed none of it, so $c'$ crosses none of it either. And $c'$ can't cross $c$ , because they sit in opposite halves.

After Alice's reply the board is symmetric again, so she can keep doing this. Alice always has a move whenever Bob does, and there are only finitely many chords, so Bob is the first one stuck.

Answer: Alice wins.

题目

解析