Mfcttrf

Find the minimum number of lines to draw 111 squares.

For example you can draw a single square using 4 lines i.e 2 vertical and 2 horizontal.

Similar, you can draw a 2 square grid using 5 lines, and so on.

The solution totally depends on how you smartly draw lines because the same number of squares can be drawn with more or less lines.

EDIT: Some have suggested that the question might be to find exactly 111 squares. In this case,

From the table below, one can see that a $6times 6$ grid and a $3times 4$ grid (with a different angle and with a set of intersections located far away from the first one) make a total of $$91+20=111$$
squares, for a total of $7+7+4+5=23$ lines.

Thanks to @Helena in the comments, you can save one line like this:

The gap between lines in the second grid is not a rational multiple of the gap in the first grid, and the small gap between the two grids is a rational multiple of neither. Then the only squares are found within the coloured borders. Total: $23-1=22$ lines

ORIGINAL ANSWER

Let's count

the number of squares in a regular $ptimes q$ grid (that is, with $p+1$ vertical lines and $q+1$ horizontal lines).


There are $p times q$ squares of area 1.
$(p-1)(q-1)$ squares of area 4.

In general, $(p-k)(q-k)$ squares of area $(k+1)^2$ as soon as $p-k$ and $q-k$ are positive.

You see that in general, for the same amount of lines, it is better to have something close to $p=q$ (a big square is better than a long and thin rectangle), because if there are more horizontal lines than vertical lines, then taking a horizontal line to make it vertical will increase the amount of squares of every size.

Indeed,$$(p-k)(q-k)=[pq-(p+q)k+k^2]$$ compared to $$(p+1-k)(q-1-k)=[pq-(p+q)k+k^2]-p+q-1$$ shows that it is worth transferring vertical to horizontal as soon as the difference is bigger than $1$ (and when the difference is $1$ it changes nothing).

The following picture shows you the first values for a $ptimes p$ grid and for a $ptimes (p+1)$ grid.


The smallest amount of lines is therefore $(6+1)+(7+1)=15$ lines.

I think the best you can do is

$15$ lines

As follows

Counting

42 squares of side length 1

30 squares of side length 2

20 squares of side length 3

12 squares of side length 4

6 squares of side length 5

2 squares of side length 6


42+30+20+12+6+2 = 112

I got:

16
By having horizontal and vertical lines on a square grid in rows [0, 1, 2, 3, 4, 5, 6] and columns [0, 1, 2, 3, 4, 6, 7, 8, 10]

Counting:

36 squares of size 1

30 squares of size 2

20 squares of size 3

15 squares of size 4

16 squares of size 5

04 squares of size 6

total: 111 squares

As a picture

I assume we have to draw exactly 111 squares.

My answer:

We have to draw a 1x111 grid, so the count is 111+2 = 114 lines. --> Changed my answer to 19 lines.

How I find that:

 class Program
 
 static void Main(string[] args)
 
 Console.WriteLine("***********");
 printGrids(111);
 Console.WriteLine("***********");
 printGrids(112);
 Console.WriteLine("***********");


 Console.ReadLine();
 

 private static void printGrids(int target)
 
 Console.WriteLine(string.Format("Target: 0", target));
 for (int minDiff = 0; minDiff <= target; minDiff++)
 
 bool found = false;
 for (int x = 1; x <= target; x++)
 for (int y = x; y <= target; y++)
 
 int val = calc(x, y);
 int diff = Math.Abs(val - target);
 if (diff == minDiff)
 
 Console.WriteLine(string.Format("0x1: 2", x, y, val));
 found = true;
 
 
 if (found)
 break;
 
 
 private static int calc(int x, int y)
 
 int sum = 0;
 for (int val = 0; val < Math.Min(x, y); val++)
 sum += (x - val) * (y - val);
 return sum;
 

 

Prints:

***********
Target: 110
1x110: 110
2x37: 110
3x19: 110
4x12: 110
***********
Target: 111
1x111: 111
***********
Target: 112
1x112: 112
6x7: 112
***********

So if 112 is acceptable, using a 6x7 grid (15 lines) would be OK. But if we want exactly 111 squares, 1x111 grid (114 lines) is the only answer.

Edit:
4x12 (18 lines) - is the best answer for 110.
We can add 1 more square to that with 1 line so the answer is 19 lines.

(I cannot see this, I hope you can)