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 question I am asking has basically already been asked. Please see this MSE thread. There are a few questions brought up on that thread, and a smaller number were answered. The reason I am asking this question is that I want to focus explicitly on one of the unanswered parts:

Does there exist $n$, and $r<2n-2$, such that the $n\times n$ square grid can be connected with an unbroken path of $r$ straight lines?

Notice that $2n-1$ is the trivial solution. This is obtained by either spiralling towards the center, or by zig-zagging up and down. On the other MSE thread, I posted an answer showing $2n-2$ was possible for $n\geq 3$. (this is obtained by reducing to the $3\times 3$ case) I felt $2n-2$ should be optimal, but I couldn't think of a proof. (Also, it is not necessarily clear that for a 100 billion by 100 billion grid you can't use some kind of cleverness to eliminate one single line)

This has been bothering me since I saw it, and I would like to know if anyone has any ideas.

Thanks,

Edit: This is regarding an question/answer I received: Not only are 45 degree lines allowed, but lines in any direction. Naturally 0,45,90 seem like the best since those angles will intersect the most lattice points, and we ask ourselves "Will any optimal solution consist only of lines at these angles?". The answer is a definite no. Consider the following solution to the $10\times 10$ grid which uses 18 lines (so $2n-2$, i.e. currently optimal). Also there is this solution to the $8\times 8 $ grid using 14 lines.

Interestingly, this solution to the $10\times 10 $ generalizes to give another $2n-2$ line solution to the $n\times n$ grid when $n$ is even.

(I found this $8\times8$ and $10\times 10$ solution on a link posted by user3123 on the other question page. Specifically it was this link.)

share|improve this question

2 Answers 2

up vote 19 down vote accepted
+50

I believe this is a proof that you can't do better than $2n-2$:

Let $m$ be the number of horizontal and vertical lines in the path. Then, since there are $2n$ rows and columns, there are $2n-m$ rows and columns that don't contain a line along their length; say, $k$ rows and $l$ columns with $k+l=2n-m$. Imagine the grid points where these rows and columns intersect taken out of the grid and arranged in a rectangle of $k$ rows and $l$ columns. Since each of the points in this rectangle is both in a row and in a column that doesn't contain a line along its length, each of these points must be on some line that is neither horizontal nor vertical.

If $k=0$, then we have $n$ horizontal lines, and these must be connected by at least $n-1$ non-horizontal lines to make an unbroken path. Thus, for $k=0$ there must be $2n-1$ lines, so we can exclude that case.

If $k=1$, then we have $n-1$ horizontal lines, and we have to connect each of the $n$ grid points on the remaining row with a separate line, so again we must have at least $2n-1$ lines, so we can exclude that case.

Thus $k\ge2$, and likewise $l\ge2$. Thus we may consider the border of the rectangle, i.e. the two outermost rows and the two outermost columns. This border consists of $2k+2l-4=2(k+l-2)=2(2n-m-2)$ grid points. Every line that doesn't run along the length of one of these rows or columns can hit at most two of these points. That means there must be at least $2n-m-2$ lines in addition to the $m$ horizontal and vertical lines, for a total of $2n-2$.

P.S.: You can check this out in the $8\times8$ and $10\times10$ solutions linked to in the question -- in each case, the "rectangle" constructed in the proof is actually a contiguous rectangle in the grid (with $k=6$, $l=8$ and $k=10$, $l=2$, respectively), and you can see that the path optimally connects two points of that rectangle's border with each line that isn't horizontal or vertical.

share|improve this answer
    
Notational confusion, sorry, it is clearer upon rereading. My feeling is that your proof is correct. I will come back and read it again tonight or tomorrow to make sure. Thanks for the answer! (+1) –  Eric Naslund Feb 24 '11 at 20:54
    
Ok so this is definitely correct. I like the proof!! Thanks again for your help! I would award the bounty and such but apparently there is some sort of minimum time limit to do so. (The bounty was put on 22 hours ago) –  Eric Naslund Feb 25 '11 at 6:05
    
@Eric Naslund: You're welcome! No hurry about the bounty -- it will draw more attention to the question while it's there :-) –  joriki Feb 25 '11 at 9:35

Since I have to explain Joriki's solution to all the people I mentioned the problem to, I decided to provide a typed solution written up in my own words. Although there are no new ideas, there doesn't seem to be any good reason not to just share it anyway:

Lemma Let $a\geq 1$, $b\geq 1$. Given an $a\times b$ rectangular grid, without using horizontal or vertical lines it requires at least $a+b-2$ lines to cover all the points. (Here the path need not be connected)

proof: Consider the exterior of the grid. If $a\geq 2$ and $b\geq 2$ then each diagonal line can cover at most two points, but there are $2a+2b-4$ points that must be covered. If $b=1$ then each diagonal line covers at most 1 point, and hence we need $a=a+b-1>a+b-2$ lines. Similarly if $a=1$.

Given a solution to the $n\times n$ grid, let $h$ be the number of horizontal lines, and $v$ be the number of vertical lines used. If $h=n$, we must have at least $2n-1$ lines since it will take at least $n-1$ lines to connect all of these horizontal parts. Similarly for $v=n$.

Now, let $v<n$, $h<n$ and remove all the rows and columns where a horizontal or vertical line appears. Then we have an $n-h\times n-v$ grid left over, which by the lemma requires at least $(n-h)+(n-v)-2=2n-2-h-v$ lines to cover. Since we already used $h+v$ lines, the entire grid requires $(h+v)+(2n-2-h-v)=2n-2$ lines, and the proof is complete.

share|improve this answer
    
I think you need to say something about the case $a=1$ (or $b=1$), since in this case the "border" of the rectangle contains not $2a+2b-4$ but just $a$ (or $b$) points, and you can cover not two bust just one of them with each line. You can either argue like I did, or, which is a bit simpler, just argue that to cover $a$ points with one line each you need $a>a-1=a+b-2$ lines so you're better off than in the case $a\ge2$. But I think you do have to mention that this case is different. –  joriki Feb 26 '11 at 23:06
    
@joriki: Thanks for the advice, the addition of those cases is definitely needed. I added the required stuff into the lemma, so it should be fixed now. –  Eric Naslund Feb 26 '11 at 23:24

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.