Four-in-a-line Puzzle

Question

_{Disclaimer: This is an open-problem, I don't have a complete solution for this puzzle yet.}

---

We are playing a $2$-player game: you as a challenger and me as a judge. Initially, there is an empty infinite $2$-dimensional plane.

Alternately starting from you, put a single point. Your points will be denoted as $O$-points and mine will be $X$-points. The point we put can be anywhere — it may have Real coordinate — as long as it is not overlapping with any previous points.

You will win if and only if at some point of time, you can draw a line segment passing $N$ number of $O$-points without passing any $X$-points. Thus, you will lose if and only if I can make sure you can't reach your goal at any point of time.

Questions:

1. If $N = 4$, can you win this game?
2. If $N = 5$, can you win this game?
3. Can you win this game for any $N$? If yes, then what is the strategy? If no, then what is the smallest number of $N$ which is impossible for you to win?

This is an example of the game for $N = 3$:

Answer 1

First of all, lets present a strategy for $N=4$.

$N=4$

$O$ can win in 7 moves (13 total).

To start, the first two moves are arbitrary due to rotation and stretching, so let us assume we have the following;
1. $O_1=[0,0]$
2. $X_1=[-1,-1]$

Now, $O$ will pick a line not on the $O_1,X_1$ line and place another point. $X$, meanwhile, should place a point between these two since not doing so give $O$ more options. The placement for $X$ is mostly arbitrary so long as it is between $O$s points.
3. $O_2=[2,0]$
4. $X_2=[1,0]$

At this point, $O$ will start on a different line, 90 degrees from the first;
5. $O_3=[0,2]$

$X$ now has two sets of 2 to worry about; $\{O_1, O_3\}$, and $\{O_2, O_3\}$. It doesn't matter which one $X$ blocks;
6. $X_3=[0,1]$ or $X_3=[1,1]$

It doesn't matter which $X$ chooses, so long as one segment is left.
7. $O_4=[1,2]$

If $X_3=[0,1]$, then $\{O_1,O_4\}$ and $\{O_2,O_3\}$ are two line segments each with 2 $O$s. If $X_3=[1,1]$, then the two line segments are $\{O_1,O_4\}$ and $\{O_1,O_3\}$. $X$ should probably take the intersection of these two segments since it blocks both. For simplicity, I will assume $X_3=[0,1]$, the the argument works either way;
8. $X_4=[\frac{2}{3}, \frac{4}{3}]$

Now $O$ can take a third point on the top line that has not been blocked. $X$ must then block it since $O$ now has 3 in a row and can win on the next turn if not blocked.
9. $O_5=[2,2]$
10. $X_5=[\frac{1}{2},2]$

At this point, there are two segments, each with two points which are not yet blocked. These are $\{O_1,O_5\}$ and $\{O_2,O_4\}$. $O$ simply takes the intersection of these points.
11. $O_6=[\frac{4}{3},\frac{4}{3}]$

Now $O$ has two line segments, each with 3 points. It doesn't matter which segment $X$ blocks, $O$ will win on the other since $X$ cannot block both.

$N=5$

As we saw previously, we can in 12 moves (six moves by $O$), get an unblocked line with 3 in a row. Lets say we play out this strategy in 3 sections of the real plane, roughly forming a triangle. We will make one move in each section round robin style.

$X$ can either concentrate on eliminating all possibilities in one section, or follow us to each section we move in. If $X$ concentrates on one section, then in two of our sections we will get 3 in a row easily using the above strategy since there is less opposition to our moves.

If $X$ instead chose to follow our round robin strategy in each section, then we would get 3 in a row in all 3 sections using the above strategy. Either way, at least two of them will have 3 in a row.

So long as we didn't make these lines parallel, we can choose a 4th point on the intersection of these lines. This will give us 2 lines of 4 in a row with no blockers. On our next move, we can complete a 5 in a row.

General solution for all $N$

We can simply repeat the $N=5$ strategy for a number of sections on the ever growing real plane. Again, $X$ will be forced to either follow our round robin strategy, or commit to a section. Either way, we will eventually get 4 in a row in at least 2 sections. By placing a point in the intersection of these segments, we will have 2 sets of 5 in a row.

This strategy can be repeated, growing larger and larger each time to achieve all possible $N$.

Answer 2

I think you can

win even if you need to connect a kajillion dots.

Here's my reasoning:

Well, any two points can be connected by a line, right?

Then you can see that

When you put a point down, you can draw a line from that point to any other point you already put down. {important}

The challenge is that your opponent can block the connections with a point of their own.

But as you remember about

the birthday paradox

Because of the {important} knowledge above, you see that

you can connect lines to $n-1$ dots when you put the $nth$ dot down.

Making the equation

When you put the $nth$ dot, you have 1 + 2 + 3 + ... + (n-1) connections.

Let's do 4. By putting

101 dots down, you have 5050 connections!

{Note: In this step don't put any dots in 3 in a row.}

That's a lot of connections you can make with lines.

Since your opponent has only put

101 blocking dots down

you can

make a 3 in a row with 2 of the remaining connections you have by looking at 2 non-parallel connections. 2 non-parallel lines will connect, right?

Your opponent can't block both lines, so you got a 4 in a row!

The strategy for $x$ dots in a line is

put many many dots to make a kajillion connections. Maybe even Graham's number.

Then

make 3 in a row with $2x-3$ non-parallel connections.

Then

make 4 in a row with $2x-4$ non-parallel connections.

Eventually you

make 2879 in a row with $2x-2879$ non-parallel connections.

And then you make

$x$ in a row with $2x-x$ connections. (The hint there is that $2x-x=x$.)

So you can get infinity in a row! YAY!

-edit- Oops, yeah there was a mistake as @GarethMcHaugan said. You should look at @Trenin's solution instead.

Answer 3

I think @Trenin has nailed it. Here's a slightly different formulation where we prove it by induction.

1. We can get 1 point in a row with each of us playing the same number of moves ($m_1=1$) and one end free of other points.

2. Suppose we can get $k$ points in a row after we've each played $m_k$ moves with one end free of other points.

3. Required to show: that we can get $k+1$ points in a row after we've each played the same number of moves with one end free of other points.

   • Get $k$ in a row
   • Repeat this $k+1$ times ensuring that none of your lines is parallel
   • Extend your lines out to a new imaginary line and start putting points on the intersections (ensure that your new imaginary line goes through each extended line at a unique point).
   • Your opponent will need to put a point on the extended line or you have achieved your goal.
   • Once you've done this $k+1$ times, you have two lines with $k+1$ points (the final extension and the new one formed on the imaginary line). Your opponent can block one of them and you have achieved your goal.
   • It has taken you $(k+1)m_k+(k+1)$ moves. This gives you an upper bound on the number of moves it will take you (in fact there are better strategies at the lower levels which can reduce the number of moves required).