What is the minimum number of straight lines to connect all the dots on this grid?

Question

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?

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:

.

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!

Answer 1

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.

Answer 2

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.



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.

Answer 3

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.