-1
$\begingroup$

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.

$\endgroup$
9
  • 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$ 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$ 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
3
$\begingroup$

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.

$\endgroup$
3
  • 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$ Sep 23 '15 at 7:23
  • $\begingroup$ See the Note ${}$ $\endgroup$
    – warspyking
    Sep 23 '15 at 9:32
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ By the time you're reading this, you've already counted to nine in your head. Twice. $\endgroup$ Oct 1 '15 at 4:34
  • $\begingroup$ @user1717828 I've counted 3 times :P $\endgroup$
    – warspyking
    Oct 1 '15 at 13:05
  • $\begingroup$ Extending the answer to another related question, I think the answer is $m+n-2$ for $m+n\geq 5$ (the answer is obviously 1 if either m or n equals 1, and 3 if m=n=2). $\endgroup$
    – justhalf
    Feb 25 at 7:20

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.