Winning strategy for an asymmetric game

combinatorial-game-theorynumber theorypuzzle

Two players, $\text{A}$ and $\text{B}$, are playing an asymmetrical game. There are $n$ points on the game board. Each turn player $\text{A}$ targets a pair of points and player $\text{B}$ says whether those two points are connected or unconnected. $\text{A}$ can target each pair only once and the game ends when all pairs have been targeted. Player $\text{B}$ wins iff a point is connected with all other points on the very last turn, while player $\text{A}$ wins if any point is connected with all other points on any turn but the very last one OR if no point is connected to all other points after the last turn. For what values of $n$ does either player have a winning strategy?

Clarifications on the question:

  • $\text{B}$ gets to decide if a pair of points targeted by $\text{A}$ are $\text{connected}$ or $\text{unconnected}$.
  • The graph of the points isn't important, as any pair of points on the board may be targeted.

My attempt:

For $n = 2,3$, $\text{B}$ has trivial winning strategies of answering $(\text{connected})$ and $(\text{connected, unconnected, connected})$, respectively.

For $n > 3$, $\text{A}$ can naïvely approach the game by asking one-by-one if all the points from $2$ to $n$ are connected to $1$, then if all the points from $3$ to $n$ are connected to $2$, and so on. $\text{B}$'s winning strategy is: answer $(\text{connected})$ for all pairs $\text{(i, i + 1)}$ to $\text{(i, n – 1)}$ for point $\text{i}$, but answer $\text{(unconnected)}$ for the pair $\text{(i, n)}$. At the last turn, $\text{A}$ targets $\text{(n – 1, n)}$. $\text{B}$ can answer $\text{(connected)}$ and win, as point $\text{n – 1}$ will then be connected to all other points on the game board.

Clearly, $\text{A}$'s naïve approach isn't a winning strategy.

But this does suggest that $\text{B}$ loses any chance of winning mid-game if all the points are $\text{unconnected}$ to at least one other point, because then no point can be connected to all the other points at the last turn. Hence, $\text{B}$ should try to answer $\text{connected}$ for all pairs $\text{(k, i)}$ for at least one point $\text{k}$, so that $\text{k}$ may be $\text{connected}$ to another point in the last turn.

However, I can't think of general strategies $\text{B}$ might try that would achieve this.

Best Answer

Player B has a winning strategy for all $n\ge2$.

Let me describe the game in an equivalent but more natural way, which will make it easier to describe the winning strategy. The game is played on the complete graph $K_n$ ($n\ge2$), which consists of $n$ vertices, each pair of vertices joined by an edge. Initially all edges are unpainted. At each turn A chooses an edge, which B paints blue or red. B wins if, after the last edge is painted, but not before that, there is a vertex which is joined to all other vertices by blue edges; otherwise A wins.

B's winning strategy is described by three rules. Of course, for B to win, the last edge to be painted must be painted blue. Let me call a vertex "red" if at least one of its incident edges has been painted red. Observe that, if it ever happens that two red vertices are joined by an unpainted edge, then A can win by saving that edge for last. Hence the need for the first two rules:

Rule 1. Paint the last edge blue.

Rule 2. Never paint an edge red if that would result in two red vertices being joined by an unpainted edge.

Rule 3. Use red paint whenever permitted by Rules 1 and 2.

Thus, if $n\gt2$, the first edge will always be painted red, the second will always be painted blue.

I have to show that this is a winning strategy. Rule 2 guarantees that "every vertex incident with a red edge" can't happen before all edges have been painted, nor can it happen at the end because of Rule 1. Therefore, when all edges have been painted, there is at least one vertex $v$ which is joined to all the other vertices by blue edges. I claim that such a "blue star" can't appear before the very end.

After the first turn there are two red vertices, neither of which is joined to $v$ by a blue edge. At some point the number of red vertices not joined to $v$ by blue edges must decrease from one to zero. But it's easy to see that Rule 3 prevents this from happening before the very last turn.

Related Question