Intereting Posts

$AB$ is a chord of a circle $C$. Let there be another point $P$ on the circumference of the circle, optimize $PA.PB$ and $PA+PB$
Convergence of fixed point iteration for polynomial equations
Estimation of a combinatorial sum
How can LU factorization be used in non-square matrix?
Looking for insightful explanation as to why right inverse equals left inverse for square invertible matrices
Example about the Reduced cost in the Big-M method?
How to derive the Dirichlet-multinomial?
Limits and derivatives – two questions
What is the group structure of 3-adic group of the cubes of units?
showing a function defined from an integral is entire
Noncausal dynamical system
Count the number of topological sorts for poset (A|)?
Evaluate $\int_0^{\pi} e^{a\cos(t)}\cos(a\sin t)dt$
Turning higher spheres inside out
clarify the term “arithmetics” when talking about Gödel's incompleteness theorems

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.

- Matroids: Prove that for circuit $C$ and its cocircuit $C^*$: $|C \cap C^*| \neq 1$
- prove or supply counter example about graph
- How to justify unicyclic connected graphs formula?
- Infinite shortest paths in graphs
- Symmetric difference of cycles
- Reduction from Hamiltonian cycle to Hamiltonian path

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.)

- Showing ${1\over n}\sum|S_i|=O(\sqrt n)$ for $S_i\subset $, $|S_i\cap S_i|\le 1$ for $i\ne j$
- Existence of d-regular graphs
- Can the complete graph $K_9$, be 2-coloured with no blue $K_4$ or red triangles?
- Is there a name for relations with this property?
- Counting certain paths in a complete graph
- What is the probability that a random $n\times n$ bipartite graph has an isolated vertex?
- Proving bipartition in a connected planar graph
- Given two non-isomorphic graphs with the same number of edges, vertices and degree, what is the most efficient way of proving they are not isomorphic?

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.

- Show that $\int_0^1\ln(-\ln{x})\cdot{\mathrm dx\over 1+x^2}=-\sum\limits_{n=0}^\infty{1\over 2n+1}\cdot{2\pi\over e^{\pi(2n+1)}+1}$ and evaluate it
- How can I use Bessel's equation to solve the Lengthening Pendulum differential equation?
- Statistics: Bertrand's Box Paradox
- Construct a Borel set on R such that it intersect every open interval with non-zero non-“full” measure
- Combining symbols with symmetry
- Show that if $f$ has compact support, then its Fourier transform cannot have compact support unless $f=0$.
- Symmetric Difference Identity
- Complex Analysis Books
- analytic in open unit disk,corresponding to a bounded sequence and a bounded functional sequence
- pullback of density
- Prob. 4, Chap. 4 in Baby Rudin: A continuous image of a dense subset is dense in the range.
- $\int^\infty_0 \frac{\cos(x)}{\sqrt{x}}\,dx$ Evaluate using Fresnel Integrals
- “Mathematical Induction”
- How to show that a root of the equation $x (x+1)(x+2) … (x+2009) = c $ can have multiplicity at most 2?
- Sum of stars and bars