8
$\begingroup$

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

enter image description here

$\endgroup$
  • $\begingroup$ Hmm.. I have a difficulty to choose which tag should be used in this puzzle: game or game-theory. $\endgroup$ – athin May 27 at 9:49
  • $\begingroup$ In your example, X could have won this game by playing between the two Xs on step 6, so this strategy fails for O. $\endgroup$ – Trenin May 27 at 11:44
  • $\begingroup$ O's move in step 5 needs to be between the two Xs. That way, X cannot win on the next move, but O has two lines of victory and X cannot block both. $\endgroup$ – Trenin May 27 at 11:47
  • 2
    $\begingroup$ I misread the question; I assumed X was trying to win as well, but the game is not the same for both players. X is simply trying to block you indefinitely and O is trying to win. $\endgroup$ – Trenin May 27 at 11:49
7
$\begingroup$

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]$

enter image description here

$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}]$

enter image description here

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}]$

enter image description here

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

$\endgroup$
  • $\begingroup$ Yep! For $N=4$, it is possible to win the game in at most $13$ steps like this :D $\endgroup$ – athin May 27 at 13:04
  • $\begingroup$ I just see the edited version, I'm very impressed with the answer for generalizing $N$ :) $\endgroup$ – athin May 27 at 14:54
  • $\begingroup$ @athin Thanks! I think it is fool proof, but could be convinced there is a better strategy for $X$. Off the top of my head, I don't see it. $\endgroup$ – Trenin May 27 at 14:58
  • $\begingroup$ One question, in $N = 5$, what if $X$ tries to put the point on the intersections of each pairs of $3$-in-a-row (which are from different section)? $\endgroup$ – athin May 27 at 15:07
  • $\begingroup$ @athin The key point is that when making the 3 in a row, it is guaranteed to be unblocked based on the strategy. If X does not follow the strategy above, we will have multiple choices for the 3 in a row, and can then choose one which has not been foiled by X. Thus, we will have different segments to choose from and X will still not be able to stop us. $\endgroup$ – Trenin May 27 at 15:28
5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ The later stages of your argument aren't very clear to me. E.g., how do you get from 2x-3 to 2x-4, exactly? How many moves does it take and have you taken into account the fact that your opponent gets to make that many moves too? I think this could use some clarification... $\endgroup$ – Gareth McCaughan May 26 at 17:24
  • 3
    $\begingroup$ Precisely as Gareth said. Also, it's not always the case that the $n$-th dot you put make $n-1$ new lines. If you tried to make $3$ in-a-line for example, the number of new lines will be fewer; and how about more in-a-line. Also, the judge may not only block $1$ line, it can be more, for example the intersection of $2$ lines will block at least $2$. $\endgroup$ – athin May 26 at 20:17
1
$\begingroup$

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).
$\endgroup$
  • $\begingroup$ Very impressive, this is a very clear solution! $\endgroup$ – athin May 29 at 2:19

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.