Minimum number of lines to draw 111 squares

Question

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 in the grid using 5 lines, and so on.

the grid of 4 squares will give you total 5 squares. 4 small squares + 1 large square.

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

Answer 1

---

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 $6\times 6$ grid and a $3\times 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 $p\times 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 $p\times p$ grid and for a $p\times (p+1)$ grid.
The smallest amount of lines is therefore $(6+1)+(7+1)=15$ lines.

Answer 2

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
06 squares of size 5
04 squares of size 6
total: 111 squares

As a picture

Answer 3

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

Answer 4

Asnwer

Diagram explaination...

if you seethe above image you can clearly see there is total 15 lines and we can form 112 squares with 15 lines.
There are 40 with sides of the length AB,
28 of the length AC,
18 of the length AD,
10 of the length AE,
and 4 squares with sides of the length AF, (F is above 15)

Therefore my answer is...

It is possible with 15 straight lines to form 112 squares With 14 straight lines you cannot form more than 91 squares.

The general formula is that with n straight lines we can form as many as if n is ODD.

$\frac{(n-3) (n-1) (n+1)}{24}$ = number of squares

if n is even

$\frac{(n-2)n(n-1)}{24}$ = number of squares

If there are m straight lines at right angles to n straight lines, m being less than n, the

$\frac{m(m - 1)(3n - m - 1)}{6}$ = number of squares

Answer 5

I assume we have to draw exactly 111 squares and the lines are finite.

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("{0}x{1}: {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. (There might be less, I'll check it out when I find time.)