15
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ A wins with $N = 0$ and B wins with $N = \aleph_0$. Thus the answer is $0 + O(\aleph)$. $\endgroup$
    – WhatsUp
    Nov 24, 2021 at 19:14
  • 2
    $\begingroup$ I can't seem to find any way for Alice to win if N >= 1. Are we misunderstanding something, or is that intentional/the solution? $\endgroup$
    – Surma
    Nov 24, 2021 at 19:37
  • 1
    $\begingroup$ @LOTGP If you look at other questions from the OP, then you'll see that the OP usually don't have an answer to them. There is no intentional solution, and sometimes (many times) you may wonder whether there is actually a solution. Thus the question should be interpreted literally as a "question": the OP is simply interested to see how much research you can do with this problem. $\endgroup$
    – WhatsUp
    Nov 24, 2021 at 19:58
  • 2
    $\begingroup$ @LOTGP Note that they are not playing on a grid, so moves can be placed at non-integer coordinates, and the squares can be at any orientation. $\endgroup$ Nov 24, 2021 at 21:37
  • 4
    $\begingroup$ @LOTGP Alice win for N=1: As soon as Alice gets three in a row with the neighbouring grid rows unoccupied she wins because she threatens two "T" shapes at the same time. Three in a row she can force by making a regular unit triangle with her first three moves. As she can place her second mark to render Bob's first off-grid for the three relvant grids Bob can only have placed two useful marks before Alice's fourth move and she has three grids to choose from. $\endgroup$
    – loopy walt
    Nov 25, 2021 at 1:11

2 Answers 2

11
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ "Now one notes that X has exactly (2N+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 (2N+1−λ)2(r+1)(r+1) copies of the unit square (λ is some constant)." Should the N's in these two equations instead be Ms? $\endgroup$ Nov 21, 2022 at 17:57
  • $\begingroup$ @GoblinGuide yep, thanks for pointing it out! Fixed. $\endgroup$
    – Ankoganit
    Nov 21, 2022 at 20:00
-4
$\begingroup$

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.

$\endgroup$
15
  • $\begingroup$ What was the downvote for? Accused of cheating again? $\endgroup$
    – Nautilus
    Oct 24, 2022 at 21:31
  • $\begingroup$ It was not me, but I have no idea what you try to say. There is no point "orthogonally next to [a point]" in $\mathbb{R^2}$. $\endgroup$
    – Florian F
    Oct 24, 2022 at 21:49
  • $\begingroup$ Also, take a look at the comments under the question. Loopy Walt's has a winning strategy for Alice for N=1. $\endgroup$ Oct 24, 2022 at 21:52
  • $\begingroup$ Sorry for my ignorance, but I just thought a unit square in the question was supposed to be a "square" of 2x2 points, so I just treated points as cells. My answer was apparently based on a wrong premise all along. $\endgroup$
    – Nautilus
    Oct 24, 2022 at 22:27
  • 2
    $\begingroup$ The point of having unit square is that the size of the square Alice is required to create is fixed at the beginning of the game. Also, can you explain more what you mean by "If Alice requires x cells to win on this grid, she requires about 3x to win on an 2n x 2n grid"? $\endgroup$
    – justhalf
    Nov 21, 2022 at 2:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.