Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
Alice and Bob take turns to mark points in $\mathbb{R^2}$ (i.e. infinite 2D plane). Alice can only mark $1$ point on her turn, while Bob can mark $N$. They're free to mark their points anywhere as long as they don't overwrite a previous one. If any four points Alice has placed form the vertices of a unit square, she wins.
Question: How large can $N$ be for the game to be still winning for Alice?
Spoiler alert: I won't bother spoiler tagging the following wall of text: proceed at your own risk.
The answer is that Alice wins for any finite $N$. In fact, the more general version holds:
Let $S$ be a finite set of points on $\mathbb R^2$. Alice and Bob take turns marking points. Alice can only mark a point on her turn, while Bob can mark $N$ points. They're free to mark their points anywhere as long as they don't overwrite a previous one. Then Alice can produce a congruent copy of $S$ within her marked points in finitely many moves.
This is a complex theorem in combinatorial game theory, and a complete proof can be found in József Beck's Combinatorial Games: Tic-Tac-Toe Theory (where the above result occurs as Theorem 2.3). The full argument is fairly involved: I'll briefly sketch the main ideas in the proof.
Let's work with the unit square case for simplicity. We'll start with the case $N=1$ and then indicate how this generalizes to larger values of $N$. The set of vertices of a unit square can be represented as the set of vectors $S=\{0,v_1,v_2,v_3=v_1+v_2\}$ where $v_1$ and $v_2$ are the unit vectors along the two coordinate axes. The first step is to pick a large number of angles $\theta_1,\dots,\theta_r$ so that the vectors $v_{i,j}=v_i$ rotated by $\theta_j$ are all linearly independent over $\mathbb Q$ (for those unfamiliar with linear algebra, this corresponds to taking a lot of rotated copies of the unit squares, and choosing the angles in a way so that the only non-trivial "additive" relations between the vectors come from the obvious ones: $v_3=v_1+v_2$, and similar relations hold for each of the rotated copies, but no new relations pop up). Note that it is possible to pick such angles because of cardinality reasons: linear dependence over rational "rule out" countably many choices of angles, but there are uncountably many options.
The next step is to construct a humongous "lattice" made out of these rotated copies that will be "rich" in copies of the unit square. Specifically, we choose the set $$X(r,M)=\left\{\left.\sum_{i=0}^r (a_iv_{1,i}+b_iv_{2,i})\right| a_i,b_i \text{ are integers in the range }[-M,M]\right\}.$$Here $M$ is a large integer suitably chosen. Essentially, this set contains a lot of rational linear combinations of the rotated copies of $v_1$ and $v_2$, so the hope is that it will contain a lot of copies of the unit square.
Now one notes that $X$ has exactly $(2M+1)^{2(r+1)}$ points (precisely the number of ways to choose the rational coordinates: linear independence guarantees no two choices lead to the same point). Further, one can count that this has at least $(2M+1-\lambda)^{2(r+1)}(r+1)$ copies of the unit square ($\lambda$ is some constant). Now let Alice always play on this set and try to form one of these copies of the unit square. If Bob plays outside this set, that's to our advantage, so we can assume both players play on this set.
Thus we have reduced our problem to something about finite sets: say we have a large but finite set $X$, and certain subsets of $X$ of size $4$ are "winning". If two players alternately occupy elements of $X$, then we want to show that the first player can always occupy a winning set as long as there are "sufficiently many" winning sets.
Fortunately, there is a handy theorem that proves exactly this: see https://en.wikipedia.org/wiki/Maker-Breaker_game#A_winning_condition_for_Maker . It says that the first player wins as long as there are more than $2d_2|X|$ winning sets. (This $d_2$ is the so-called max-pair degree of the corresponding "hypergraph". I won't bother defining any of those words here, just remark that it's easy to estimate $d_2$ in our case; in fact, it's at most $6$, and, uh, things work out.) An application of this theorem immediately solves our problem; if we make $r$ and $M$ big, our set does end up having sufficiently many winning sets.
Now for the general case where $N>1$, one uses a biased version of the above result: we still use the same set $X=X(r,M)$, but Bob is now allowed to occupy $N$ elements per move. Simplified for our specific case, this biased version tells us that Alice still wins as long as there are more than $$N^2(1+N)d_2|X|$$ winning sets (Theorem 2.2 in Beck). Thus the same strategy takes care of the general case too.
Alice can always find a way to win:
If there's a minimum average number (rational or irrational) of Bob's points per turn preventing Alice from winning on an infinite plane, let there be a rectangular area where Alice's dots are overrepresented. Alice can win in this area, so she can win the entire game that way. She's bound to be overrepresented in some areas if she ignores others, so she wins.
