MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Return to Answer

2 Pi/3 longest path image added.

For testing potential answers to Q3, let me suggest http://www.math.chalmers.se/~wastlund/Quirks/Game.html.

The appearance as well as the specific set of bugs might depend on your browser, but as I hope will be clear, the length of the longest path as a function of the angle $\delta$ is quite funny (this is part of the reason I spent too much time on this problem, although I'm also interested in similar path-forming games for more "serious" reasons).

After drawing a couple of quick sketches I realized I wasn't even able to figure out the behavior when $\delta$ approaches $\pi$ from below. As it turns out, the number of edges in the longest path is 5 throughout the interval $3\pi/4 \leq \delta < \pi$. For $\pi/2 < \delta < 3\pi/4$ it's 7 (although the game-tree changes also at $2\pi/3$). At $\delta = \pi/2$ it has an isolated local minimum of 5, and for angles just smaller than $\pi/2$, it seems to jump to 23.

Here's why I couldn't let go of this problem: In all the cases where I can visualize the entire game-tree, which is when $\delta\geq \pi/2$,

(1) Alice, who draws the first arc, wins the game-version.

(2) Bob, while losing, can force Alice into a maximal-length path. In other words, Alice cannot force a win in fewer moves than the length of the longest path. This property holds for some similar path-forming games where there are explicit winning strategies.

(3) As a consequence of (1) and (2), the length of the longest path is always odd.

A couple of other observations: If we allow players to cross their own edges but not the opponent's, then an edge is never a liability, and consequently Alice has a non-losing strategy. If on the other hand we allow players to cross the opponent's edges but not their own, then an extra edge cannot be an advantage, and now Bob has a non-losing strategy (two more questions arise here: are these games too necessarily finite, and can the (winning?) strategies be made explicit rather than just exhibited by strategy-stealing?).

Therefore I thought for a while that I was on to something, and that there might be a beautiful reason that Alice must win.

So I let Maple analyze the game for some suitably chosen angles, working symbolically to get reliable results. This is feasible when $\delta$ is such that the ring $\mathbb{Z}[\cos\delta, \sin\delta]$ where the coordinates of the points lie, is either a sub-ring of $\mathbb{Q}$ or of some nice algebraic field (degree 2 or 4).

To summarize, I found counter-examples to each of (1), (2) and (3): For $\delta = \arctan(24/7)$, Bob wins at move 16 but the longest path has length 23. For $\delta = \arctan(12/5)$, the longest path has length 24 (but Alice can force a win in 13). Moreover, for $\delta=\pi/3$ there is a path of length 29 but Alice wins in 17. For $\delta=\arctan(4/3)$, Bob wins in 16 (I don't know the length of the longest path).

Addendum. (by J.O'Rourke). I took the liberty of adding an image of Johan's $\pi/3$ longest path from his applet, as detailed in his comment below. Note the near miss where the 28th segment just misses the 1st segment.

1

For testing potential answers to Q3, let me suggest http://www.math.chalmers.se/~wastlund/Quirks/Game.html.

The appearance as well as the specific set of bugs might depend on your browser, but as I hope will be clear, the length of the longest path as a function of the angle $\delta$ is quite funny (this is part of the reason I spent too much time on this problem, although I'm also interested in similar path-forming games for more "serious" reasons).

After drawing a couple of quick sketches I realized I wasn't even able to figure out the behavior when $\delta$ approaches $\pi$ from below. As it turns out, the number of edges in the longest path is 5 throughout the interval $3\pi/4 \leq \delta < \pi$. For $\pi/2 < \delta < 3\pi/4$ it's 7 (although the game-tree changes also at $2\pi/3$). At $\delta = \pi/2$ it has an isolated local minimum of 5, and for angles just smaller than $\pi/2$, it seems to jump to 23.

Here's why I couldn't let go of this problem: In all the cases where I can visualize the entire game-tree, which is when $\delta\geq \pi/2$,

(1) Alice, who draws the first arc, wins the game-version.

(2) Bob, while losing, can force Alice into a maximal-length path. In other words, Alice cannot force a win in fewer moves than the length of the longest path. This property holds for some similar path-forming games where there are explicit winning strategies.

(3) As a consequence of (1) and (2), the length of the longest path is always odd.

A couple of other observations: If we allow players to cross their own edges but not the opponent's, then an edge is never a liability, and consequently Alice has a non-losing strategy. If on the other hand we allow players to cross the opponent's edges but not their own, then an extra edge cannot be an advantage, and now Bob has a non-losing strategy (two more questions arise here: are these games too necessarily finite, and can the (winning?) strategies be made explicit rather than just exhibited by strategy-stealing?).

Therefore I thought for a while that I was on to something, and that there might be a beautiful reason that Alice must win.

So I let Maple analyze the game for some suitably chosen angles, working symbolically to get reliable results. This is feasible when $\delta$ is such that the ring $\mathbb{Z}[\cos\delta, \sin\delta]$ where the coordinates of the points lie, is either a sub-ring of $\mathbb{Q}$ or of some nice algebraic field (degree 2 or 4).

To summarize, I found counter-examples to each of (1), (2) and (3): For $\delta = \arctan(24/7)$, Bob wins at move 16 but the longest path has length 23. For $\delta = \arctan(12/5)$, the longest path has length 24 (but Alice can force a win in 13). Moreover, for $\delta=\pi/3$ there is a path of length 29 but Alice wins in 17. For $\delta=\arctan(4/3)$, Bob wins in 16 (I don't know the length of the longest path).