Consider a \( n \times n \) grid of \( n^2 \) points. What is the minimum number of straight lines that are needed to cover all \(n^2 \) points if you were using a pen that could not be removed from the page?

Treat the points as a 0-dimensional object. They do not have length or width.

Treat the lines as a 1-dimensional object. They do not have width.

For \( n = 3 \), see Think outside the box sometimes.

For \( n = 4 \), see Inspired by Chester Robinson.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestIt seems to require \((2n - 2)\) lines to cover a board of size \(n\times n\ (n > 1).\) The best solution for a \(5\times 5\) board uses \(8\) lines, and for \(6\times 6,\) I can find \(10\) lines. I cannot find a proof, and as the strong law of small numbers states, \[\text{"You can't tell by looking."}\]

More precisely it seems that it would require, at most and/or at least, \((2n - 2)\) lines. I have not been able to prove that this is insufficient for larger boards, or that it can be optimized for larger boards. Do you already have the answer Calvin? I have spent an hour on it and it drives me mad (I have spent the better part of the past 45 minutes trying to find an induction step).

Log in to reply

For \( n = 2 \), you actually need 3 lines instead of 2. That is a "special case" that needs to be dealt with.

The answer is indeed \( 2n -2 \) for \( n \geq 3 \).

There is a straight-forward induction proof to show that \( 2n-2 \) lines are sufficient to cover a \(n \geq 3 \) board.

There is a "innovative" proof which shows that you need at least \( 2n - 2 \) lines to cover a \( n \geq 3 \) board. My idea for the proof arose from the induction step, and looking at what the construction looks like.

Log in to reply

Following up on your hint in the comment section of the \(n = 4\) question, suppose that a "legal" path through the points of the \(n\) by \(n\) grid has a total of \(k\) horizontal lines and vertical lines. Since there are \(2n\) rows and columns, there are \(2n - k\) rows and columns that aren't traversed by horizontal or vertical lines, respectively. Let there be \(h\) such horizontal lines and \(v\) such vertical lines, in which case \(2n - k = h + v\). The points these rows and columns have in common, i.e., their points of intersection, must then be traversed by a diagonal, (not necessarily a \(45^{\circ}\) diagonal).

If \(h = 0\) then the path has \(n\) horizontal lines, which would have to be connected by at least \(n - 1\) non-horizontal lines in order to have a continuous path. The path in this case would then have at least \(2n - 1\) lines, exceeding the already established ceiling of \(2n - 2\) lines. Similarly if \(v = 0\).

If \(h = 1\) then the path has \(n - 1\) horizontal lines, with a row of \(n\) points that will each have to have at least one distinct line passing though it to create a legal path. The path in this case would also have to then have at least \(2n - 1\) lines. Similarly if \(v = 1\).

Thus both \(h\) and \(v\) must be \(\ge 2.\) The convex shell of the set of intersection points discussed above will contain \(2h + 2(v - 2) = 2(h + v - 2) = 2(2n - k - 2)\) points, and any diagonal line, (\(45^{\circ}\) or otherwise), can only traverse a maximum of two of these points. Thus we need to have at least \(2n - k - 2\) lines on the path in order to traverse all the points on the grid in addition to the \(k\) horizontal and vertical lines we started with. This gives us a total of at least \((2n - k - 2) + k = 2n - 2\) lines on any legal path. Since we have already established a ceiling of \(2n - 2\) lines, we can conclude that the optimal solution path has \(2n - 2\) lines.

Log in to reply

I let \(H\) be the number of horizontal lines, \(V \) be the number of vertical lines, \( D \) be the number of diagonal lines. It made it slightly easier to count / think about.

\[ H + V + \frac{ 2 (n-H) + 2(n-V) - 4 } { 2} = H + V + (n-H) + (n-V) - 2 = 2n - 2 \]

Log in to reply

Log in to reply

Construction, which talks about the different possible approaches.

Read this wiki onIn this problem, because the solution for \( P_{n+1} \) does not necessarily have a subcase of \( P_{n} \), the forward induction and backward induction approaches will (most likely) not work. Instead, we have to resort to another approach.

In this case, we used the structure finder / structure avoider approach. The idea was that horizontal and vertical lines do great, but we need some diagonal lines to connect things up. However, diagonal lines do very poorly. So, we want to minimize the number of diagonal lines and maximize the number of horizontal / vertical lines, and that is where the push and pull of the problem comes in.

Log in to reply

Log in to reply

Log in to reply