The following is a popular riddle:
Draw a $3 \times 3$ grid, and connect all the dots using only $4$ straight consecutive lines.
The solution is to think outside of the box and do the following:
My question is, what is the minimal number of lines (let us call this number $k_n$) for an $n\times n$ grid to connect al the dots using only straight consecutive lines
It is impossible to connect all the dots using only three lines, which gives us the minimal number of lines for $n = 3$ with $k_3 = 4$.
For $n = 2$, we easily see that $k_2 = 3$:
For $n \geq 4$ we can use the trick we used for $n = 3$ and then just expand from there:
This gives us $k_4 \leq 6$ (using what I found out in the edit, this becomes $k_4 = 6$) and in general $k_n \leq 4 + (n-3)\cdot 2 = 2\cdot (n - 1) $ as we need two more lines for every step larger then $3$.
Furthermore, we know that $k_n > n$ because every single line can connect at most $n$ points, and we need to connect $n^2$ points, and we must have double points.
Therefore we can conclude for $n \geq 4$ that:
$$ n < k_n \leq 2\cdot (n-1)$$
My question is: Can we improve the lower or upper limit? Does there even exist an $n\geq 4$ such that $k_n < 2 \cdot (n-1)$?
EDIT: After some thinking, I think we can assume that only the first line can connect $n$ dots, and all the following can at the most connect $n-1$ dots. Now because $n^2 - n = n \cdot (n-1)$ this means that we must atleast need $n$ lines for the $n^2 - n$ dots that remain after the first line. I think it is impossible to actually connect $n -1$ dots with every line (except the first), which improves our lower bound:
$$ n + 1 < k_n \leq 2\cdot (n-1) $$
We now know that $k_4 = 6$, it may be an interesting starting point to see if anyone can find a solution for $n=5$ using $7$ lines, as we know that $6$ is impossible and $8$ is possible.
