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?
Note: This has essentially already been asked – see this MSE thread. I am posting this question because I wanted to explicitly focus on one of the unanswered parts.
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.
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.)
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.
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.