12
$\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$
2
  • $\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
    Commented Aug 9, 2015 at 1:30
  • $\begingroup$ An interesting question is seeing what happens in $3$ dimensions. $\endgroup$
    – Allawonder
    Commented Aug 14, 2019 at 21:02

1 Answer 1

6
$\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$
1
  • $\begingroup$ This result is for $n\ge 3,$ isn't it? $\endgroup$
    – Allawonder
    Commented Aug 14, 2019 at 20:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .