10
$\begingroup$

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:

3x3

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$:

2x2

For $n \geq 4$ we can use the trick we used for $n = 3$ and then just expand from there:

4x4

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.

$\endgroup$
  • $\begingroup$ I have found the following 'paper' here that 'proves' that $k_n = 2\cdot (n-1)$ for all $n \geq 3$, however his argument is not as rigorous as I had hoped. $\endgroup$ – Krijn Aug 9 '15 at 1:30
4
$\begingroup$

I have found a paper that rigorously proves that $k_n = 2\cdot(n-1)$ using graph theory. It is however too long to summarize here. It also handles the cases of an $n \times m$ grid and other options with regard to the rules of the riddle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.