Intereting Posts

Conditional probability on zero probability events (Definition)
Zero integral implies zero function almost everywhere
Compact multiplication operators
Numbers $n$ with $n,n+2$ coprime to $p_k\#$ on $$
Who is buried in Weierstrass' tomb?
Can every uncountable subset of $\mathbb R$ be split up this way?
Is there any infinite set of primes for which membership can be decided quickly?
Relations (Binary) – Composition
# of counts of an element – Combinatorial Proof of Inclusion-Exclusion Principle (IEP)
What is so interesting about the zeroes of the Riemann $\zeta$ function?
Binary long division for polynomials in CRC computation
Principal value of 1/x- equivalence of two definitions
How is a system of axioms different from a system of beliefs?
Proving :$\arctan(1)+\arctan(2)+ \arctan(3)=\pi$
Specify a bijection from to (0,1].

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!):

- Finding point coordinates of a perpendicular
- How to prove that the problem cannot be solved by the four Arithmetic Operations?
- Is it possible to find an infinite set of points in the 3D space where the distance between any pair is rational?
- The intersection of two parallel lines
- Finding out the area of a triangle if the coordinates of the three vertices are given
- find arc between two tips of vectors in 3D

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

- incidence matrix of a digraph with a self loop
- Given a solid sphere of radius R, remove a cylinder whose central axis goes through the center of the sphere.
- Visual Ways to Remember Cross products of Unit vectors? Cross-product in $\mathbb F^3$?
- A circle with infinite radius is a line
- Family of geometric shapes closed under division
- Ravi substitution in inequalities
- How many maximum number of isosceles triangle are possible in a regular polygon of $n$ sides?
- Why do we use the Euclidean metric on $\mathbb{R}^2$?
- What is (fundamentally) a coordinate system ?
- Geometric proof for inequality

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.

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

- $AB-BA=I$ having no solutions
- A surprising inequality about a $\limsup$ for any sequence of positive numbers
- Mapping $\Delta(2,2,2)\mapsto \Delta(4,4,2)$…
- Prove $\int_0^1 \frac{4\cos^{-1}x}{\sqrt{2x-x^2}}\,dx=\frac{8}{9\sqrt{\pi}}\left(9\Gamma(3/4)^2{}_4F_3(\cdots)+\Gamma(5/4)^2{}_4F_3(\cdots)\right)$
- A group where every two elements different than 1 are conjugate has order 1 or 2.
- Use Little Fermat Theorem to prove $341$ is not a prime base $7$
- Show that $G$ is cyclic
- Nonclassical solution to $u_t-\Delta u=f$ in one space dimension?
- Measurable cardinal existence condition
- $n^2 + (n+1)^2 = m^3$ has no solution in the positive integers
- Purpose Of Adding A Constant After Integrating A Function
- Proof about Steady-State distribution of a Markov chain
- Meaning of “a mapping preserves structures/properties”
- Please prove: $ \lim_{n\to \infty}\sqrt{\frac{1}{n!}} = 0 $
- Is there a generalization of the fundamental theorem of algebra for power series?