8
$\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 $4$ points. They're free to mark their points anywhere as long as they don't overwrite a previous one. If any three points Alice has placed form the vertices of a unit equilateral triangle, she wins.

Find a winning strategy for Alice.

$\endgroup$
4
  • $\begingroup$ by unit equilateral triangle do you mean 1x1x1? $\endgroup$
    – SteveV
    Nov 27 '21 at 22:00
  • $\begingroup$ This one looks much better than the previous one, as it's a clear statement that a winning strategy exists! $\endgroup$
    – WhatsUp
    Nov 27 '21 at 22:57
  • $\begingroup$ @SteveV Yes, it's a triangle with side length 1. $\endgroup$
    – Eric
    Nov 28 '21 at 0:45
  • 1
    $\begingroup$ @WhatsUp I don't think that comparison is fair. I asked different questions in the two puzzles. Besides, loopywalt already showed how winning strategy exists for N=1 in the comment for the previous one. $\endgroup$
    – Eric
    Nov 28 '21 at 0:51
3
$\begingroup$

Sketch:

The general strategy is to overwhelm Bob combinatorially with simultaneous threats. To keep our argument simple we will assume that all our constructions (and all Bob's counter measures!) below yield distinct points. We can expect this to be the case when "free" points, i.e. points which are not constructed from other points are chosen "properly randomly".

By abuse of language let's refer to points "with no special relationship except what is explicitly stated" as points in general position. One could probably whip up a formal definition by requiring something along the lines that there be no algebraic relationship between coordinates, but I won't attempt to do so. Intuitively, what I mean is stuff like no three points are collinear or form a special angle like 90° or 60° or no two points lie a "clean" distance (like 1, or 1/2 or even sqrt(3)) apart. I won't say it all the time but unless stated otherwise we'll assume points we choose to be in general position.

One last remark before getting our hands dirty: This solution is neither optimal nor unique it's just one way of getting the job done.

Step 1:

Choose a unit circle and mark 15 points on it. There is nothing Bob can do about this. Call the set of these points P and the points P1,P2,...

Step 2:

Pick a small (length <<1) offset vector and mark points at that offset to as many points in P as Bob will allow, at least 20%. Repeat this procedure a huge number of times.

Step 3:

Find offsets O1 and O2 and Points P1,P2,P3 such that the six points P1+O1,...,P3+O2 are all marked (call this an OPset) and Bob did not yet have the chance to react to them in any way. (We'll do the numbers to show that such an OPset exist in a moment). Now for each pair PnO1,PnO2 mark the centre of one of the two unit circles passing through the pair. It doesn't matter which one but it must be "the same" for each pair. I.e. if the centres are NW and SE of each pair, say, we have to choose either NW each time or SE each time. (Note that Bob cannot interfere because he's busy parrying the four direct threats arising from us creating two unit-distance pairs simultaneously.) As the three new points are shifts of P1,P2,P3 by the same vector they lie on a unit circle. We use the next move to mark its centre. As this creates three new unit-distance pairs Bob will be forced to concede.

The numbers:

It suffices to show that the number of pairs of offsets that occur in an OPset grows supra-linearly in the number of offsets O because then Bob will eventually have to let an offset pair unanswered. (Remember that we were careful to put everything in general position, so Bob will have no chance to react to two pairs with a single mark.) The number of all pairs grows, of course, quadratically. How about the subset of those that will make it into an OPset? Split the offsets into 15-choose-3 groups based on which Ps they occur with. (If an offset belongs to muliple groups choose randomly between them.) Pick the largest group. The number of pairs grows quadratically in this group's size and therefore also quadratically in the number of offsets.

Thanks @Joseph Sible-Reinstate Monica for this picture and description for step 3. The circle from step 1 is bottom left, the circle delivering the "killing blow" is in the centre):

enter image description here
Once you've found your OPset, mark B. Bob will be forced to mark T and V to protect them from B and P1'O1, and U and W to protect them from B and P1'O2. Mark C. Bob will similarly mark P, R, Q, and S. Mark D. Bob will similarly mark L, N, M, and O. Mark E. Bob now needs to mark F and G to protect them from B and E, H and K to protect them from C and E, and I and J to protect them from D and E. But he can only mark four of those, so mark one of the two that he doesn't, and you'll immediately win.

$\endgroup$
7
  • 1
    $\begingroup$ I made a visual aid for your step 3 in GeoGebra: i.stack.imgur.com/vE1u1.png I can upload the .ggb file somewhere too if you want it. It goes like this (feel free to edit into your answer if you want): $\endgroup$ Nov 30 '21 at 4:52
  • $\begingroup$ Once you've found your OPset, mark B. Bob will be forced to mark T and V to protect them from B and P1'O1, and U and W to protect them from B and P1'O2. Mark C. Bob will similarly mark P, R, Q, and S. Mark D. Bob will similarly mark L, N, M, and O. Mark E. Bob now needs to mark F and G to protect them from B and E, H and K to protect them from C and E, and I and J to protect them from D and E. But he can only mark four of those, so mark one of the two that he doesn't, and you'll immediately win. $\endgroup$ Nov 30 '21 at 4:52
  • $\begingroup$ @JosephSible-ReinstateMonica Thank you very much! I've incorporated them. $\endgroup$
    – loopy walt
    Nov 30 '21 at 5:12
  • $\begingroup$ "It suffices to show that the number of pairs of offsets that occur in an OPset grows supra-linearly in the number of offsets ... " If we substitute "pairs" with "triples" or "quadruples" etc. the supra-linear growth still holds and with slight modifications we prove Alice wins against N-points Bob for any natural number N. Is that right? $\endgroup$
    – Eric
    Nov 30 '21 at 8:17
  • 1
    $\begingroup$ @Eric if they all on the same circle (one circle per Pn) then all Bob needs to do is mark the centre of that circle to shut us down. If we try to create multiple circles then there is no (at least no obvious) way how to make sure that whenever we mark the third point on a circle we do this for mulitple circles at the same time. And otherwise Bob just marks the centre of each circle as soon as we have drawn three points on its circumference. $\endgroup$
    – loopy walt
    Nov 30 '21 at 9:49
0
$\begingroup$

To start, here's a strategy to win against 2 dots per turn.

Start by playing the corners of a unit square. (Each turn, she has two winning moves and at least one next corner. Bob can't stop all of them. After her fourth move, she has four threats to win on her fifth move.)

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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