This game can be described as an impartial edge colouring game on $K_n$ where creating a monochrome $K_k$ is not allowed, and the last player to make a move wins (normal play). Hence, it is equivalent to a nimber. I use the terms $P$-position and $N$-position sporadically to mean "a game state where the previous (resp. next) player has a winning strategy". I didn't calculate Sprague-Grundy values, but that is certainly doable. The game on $K_5$ with $K_3$ disallowed is a first player win. The game tree is small enough that I can give a complete strategy. I've also tried my best to make it RG/BY-colourblind readable by using dotted lines for anything that wasn't red or blue, but do let me know if it still causes problems and I could do something different.
As Flo Pfender mentioned, the first player should strive to create a monochromatic $C_4$ plus one edge, which I will call $C_4^+$
The dotted purple edge can be coloured red or blue, but the rest must be coloured blue, and the loser will be the player who makes the last move. Hence, the first player (us) will win if we can construct $C_4^+$ at any time. This will be the main goal of the strategy.
Beginning with one red edge, there are four non-isomorphic moves the second player can make:
Cases 1 & 2
The first two cases will elicit a similar response from us, which is to complete the triangle.
The second player can make 6 distinct moves from here, 3 with each colour.
A red response
For the first picture, we should complete the red $C_4$, and will ensure victory by adding one red line (from at least three possible) next turn. The latter two pictures can be combined into one by adding a red line, then on the next turn, our hero can create a $C_4^+$ by colouring either of the dotted green lines red. Since no other red edges can be drawn, they can only be blocked by colouring them blue, and with two possibilities, we will always have one available.
A blue response
The three pictures with blue lines added are as follows:
In the first two, we should complete to the picture below on the left, while in the third, we should play to the picture below on the right. Both of these positions have one triangle and a monotone length $2$ path, which is the same colour as the single triangle edge. These are $P$-positions (which is us) as we will show, and they come up again later in the final case, so I will refer to them as $T$ (for triangle) drawings.
First $T$
For the first, if our opponent plays any blue edge, we can complete it to a blue $C_4^+$:
For the first two, create a red $C_4$. It has two possible positions for an additional edge, so it can always be completed to a $C_4^+$. In the third, create a blue $C_4$, again with two places for a future blue edge. For the last two, colour a blue edge from the vertex with three red edges:
On the left, the blue $C_4^+$ cannot be blocked, while on the right, if the blue one is blocked by a red edge, then we can create a red $C_4^+$.
Second $T$
For the first four, make a red $C_4$, which can be completed to $C_4^+$ next turn, since there are at least two possibilities for the final edge. For the last one, draw a blue edge as shown - then the blue $C_4^+$ cannot be blocked.
Case 3
In the third case of the early game, our opponent has played the same colour as us on a non-adjacent edge. We should make it a monochrome path.
If they do not play a blue line to block the $C_4$, then we can play there, and we will have at least two options available for the final red line necessary for $C_4^+$. If they do play there, we will follow up with a red line to the untouched vertex (on the left below, which I will later refer to as a $Q$ drawing) - our opponent will be forced to block the $C_4^+$ again with a blue edge, which leaves a dotted black edge that can't be coloured safely, and three other edges which can only be coloured blue (on the right).
Each of the three safe edges to be coloured blue will not complete a blue triangle, either because the triangle would contain the black edge, or it contains an edge which is already red, so those are $3$ free moves. Thus, the second player will lose by having to play last.
Case 4
Finally, if your opponent chooses the opposite colour on their first turn, and doesn't play adjacent to you, you should connect the edges.
From here they have $13$ moves that continue the game, but fortunately we have covered most of them already. Three of the moves create a triangle plus one edge, which we know is an $N$-position from the first two cases.
The four possible moves from the bottom vertex to the two closest vertices can be extended to a $T$ drawing, again from the first section.
These should be played as follows, and note that the first two are now equivalent:
Of the four possible edges to colour red in the first image, three can be completed to $C_4^+$, and the last is the second player's response to $Q$, so the first player will win all of these.
Of the four possible blue edges, two can be completed to $C_4$ with two options for another blue edge. The other two should be followed by the dotted blue move, which makes them the same, and leaves two edges that can be given any colour, and one which cannot be safely coloured.
The three allowable blue edges can each be completed to $C_4^+$, while any of the four allowable red edges create a $T$ drawing plus one edge. Since we know that the $T$ drawing (triangle and monochrome 2-path) is a $P$-position, adding one edge makes it an $N$-position, so the first player wins.
I like this question a lot. It provides an interesting way of talking about
some of the ideas connected with the maximality principle and the
modal logic of forcing.
Let me make several observations.
First, Alice can clearly win, in one move, with any forceably
necessary statement $\sigma$, which is a statement for which
$\newcommand\possible{\Diamond}\newcommand\necessary{\Box}\possible\necessary\sigma$
holds in the modal logic of forcing, meaning that one can force so
as to make $\sigma$ remain true in all further forcing extensions.
She should simply force to make $\necessary\sigma$ true, and then
Bob cannot prevent $\sigma$ in any further extension, including the
limit model. Under the maximality
principle, all such
statements are already true.
Let me point out that there are some subtle issues about
formalization in the question. For example, the strategies here
would be proper class sized objects, and so one must stipulate
whether one is working in ZFC with only definable classes or
whether one has GBC or KM or whatever and whether global choice
holds. Another difficulty concerns the determinacy of the game,
since even open determinacy for class
games is
not a theorem of GBC.
Meanwhile, here is something positive to say. I shall consider only the direct-limit version of the game.
Theorem. Suppose there is a $\omega$-closed unbounded class of cardinals
$\kappa$ such that the statement $\sigma$ is forced by the collapse
forcing of $\kappa$ to $\omega$. Then Alice has a winning strategy
in the $\sigma$ game.
Proof. Let $C$ be the class $\omega$-club of such $\kappa$, and let
Alice simply play always to collapse the next element of $C$ above
the size of the previous forcing played by Bob. It follows that the
limit forcing $\mathbb{P}$ will collapse all the cardinals up to an
element $\kappa\in C$, and since $\kappa$ will have cofinality
$\omega$, it will also collapse $\kappa$ itself. Since the forcing
will also have size $\kappa$, in the direct limit case, it follows
that the forcing is isomorphic to $\text{Coll}(\omega,\kappa)$, and
so $\sigma$ holds in the model $V[G]$, so Alice has won. $\Box$
For example, if the GCH holds, then CH will be such a statement
$\sigma$, even though this is a switch, because the collapse
forcing will collapse $\kappa$ and the CH will hold in $V[G]$, as a
residue of the GCH in $V$. Thus, the GCH implies that Alice can win
the CH game.
A dual analysis is:
Theorem. If the class of cardinals $\kappa$ of countable
cofinality for which the collapse forcing
$\text{Coll}(\omega,\kappa)$ forces $\sigma$ is stationary, then
Alice can defeat any strategy of Bob in the $\sigma$ game.
Proof. For any strategy for Bob, there is a club of cardinals
$\theta$ such that $V_\theta$ is closed under the strategy, in the
sense that if Alice plays a poset in $V_\theta$ then Bob's strategy
will reply with a strategy in $V_\theta$. So by the stationary
assumption of the theorem, there is a $\kappa$ of countable
cofinality that is closed under the strategy. Alice can now play so
as to collapse more and more of $\kappa$, and Bob will always reply
with a poset below $\kappa$. So the limit forcing will again be the
collapse of $\kappa$, which forces $\sigma$. So Alice can defeat
this strategy.
$\Box$
For example, if the GCH fails on a $\omega$-closed unbounded class of
cardinals (this contradicts SCH), then
Alice can win with $\neg$CH. And if it fails on a stationary class
of such cardinals with countable cofinality, then Bob cannot win the $\neg$CH game.
Theorem. From suitable consistency assumptions, it is
consistent with GBC that the CH game is not determined with respect
to class strategies.
Proof. Using the Foreman-Woodin theorem that it is relatively
consistent that GCH fails everywhere, we can perform additional
forcing by first adding a generic class of cardinals, and then
forcing certain instances of GCH by collapsing cardinals. The result will be a model of GBC where the class of
cardinals $\kappa$ of cofinality $\omega$ at which the GCH holds is
both stationary and co-stationary. By the theorem above, considered
from either Alice's or Bob's perspective, either player can defeat
any strategy of the other player. So the game is not determined.
$\Box$
I guess the argument isn't just about CH, but rather any statement $\sigma$ such that there is a stationary/co-stationary class of $\kappa$ of countable cofinality such that $\sigma$ holds after the collapse of $\kappa$. In such a case, neither player can have a winning strategy.
The ideas appear to culminate in answer to question 1.
Theorem. The following are equivalent for any statement $\sigma$.
- Alice has a winning strategy in the $\sigma$ game.
- The class of cardinals $\kappa$ of countable cofinality, such that the collapse forcing of $\kappa$ to $\omega$ forces $\sigma$, contains a class $\omega$-club.
Proof. Statement 2 implies statement 1 by the first theorem above. Conversely, if statement 2 fails, then there is a stationary class of such $\kappa$ where $\sigma$ fails in the collapse extension. In this case, Bob can defeat any strategy for Alice, by Bob's analogue of the second theorem.
$\Box$
Best Answer
For even $n$, I claim that nobody has a winning strategy, and therefore both players have drawing strategies.
To see this, observe first that by the fundamental theorem of finite games, we know that either one of the players has a winning strategy, or both players have drawing strategies.
Next, I claim that Bob has a drawing strategy, which is simply to use the copying idea of user Mohemnist in the comments. He should simply pair up opposite vertices and make the coloring anti-symmetric. In this way, any string of red vertices is matched by a symmetric string of blue vertices, and therefore Bob can ensure that he will not lose.
But now, it follows that Bob cannot have a winning strategy, since Alice can pretend to be Bob by a strategy-stealing argument. Basically, this amounts to the observation that 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.
So we've shown that Bob has a drawing strategy and cannot have a winning strategy. It follows that Alice cannot have a winning strategy, and so we must be in the case of the fundamental theorem where both players have drawing strategies.
The strategy-stealing argument works regardless of whether $n$ is even or odd, showing that Bob can never have a winning strategy. But of course, we already knew this in the odd case, since Mohemnist showed in that case that Alice has a drawing strategy.