Covering n×n n \times n dots with continuous straight lines

Consider a n×n n \times n grid of n2 n^2 points. What is the minimum number of straight lines that are needed to cover all n2n^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 n = 3 , see Think outside the box sometimes.
For n=4 n = 4 , see Inspired by Chester Robinson.

Note by Calvin Lin
4 years, 8 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

More precisely it seems that it would require, at most and/or at least, (2n2)(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).

Caleb Townsend - 4 years, 8 months ago

Log in to reply

For n=2 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 2n2 2n -2 for n3 n \geq 3 .

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

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

Calvin Lin Staff - 4 years, 8 months ago

Log in to reply

Following up on your hint in the comment section of the n=4n = 4 question, suppose that a "legal" path through the points of the nn by nn grid has a total of kk horizontal lines and vertical lines. Since there are 2n2n rows and columns, there are 2nk2n - k rows and columns that aren't traversed by horizontal or vertical lines, respectively. Let there be hh such horizontal lines and vv such vertical lines, in which case 2nk=h+v2n - 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 4545^{\circ} diagonal).

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

If h=1h = 1 then the path has n1n - 1 horizontal lines, with a row of nn 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 2n12n - 1 lines. Similarly if v=1v = 1.

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

Brian Charlesworth - 4 years, 8 months ago

Log in to reply

@Brian Charlesworth My solution is identical / similar to yours.

I let HH be the number of horizontal lines, VV be the number of vertical lines, D D be the number of diagonal lines. It made it slightly easier to count / think about.

  1. If H=n H = n , then we will need n1 n - 1 lines to connect them up, so a minimum of 2n1 2n - 1 . Similarly if V=n V = n .
  2. Otherwise, there is a (nH)×(nV) (n - H) \times ( n - V) subgrid of points that isn't covered. As pointed out, there are 2(nH)+2(nV)4 2(n-H) + 2(n-V) - 4 points on the perimeter, and each diagonal line can cover at most 2 points. Hence, the total number of lines is t least

H+V+2(nH)+2(nV)42=H+V+(nH)+(nV)2=2n2 H + V + \frac{ 2 (n-H) + 2(n-V) - 4 } { 2} = H + V + (n-H) + (n-V) - 2 = 2n - 2

Calvin Lin Staff - 4 years, 7 months ago

Log in to reply

@Calvin Lin O.k., great. Same idea, but more clearly stated than my exposition. :)

Brian Charlesworth - 4 years, 7 months ago

Log in to reply

@Calvin Lin I see; 4 months ago, I read in a textbook, "Induction is very powerful, but not so powerful that it can prove something that isn't true." Perhaps the reason I couldn't prove that the number of lines required is 2n22n - 2 is because I was assuming it was also true for n=1n = 1 and n=2.n = 2.

Caleb Townsend - 4 years, 7 months ago

Log in to reply

@Caleb Townsend I like that quote. With induction, I guess you have to be careful where you start the journey. :)

Brian Charlesworth - 4 years, 7 months ago

Log in to reply

@Caleb Townsend Read this wiki on Construction, which talks about the different possible approaches.

In this problem, because the solution for Pn+1 P_{n+1} does not necessarily have a subcase of Pn 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.

Calvin Lin Staff - 4 years, 7 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...