# Minimum number of lines to draw 111 squares

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.

• How many squares in 2x2 grid (6 lines)? 4 or 5 squares? – npkllr Sep 16 '19 at 15:11
• Is it a requirement that the lines are infinite or can I use line segment? – Helena Sep 16 '19 at 18:44
• Do the lines have to be on an ordinary plane? I can do it with two lines on a mobius strip. :P – Spitemaster Sep 16 '19 at 19:14
• @Spitemaster pictures or it didn't happen – Helena Sep 17 '19 at 7:12
• @npkllr has a very good question there – Raystafarian Sep 17 '19 at 7:33

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

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.

• You can safe at least one line by reusing a line of the first grid for your second grid. You can make your squares in the second grid a different size, to not make sure that you are not accidentally creating a new square. E.g. if your grid size is 1 in the first grid, can make it sqrt(2) in the second grid. – Helena Sep 16 '19 at 18:48
• @Helena Agreed and edited. Thanks! – Arnaud Mortier Sep 16 '19 at 19:26

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

• Nice one! Just 1 short of the optimal number for the $\geq 111$ version. – Arnaud Mortier Sep 16 '19 at 20:07
• Thanks, I'd give some more explanation and share my source code. But I haven't figured out how to maintain proper formatting while using the spoiler tag – Helena Sep 16 '19 at 20:08
• @ArnaudMortier maybe if we combine our approaches we can that number too – Helena Sep 16 '19 at 20:13
• This answer should be the accepted one, optimal for exactly 111 squares. – Conifers Sep 17 '19 at 1:28
• @Conifers The fact that it is not simply tells you that "exactly" was not part of the question. You're the one who came up with that idea initially. – Arnaud Mortier Sep 17 '19 at 5:37

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

• How about exactly 111 squares? :P – Conifers Sep 16 '19 at 15:28

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,
10 of the length AE,
and 4 squares with sides of the length AF, (F is above 15)

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

• I took the liberty to edit part of your answer so that you can see what MathJax can do for you. You can edit it further by clicking "edit" below your answer, or by clicking here. – Arnaud Mortier Sep 17 '19 at 10:12
• By the way, I believe that you cannot get these values without making further assumptions regarding the gap between consecutive lines. In any case, it would be interesting to explain how you obtained them. – Arnaud Mortier Sep 17 '19 at 10:14
• @ArnaudMortier thanks for the MathJax part :P I am new – Pʀıncess Anaya Sep 17 '19 at 10:29
• You're welcome. Don't hesitate to explain even briefly how you obtained these results. – Arnaud Mortier Sep 17 '19 at 10:38

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

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("***********");

}

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.)

• @Arnaud Mortier the "calc" method is what I could formulate to calculate the problem. I've tried it on some cases that I could count and it seems working. And when we try all the cases, there is no solution for 111 except 1x111. This is what I could find, I may be wrong. If you find a mistake for the formulation, it is appreciated. – Koray Sep 16 '19 at 17:30
• I think that your "mistake" comes from the fact that all your lines are either horizontal or vertical, but that is not a requirement from the problem. It is only something you would do if you want to pass 111 as fast as you can, but not if you want to exactly reach it. – Arnaud Mortier Sep 16 '19 at 17:31
• @Arnaud Mortier yes, my solution only uses vertical and horizontal lines. I would love to see other than that, if there is. – Koray Sep 16 '19 at 17:33
• @Arnaud Mortier my country does not allow i.stack.imgur.com so I cannot see your picture.. Opera VPN also not working.. I couldn't visualized your answer :( – Koray Sep 16 '19 at 17:41
• That's too bad. I didn't choose the site, it's automatic in StackExchange sites. – Arnaud Mortier Sep 16 '19 at 17:45