31
$\begingroup$

Recently a question was posted with this picture of a 7x7 grid of dots, asking for a possible configuration with 12 lines where you can draw them without lifting a pencil. But is it possible with 11 lines? If so, what about 10?

7x7 square of dots

Just to be clear, you have to draw 11 lines that meet all dots. Or fewer if possible.

Or if it is not possible, explain why not.

Solutions to 12 lines:

1st solution (simpler). 2nd solution (complicated)

Just to be clear, this grid is meant to be placed on a flat surface (such as a table.) Also as implied by the questions, line thickness is smaller than dot radius, but it must pass through the centre if the fit!

$\endgroup$
  • 4
    $\begingroup$ @BmyGuest, a generalised proof of minimum number of lines for different size/shape grids could be interesting IMO. $\endgroup$ – A E Jan 12 '15 at 17:54
  • 1
    $\begingroup$ @warspyking with the new title and context it makes more sense. $\endgroup$ – BmyGuest Jan 12 '15 at 18:14
  • 4
    $\begingroup$ As with other problems of this type, you need to specify the geometry being used. The Euclidean plane is implied, but if you use the projective plane, you can do it with 6 lines. On a torus, you can cover them all with 1 line. People will try to exploit this sort of thing, if you let them. $\endgroup$ – KSmarts Jan 12 '15 at 19:09
  • 1
    $\begingroup$ Are the dots intended to represent points? $\endgroup$ – frodoskywalker Jan 12 '15 at 20:15
  • 3
    $\begingroup$ One more loophole in this kind of question is thickness. A line of sufficient thickness can connect all the dots (by covering them) $\endgroup$ – March Ho Jan 13 '15 at 7:28
44
$\begingroup$

Consider an arbitrary solution: it will use $H$ horizontal lines, $V$ vertical lines, and $S$ skew lines (that are neither vertical nor horizontal).

  1. If $H=7$, then we need at least $6$ lines to connect these horizontal lines to each other. Hence $H+V+S\ge13$ in this case.

  2. If $V=7$, we argue symmetrically to case 1.

  3. If $H=6$, there exist $7$ points (on another horizontal line) that are NOT covered by the horizontal lines in the solution. Each of these $7$ points must be covered by a separate line; this yields $V+S\ge7$ and $H+V+S\ge13$.

  4. If $V=6$, we argue symmetrically to case 3.

  5. It remains to consider the case with $H\le5$ and $V\le5$. Consider the remaining $(7-H)(7-V)$ points that are not covered by any horizontal or vertical line. They form a grid, and the boundary of this grid contains $24-2(H+V)$ points. As each of the skew lines covers at most $2$ of these boundary points, we conclude $S\ge 12-(H+V)$. This is equivalent to $H+V+S\ge12$.

Summarizing, in each of the five cases we needed $H+V+S\ge12$ lines.

The argument generalizes to $n\times n$ grids and yields a lower bound of $2n-1$ for $n\le2$ and a lower bound of $2n-2$ for $n\ge3$. These lower bounds are actually best possible, as one easily constructs solutions with at most $2n-2$ lines for $n\ge3$ (just keep extending the spiral in the above answer for $n=7$; whenever $n$ increases by $1$, we attach $2$ further segments to the spiral).

Hence the complete answer to the problem is as follows. If $n=1$ or $n=2$, the best solution uses $2n-1$ lines. If $n\ge3$, the best solution uses $2n-2$ lines.

$\endgroup$
6
$\begingroup$

Since there is not any restriction to my solution I'm posting this.

As it mentioned in previous question, lines are infinitesimal. Which means without any restriction on dots height, dots are bigger than lines. To show my method easily, here is a picture of the solution with 3x3 dots.

3x3

If you can draw a line that meets all 7 dots in a row with appropriate angle you can basically cover all dots with 7 lines.

$\endgroup$
  • 1
    $\begingroup$ Nice +1. I think the accepted answer is still better, but the OP should be changed to out rule your loophole. (I know that you've asked first. Hence the +1). A simple dot->point replacement will do, won't it? (point meaning the mathematical object) $\endgroup$ – BmyGuest Jan 13 '15 at 8:37
  • 1
    $\begingroup$ @BmyGuest yes, i think same about accepted answer. Only purpose of this answer to show making puzzles shouldnt be this easy and cover all possible outcomes. If it was a geomerty question surely this is not even an answer but hey we are on puzzling.SE $\endgroup$ – shyos Jan 13 '15 at 8:44
  • 1
    $\begingroup$ +1 for creativity. As @BmyGuest says it wouldn't work if using the mathematical definition of "point", but everyone loves a good loophole. $\endgroup$ – Jon Story Jan 13 '15 at 12:52
  • $\begingroup$ The 3 by 3 solution violates the rule of the OP: "...line thickness is smaller than dot radius, but it must pass through the centre..." $\endgroup$ – Olive Stemforn Apr 14 '16 at 20:18
1
$\begingroup$

My answer covers another loop hole, using only 7 lines!

If the dots were mathematical objects, and if the 7x7 dots are on a mathematical ball that's big enough (perhaps we are allowed to assume it's the Earth?), then 7 lines will do also, since all the lines will be large circles and share 2 points (left and right of the square, corresponding to "poles"). One goes simply from one "pole" to the other and back, drawing a zig-zag with 7 lines through all the points. Thanks to @shyos for inspiration.

$\endgroup$

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.