Javascript required
Skip to content Skip to sidebar Skip to footer

It is Possible to Solve the Nine dot Problem With One Straight Continuous Line

Forget to begin with that we have to find a path, but simply try covering the $9$ points by four infinte straight lines.

Call a line covering $n$ points an $n$-line. Since four lines covering only $2$ points each can never cover $9$ points a solution has at least one $3$-line in it. When identifying rotations and reflections we have exactly three distinct types of $3$-lines:

enter image description here

No parallel $3$-lines

It is not possible to have a solution involving parallel $3$-lines. For instance if we have the following situation:

enter image description here

When the two blue $3$-lines shown above have been placed we have to cover the remaining three points by two lines. So at least one line must cover more than one point which implies that the dashed grey line has to be added. But three parallel lines are clearly impossible, since it takes two additional linear moves to visit and travel along all three, but we only have one line left!

Ruling out type 3

With the above we can rule out type 3 being a part of any solution: We cannot have any line parallel to the initial $3$-line by the above argument. This actually means that each of the remaining three lines has to cover exactly $2$ of the remaining $6$ points each. Also we can only have one line orthogonal to the $3$-line for otherwise we would again have parallel $3$-lines (in the orthogonal direction).

So we have to have two lines passing through $2$ of the remaining $6$ points each that are not parallel nor orthogonal to the initial $3$-line of type 3. When symmetries are considered, this gives essentially two setups to consider. The first one is:

enter image description here

which clearly does not hold a solution since the lines only intersect at one point so it takes far more than four linear moves to travel since you would have to return to this intersection time and again in any path traversing parts of all of these lines. The other setup to consider is:

enter image description here

One way of seing why the above holds no solution is, that some of the lines are only intersected in ways having some of their points lying to both sides of the point of intersection. This makes it impossible to go through all points on any of these without visiting that line twice or reversing direction at some point.

Ruling out exclusive type 1 or 2

If we start from type 1 and do not allow type 2 and already know that type 3 must be ruled out and that no line parallel to the initial $3$-line is allowed, we see that this means that a line that passes the center point of the $9$ point pattern can pass no other point it the pattern as that would lead to one of the situations just mentioned. But with a line that only passes through the center the remaining two lines must covers $5$ points, so one of the lines must cover the $3$ points that are parallel to the initial $3$-line which again leads to a paralel $3$-lines contradiction.

If we start from type 2 and do not allow the other two types, there is essentially only one setup not already covered to consider:

enter image description here

which is another setup having three parallel lines. By previous arguments three distinct parallel lines can never be part of any solution.

The unique solution (type 1 + type 2)

By inclusion-exclusion any solution must involve type 1 and type 2 at the same time. So the situation looks like this to begin with:

enter image description here

and since we already know that we are not allowed to add a line parallel to the $3$-line of type 1 there are only two ways to complete the above setup. One way is like this:

enter image description here

and we see how the $3$-line of type 1 is the only line connecting to the other three lines to one side of their points. The other three lines divide each other in parts having points on each side. So all three other lines must be connected to the $3$-line of type 1 in a given solution. This is impossible since each line can only be connected to two other lines in a path that does not travel along any line twice.

So finally this leaves us with the well known solution as essentially the only possibility when considering rotations and reflections.

gellatlysteranded.blogspot.com

Source: https://math.stackexchange.com/questions/565942/how-to-prove-the-number-of-solutions-to-nine-dots-puzzle