0

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.

Community
  • 1
warspyking
  • 14,500
  • 10
  • 78
  • 144
  • 2
    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) – Ben Frankel Sep 23 '15 at 03:39
  • @Ben See the note – warspyking Sep 23 '15 at 09:32
  • 2
    @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)? – ghosts_in_the_code Sep 23 '15 at 12:43
  • 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$) – warspyking Sep 24 '15 at 02:13
  • 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. – Rohcana Sep 29 '15 at 18:25
  • @Anachor You mean like (continue to next comment) – warspyking Sep 30 '15 at 02:05
  • @ghosts_in_the_code I did just then? (Read comment above) – warspyking Sep 30 '15 at 02:06
  • I don't know why people get so pedantic about this kind of thing. While the question may not have all its parameters rigorously stated, it seems to me that the intent is quite clear: Connect the dots with straight lines, and no funny business about making super-wide lines that span several dots or vice versa. You're not supposed to be thinking outside the box, except perhaps in the most literal sense. – GentlePurpleRain Oct 01 '15 at 04:48
  • @GentlePurpleRain I smiled at that last part "You're not supposed to be thinking outside the box, except perhaps in the most literal sense" – warspyking Oct 01 '15 at 13:03

2 Answers2

4

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.

ghosts_in_the_code
  • 7,024
  • 1
  • 30
  • 100
4

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

Community
  • 1
GentlePurpleRain
  • 25,965
  • 6
  • 93
  • 155