A simple game with $n$ points in 3D space - red triangle wins

Question

(Once again a son is torturing his father...)

Alice and Bob play a fairly simple game with $n$ predefined points in 3D space. No four points are complanar (which also implies that no three points are collinear).

They play in turns by connecting points that are not yet connected with straight segments. On her turn Alice connects a single pair of unconnected points with a single segment of red color. After that Bob connects $k$ pairs of unconnected points with $k$ segments of blue color.

Alice wins if she is able to create a triangle with red sides. If all points are connected and Alice was not able to create a red sided triangle before that, Bob wins.

Who has a winning strategy?

My thoughts: obviously, the outcome of the game heavily depends on releation between $n$ and $k$.

Suppose that $k=1$ with big enough value for $n$. Alice will simply draw segment $AB$, Bob draws his segment at will, Alice then draws $AC$, Bob blocks triangle $ABC$ by drawing segment BC, Alice draws segment $AD$ and Bob is lost. He cannot block triangles $ABD$ and $ACD$ by drawgin a single segment.

On the other side, with $k$ big enough, Bob can easily block creation of all red triangles by drawing a lot of lines.

So for $k\le k_1$, Alice wins. For $k\ge k_2\ge k_1$, Bob wins. I need some estimate for $k_1$ and $k_2$ (better than mine). Also note that the game always has a winner. Does it mean that $k_1=k_2$? I guess it does, but if we are just trying to estimate the lower and the upper bound, we can come up with two different values.

Answer 1

This is called a biased Maker-Breaker game; it was first proposed by Chvátal and Erdős in their 1978 paper Biased positional games. (The results below are Theorem 5.1 in that paper.)

In that paper, they prove that when $k < \sqrt{2n+2} - \frac52$, Alice has a winning strategy, which has already been covered in the other answers: Alice draws many segments out of a single point $v$, and eventually there are so many other endpoints of those segments that Bob can't connect them all.

---

When $k \ge 2\sqrt n$, they prove that Bob has a winning strategy. Here, Bob will follow the rule that whenever Alice plays a segment $vw$, Bob will draw $\lfloor \sqrt n \rfloor$ segments out of point $v$ and $\lfloor \sqrt n \rfloor$ segments out of point $w$. (If there are fewer than $\lfloor \sqrt n \rfloor$ undrawn segments out of either point, Bob can skip drawing those.) Which segments will Bob draw? We'll get to that later.

A consequence of this rule is that Alice can never draw more than $\sqrt n + 1$ segments out of the same point (every time she draws a segment out of some point, Bob draws $\lfloor \sqrt n \rfloor$ out of the same point).

When Alice draws segment $vw$, the only ways she could win on the next move (which Bob has to thwart) are triangles using that segment: triangles $uvw$ with some third point $u$.

• There are at most $\sqrt n$ other segments she's drawn out of $v$, so there's at most $\sqrt n$ triangles $uvw$ where $uv$ and $vw$ are already present. Bob can draw segment $uw$ for each of those triangles, as part of his "draw $\sqrt n$ segments out of $w$" rule, and block them all.
• Similarly, there are at most $\sqrt n$ other segments Alice has drawn out of $w$, so there's at most $\sqrt n$ triangles $uvw$ where $uw$ and $vw$ are already present. Bob can block them all as part of his "draw $\sqrt n$ segments out of $v$" rule.

So at every step, Bob can block Alice from winning on the next move. It follows that Alice can never make a triangle, and Bob wins.

---

Okay, so that was what we knew 42 years ago. Has there been progress since then?

Yes, but we still don't know the exact answer. Approximately, the above shows that the critical value of $k$ is somewhere between $1.414 \sqrt n$ and $2 \sqrt n$. Since then, the upper bound has been reduced. This paper is I think the best upper bound known so far, bringing the upper bound down to about $1.633 \sqrt n$. But there's still a gap.

Answer 2

We shall consider a natural reformulation of the game as a coloring of edges of a complete graph $G=K_n$ on $n$ vertices.

Proposition 1. If $k<\sqrt{2n-2}-\tfrac 32$ then Alice has a winning strategy.

Proof. Consider the following strategy for Alice. At the first stage, Alice picks a vertex $v$ of $G$ and then, as far as she can, she colors edges incident to $v$. When the first stage ends, Alice looks whether there are two vertices $u$ and $w$ adjacent to $v$ by a red edge, which are not adjacent by a blue edge. If they are then she wins. Assume that during the first stage $r$ edges were colored red and $b=kr$ edges were colored blue. If Alice cannot immediately win then among these $b$ edges are all not red edges incident to $v$ and all edges connecting vertices adjacent to $v$ by a red egde. Than is $kr\ge n-1-r+\tfrac {r(r-1)}2$, which implies

$$k\ge \frac {n-1}r +\frac r2-\frac 32\ge 2\sqrt{\frac {n-1}r\cdot\frac r2}-\frac 32= \sqrt{2n-2}-\frac 32. \square$$

Maybe the strategy described in the proof of Proposition 1 is a worst case for Bob.

Proposition 2. If $k\ge 2n-2$ then Bob has a winning strategy.

Proof. Bob's winning strategy is to color all possible edges between vertices of red edges. $\square$

I checked by hand small values of $n$ for a value $k_1=k(n)$ such that if $k\le k_1$ then Alice has a winning strategy and if $k>k_1$ then Bob has a winning strategy. We have $k_1(3)=k_1(4)=0$ and $1\le k_1(5)\le 2$.

Answer 3

At any time in the game Alice creates potential for more triangles to be constructed, if at each step she kept radiating a new segment from the original angle she created in first two steps.

At step 1 Alice starts with a segment. Bob can build k segments which will eliminate all but endpoints of Bob’s newly created polygonal line.

After step 1, Bob eliminated k-1 points

At step 2 Alice has completed an angle. Bob is compelled to close the potential triangle so he uses a hop for it. The remaining k-1 polygonal line originated in one endpoints of the angle has consumed k-2 points (k-1 segments are formed with k points; one Endpoint is on Alice’s angle and another one is free; remaining k-2 points are internal to the polygonal line and could never become segments or sides in a possible triangle for Alice so they are eliminated from the game) After step 2, (k-1)+(k-2) points are eliminated

At step 3 Alice radiates another segment from the angle vertex, thus she creates potential for two triangles. Bob counters the two triangles and eliminates another k-3 points. After step 3, 3k-1-2-3 points are eliminated.

This continues to step k+2 when Alice created potential for k+1 triangles. Bob can only block k triangles. If the game reaches this point then Bob looses.

However, after step k+1 Bob has eliminated $k(k+1)-(1+2+...+k+1)=k(k+1)-\frac{(k+1)(k+2)}{2}=\frac{(k-2)(k+1)}{2}$ points.

The points needed still in the game (for Alice to win) are one for the vertex plus k+2 to overcome k hops, that is k+3.

Now we have an inequation to determine k against n: $\frac{(k-2)(k+1)}{2}+k+3\le n$

$k^2+k\le 2n-4$

With n sufficiently large compared to k, Alice always wins for any value of k that satisfies the inequation. Otherwise Bob always wins.

For example, if n=20 then Alice wins for k up to 5. However if k is greater than 5, then Bob wins. Another example: $n=500: k\le31 \Rightarrow$ Alice wins

For Alice to win she needs to play k+2 steps.