Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The aim of the Nine Dots Puzzle is to draw a path connecting 9 dots arranged in a $3\times 3$ grid using 4 continuous straight lines, never lifting the pen/pencil from the piece of paper. A solution is displayed below (spoiler alert):

Nine Dots Solution

In the Wikipedia page linked above, the solution is labeled as "One of many solutions to the puzzle..." However, this page claims it's the unique solution to the puzzle. In my cursory exploration of the puzzle, all the solutions I have found are either some rotation of the above solution or the same solution with a different starting point. For example, the following solution:

enter image description here

is just a $90\,^{\circ}$ rotation of the first.

Alternatively, if we number the dots like so:

enter image description here

the first solution can be generated using the paths $$9\rightarrow 5\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 6\rightarrow 8\rightarrow 7\rightarrow 4\rightarrow 1 \tag{1}\label{a} $$ and $$9\rightarrow 5\rightarrow 1\rightarrow 4\rightarrow 7\rightarrow 8\rightarrow 6\rightarrow 3\rightarrow 2\rightarrow 1 \tag{2}\label{b} $$ which are just reflections about $y=-x$ (if the 1-dot is the origin) of each other.

Another path (and its reflection) which generates the first solution is: $$1\rightarrow 2\rightarrow 3\rightarrow 6\rightarrow 8\rightarrow 7\rightarrow 4\rightarrow 1\rightarrow 5\rightarrow 9 \tag{3}\label{c}$$

[Note that path $\eqref{c}$ is path $\eqref{a}$ with the first two elements reversed and moved to the end of the path]

My initial thought is that, if the first solution is indeed the unique solution, then the Wikipedia article may be counting all the rotations, reflections, and alternate paths as different solutions to the puzzle because I can't think of another solution.

Question:

Treat solutions which are rotations or reflections of each other or solutions which generate the same "picture" despite their exact path as equivalent solutions. How many solutions are there and how would you prove (other than through brute force) that the puzzle has only $K$ solution(s)?

This question may require a more rigorous definition of "same picture" but I'm unable to think of a better way of describing it.

share|improve this question
3  
This puzzle was presented in my psychology class to show functional fixedness, and a second solution was presented, which would be fine in the context of psychology, but does not meet the requirements if one considers points to be dimensionless quantities and restricts the lines to being co-planar, as we do in the mathematical version of the puzzle. Wikipedia might have been talking about the psychology solution, which is why I agree with you that there are no other solutions, but I can not provide a proof of it. –  Juan Sebastian Lozano Muñoz Nov 13 '13 at 21:58
    
@Juan: I can't believe that your "second solution" was seriously advocated as a solution to this problem! –  TonyK Nov 13 '13 at 22:11
    
@TonyK: It can actually be found along with other "false solutions" in the link captioned by "this page" in the question text. They present it as "creative solutions" that are less mathematical. –  String Nov 13 '13 at 22:26

1 Answer 1

up vote 6 down vote accepted
+50

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.

share|improve this answer
    
I am just now really diving into your solution as your images don't load correctly on my work computer. Great work and nice write-up! –  Mike Wierzbicki Feb 5 at 3:27
    
@MikeWierzbicki: Thank you for your appreciation of my work! I am sorry to hear that the images do not work properly. Without them my write-up must be extremely challenging to follow! –  String Feb 5 at 9:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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