Given a grid of $n \times m$ points, on a sheet of paper, what's the minimum amount of lines (which can extend infinitely) required to pass through each point, that you can draw without lifting a pencil?

Sample grid and answer: Connect the dots

Note: Lines are of less width then points are radius, all lines must be straight.

  • 2
    $\begingroup$ Could we just say that the points are of zero radius and the lines are of zero width? Otherwise the answer is "technically" 1 because you can always have the dots large enough that they overlap and you can just put a line through their intersection. Also, must the lines be end to end as stated in the puzzle you linked? (if not it's trivial) $\endgroup$ – Ben Frankel Sep 23 '15 at 3:39
  • $\begingroup$ @Ben See the note $\endgroup$ – warspyking Sep 23 '15 at 9:32
  • 2
    $\begingroup$ @warspyking Well, your note is (a) grammatically incorrect (b) difficult to understand. Could you please state the question in a more elaborate form, so we can atleast understand it (and the edit it for you)? $\endgroup$ – ghosts_in_the_code Sep 23 '15 at 12:43
  • $\begingroup$ Basically I give you a grid of dots, and without lifting your pencil you have to draw over every dot with nothing but straight line segments. (The grid is $n \times m$) $\endgroup$ – warspyking Sep 24 '15 at 2:13
  • $\begingroup$ I have voted to close this question as unclear. If you address @ghosts_in_the_code's questions and modify the question, I will retract it. $\endgroup$ – Rohcana Sep 29 '15 at 18:25

I hope the lines are not required to intersect.

We want maximum number of points on each line. We can have a maximum of $m$ points on it (for $m\geq n$). Hence we draw $n$ parallel lines, each with $m$ dots.

  • 2
    $\begingroup$ Even if the lines are required to intersect, because the points are not restricted to zero radius, you can always tilt the lines such that the $n$ lines are in a zigzag formation. $\endgroup$ – Hackiisan Sep 23 '15 at 7:17
  • $\begingroup$ I think @warspyking meant that (a) the points are of zero-radius (b) the lines must form a continuous curve. We'll have to wait and see. $\endgroup$ – ghosts_in_the_code Sep 23 '15 at 7:23
  • $\begingroup$ See the Note ${}$ $\endgroup$ – warspyking Sep 23 '15 at 9:32

This is my hypothesis, but I haven't figured out how to prove it yet:

For $m = n$, the answer is

$2(n-1)$. This employs the solution given in the linked question, of basically using the well-known four-line solution for a $3\times3$ grid, and then extending a square spiral outward to encompass the other dots:

enter image description here

Any other solution (e.g. using a triangle spiral instead of a square) doesn't seem to improve on this number.

For $m > n$, the solution is

$2n-1$. There doesn't appear to be any more efficient solution than just drawing a spiral or zigzagging across the rows:

enter image description here or enter image description here

  • $\begingroup$ By the time you're reading this, you've already counted to nine in your head. Twice. $\endgroup$ – user1717828 Oct 1 '15 at 4:34
  • $\begingroup$ @user1717828 I've counted 3 times :P $\endgroup$ – warspyking Oct 1 '15 at 13:05

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.