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.

I stumbled across the problem of connecting the points on a $n, n$ grid with a minimal amount of straight lines without lifting the pen.

For $n=1, n=2$ it is trivial. For $n=3$ you can find the solution with a bit trial and error (I will leave this to the reader as it is a fun to do, you can do it with 4 lines). I found one possible solution for a $4,4$ grid and animated it, it uses 6 lines and is probably optimal (will hopefully help you to understand the problem better, the path doesn't have to be closed like in the animation, open ends are allowed!):

Problem

Now my question is, for higher $n$, is there a way to get the amount of minimal lines to use and does an algorithm exist to find a actual solution? I think its quite hard to model the "straight lines" with graph theory.

Edit: Reading Erics excellent answer I found the following website: http://www.mathpuzzle.com/dots.html that also gives an algorithm to connect the points in $2n-2$ steps, solutions up to $10,10$ and mentions:

Toshi Kato conjectures: On $(2N+1)x(2N+1)$ grid, $N \geq 2$, Using $4N$ continuous lines, and not lifting your pencil from the paper, can go through all the dots of a $(2N+1)x(2N+1)$ grid, ending at the same place started. But must visit at least one dot twice in the route.

On $(2N)x(2N)$ grid, $N \geq 2$, Using $4N-2$ continuous lines, and not lifting your pencil from the paper, can go through all the dots of a $(2N)x(2N)$ grid, ending at the same place started. And can visit each dots just once.

It seems to be an open problem to show that $2n-2$ is optimal.

Also I found the following page with a proof that in the $3,3$ grid there cannot be $2$ parallel lines: http://fahim-patel.blogspot.com/2011/01/proof.html I think it might be interesting for coming up with a proof that $2n-2$ is optimal (however maybe there is no such proof, as we only saw solutions for very small $n$, for bigger $n$ there might be some developments we don't know about).

share|improve this question
    
You didn't have to make it closed! You could have started and/or ended at points in the grid. But it's a nice animation :-) –  TonyK Feb 13 '11 at 17:58
    
I know, I noticed it later when uploading it and therefore wrote a warning to avoid confusion. –  Listing Feb 13 '11 at 18:03
    
I have nothing useful to add but I will say that the solution will need some thinking outside the box - en.wikipedia.org/wiki/Thinking_outside_the_box#Nine_dots_puzzle –  Dinesh Feb 13 '11 at 18:31
    
@user3123: Just in case you didn't see it, Joriki posted a complete solution on the other page I made: math.stackexchange.com/questions/23193/… –  Eric Naslund Feb 26 '11 at 22:51
add comment

2 Answers

up vote 4 down vote accepted

Interesting question. In what follows consider the $n\times n$ square grid. Notice that the trivial solution obtained by following a square spiral towards the center starting from an outside corner yields a solution with $2n-1$ lines.
To see why, notice that 2 lines reduces the grid to a $(n-1)\times (n-1)$ grid, and since the $1\times 1$ grid requires only 1 line, induction yields $2n-1$ lines.

Can we do better? Based on the posts in the forum and my own attempts, I believe the answer is that $2n-2$ lines is optimal. Showing this is possible is again easy. Start at a corner, and spiral towards the center until there is only a $3\times 3$ grid remaining. Recall from above that 2 lines in the spiral will reduce the grid by a dimension, so thus far we will have used $2\cdot (n-3)=2n-6$ lines. On the last line, end it so that we are in a position to go through the diagonal of the $3\times 3 $ grid. Since the $3\times 3$ grid has a solution with $4$ lines starting diagonally from a corner we have found a solution to the $n\times n$ grid using only $2n-2$ lines.

Now, the question remains, is $2n-2$ optimal? The more I think about it, the more I believe it, but a proof does not leap into mind. I will think more.

Edit: Of course $n=1,2$ are exceptions, and required $2n-1$ lines. The method I presented can be modified slightly to produce a closed path. All that must be changed is the way the final $3\times 3$ grid is traversed, and perhaps moving the starting position of the first line to a spot slightly outside of the original $n\times n$ grid. In other words the conjecture Toshi Kato is true.

Edit 2: For a proof that $2n-2$ is optimal, see Joriki's answer to this question Not lifting your pen on the $n\times n$ grid.

share|improve this answer
    
Very nice, knowing this I searched some more on the web and discovered a website mentioning exactly what you did (maybe the algorithms are a bit different). See my updated question. –  Listing Feb 14 '11 at 9:07
add comment

There is some discussion of this problem here: http://www.tek-tips.com/viewthread.cfm?qid=1370890&page=2

share|improve this answer
    
Nice find. Still it doesn't seem that they have made much more progress than we. Except they fund more solutions for slightly bigger $n$ (I think the heighest $n=8$) by trial and error. –  Listing Feb 13 '11 at 17:59
add comment

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.