Skip to main content
1 of 3
Joel David Hamkins
  • 236.2k
  • 44
  • 777
  • 1.4k

For even $n$, I claim that nobody has a winning strategy, and therefore both players have drawing strategies.

To see this, observe first that Bob has a drawing strategy, which is simply to use the copying idea of user Mohemnist in the comments. By making the coloring symmetric, it follows that Bob will not have lost.

But now, it follows that Bob cannot have a winning strategy, since Alice can pretend to be Bob by a strategy-stealing argument, since it cannot be advantageous to go second. That is, Alice can simply start by coloring any vertex red, and thereafter pretend to be the second player, following the winning strategy for Bob, but with swapped colors. If that strategy should ever direct her to color the already-colored vertex, then she can simply take another free move.

Thus, Bob has a drawing strategy and cannot have a winning strategy. Since this is a finite game, it now follows that both players have drawing strategies.

Joel David Hamkins
  • 236.2k
  • 44
  • 777
  • 1.4k