7
$\begingroup$

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.

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

5 Answers 5

13
$\begingroup$

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.

enter image description here
Thanks to @Helena in the comments, you can save one line like this:
enter image description here
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.
enter image description here The smallest amount of lines is therefore $(6+1)+(7+1)=15$ lines.

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Helena
    Sep 16, 2019 at 18:48
9
$\begingroup$

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

>!

$\endgroup$
7
  • $\begingroup$ Nice one! Just 1 short of the optimal number for the $\geq 111$ version. $\endgroup$ Sep 16, 2019 at 20:07
  • $\begingroup$ 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 $\endgroup$
    – Helena
    Sep 16, 2019 at 20:08
  • $\begingroup$ @ArnaudMortier maybe if we combine our approaches we can that number too $\endgroup$
    – Helena
    Sep 16, 2019 at 20:13
  • $\begingroup$ This answer should be the accepted one, optimal for exactly 111 squares. $\endgroup$
    – Conifers
    Sep 17, 2019 at 1:28
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 17, 2019 at 5:37
5
$\begingroup$

I think the best you can do is

$15$ lines

As follows

enter image description here

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

$\endgroup$
1
  • 3
    $\begingroup$ How about exactly 111 squares? :P $\endgroup$
    – Conifers
    Sep 16, 2019 at 15:28
2
$\begingroup$

Asnwer

enter image description here

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

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 17, 2019 at 10:12
  • $\begingroup$ 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. $\endgroup$ Sep 17, 2019 at 10:14
  • $\begingroup$ @ArnaudMortier thanks for the MathJax part :P I am new $\endgroup$ Sep 17, 2019 at 10:29
  • $\begingroup$ You're welcome. Don't hesitate to explain even briefly how you obtained these results. $\endgroup$ Sep 17, 2019 at 10:38
1
$\begingroup$

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.) enter image description here

$\endgroup$
10
  • $\begingroup$ @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. $\endgroup$
    – Koray
    Sep 16, 2019 at 17:30
  • $\begingroup$ 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. $\endgroup$ Sep 16, 2019 at 17:31
  • $\begingroup$ @Arnaud Mortier yes, my solution only uses vertical and horizontal lines. I would love to see other than that, if there is. $\endgroup$
    – Koray
    Sep 16, 2019 at 17:33
  • $\begingroup$ @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 :( $\endgroup$
    – Koray
    Sep 16, 2019 at 17:41
  • $\begingroup$ That's too bad. I didn't choose the site, it's automatic in StackExchange sites. $\endgroup$ Sep 16, 2019 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.