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 $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.
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):
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.
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.)
