100 squares

In this diagram, there are twelve 1 × 1 , 1\times 1, six 2 × 2 , 2\times 2, and two 3 × 3 3\times 3 squares for a total of 20 squares.

What is the least number of lines needed in total to have exactly 100 squares?


The answer is 15.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

12 solutions

Let n 1 n_1 and n 2 n_2 denote the number of lines for either a row or column, respectively. Without loss of generality, let n 1 n 2 n_1 \geq n_2 . The number of 1 × 1 1\times 1 squares in an n 1 × n 2 n_1 \times n_2 figure is ( n 1 1 ) ( n 2 1 ) (n_1 - 1)(n_2 - 1) . The number of 2 × 2 2\times2 squares in an n 1 × n 2 n_1 \times n_2 figure is ( n 1 2 ) ( n 2 2 ) (n_1 - 2)(n_2 - 2) . This pattern repeats until the number of n 2 1 × n 2 1 n_2 -1 \times n_2 - 1 squares are counted. Therefore, the number of total squares in an n 1 × n 2 n_1 \times n_2 figure is i = 1 n 2 1 ( n 1 i ) ( n 2 i ) \sum_{i = 1}^{n_2-1}(n_1-i)(n_2-i) Solving this for 100 squares leads to i = 1 n 2 1 ( n 1 i ) ( n 2 i ) = 100 \sum_{i = 1}^{n_2-1}(n_1-i)(n_2-i) = 100 i = 1 n 2 1 n 1 n 2 ( n 1 + n 2 ) i = 1 n 2 1 i + i = 1 n 2 1 i 2 = 100 \sum_{i = 1}^{n_2-1}n_1 n_2 - (n_1 + n_2)\sum_{i = 1}^{n_2-1}i + \sum_{i = 1}^{n_2-1}i^{2}= 100 n 1 n 2 ( n 2 1 ) ( n 1 + n 2 ) ( ( n 2 1 ) ( n 2 ) 2 ) + ( n 2 1 ) ( n 2 ) ( 2 n 2 1 ) 6 n_1 n_2(n_2 -1) - (n_1 + n_2)\big(\frac{(n_2-1)(n_2)}{2}\big) + \frac{(n_2 - 1)(n_2)(2n_2 -1)}{6} After much rearranging and dreaded algebra we get 3 n 1 n 2 2 3 n 1 n 2 n 2 3 + n 2 = 600 3n_1n_2^{2} - 3n_1 n_2 - n_2^{3} + n_2 = 600 After some factoring we get ( n 2 ) ( n 2 1 ) ( 3 n 1 ( n 2 + 1 ) ) = 2 3 × 3 × 5 2 (n_2)(n_2-1)(3n_1 - (n_2+1)) = 2^{3}\times3\times5^{2} The two numbers that satisfy the equation and minimize the sum of n 1 n_1 and n 2 n_2 are n 2 = 6 n_2 = 6 and n 1 = 9 n_1 = 9 so the answer is 15 15 .

The numbers 5 and 12 also make it work.

Udbhav Kharad - 3 years, 1 month ago

Log in to reply

Thanks for letting me know; I’ll fix that.

Lucas Chaves Meyles - 3 years, 1 month ago

5+12 = 17, 17>15 therefore it is not the least number of lines.

Roland Ramsdale - 3 years, 1 month ago

There exist a lot of number satisfy the equation. Such as n 2 = 2 , n 1 = 101 , n 2 = 4 , n 1 = 35 n_2=2,n_1=101, n_2=4,n_1=35 . Hence, your last line conclusion is wrong.

Chan Tin Ping - 3 years, 1 month ago

Log in to reply

Thanks for letting me know, I’ll fix that.

Lucas Chaves Meyles - 3 years, 1 month ago

The question asks not merely for solutions that give 100 squares but for the least number of lines which gives 100 squares.

Roland Ramsdale - 3 years, 1 month ago

That last part, where you factor both sides to figure out which whole numbers satisfy the equation... can you expand on the logic a bit there? This seems like a really useful strategy in general

Jonathan Drucker - 3 years, 1 month ago

Log in to reply

Sure! Factoring the left-hand side as much as possible allows us to do a very efficient guess and check method on the number n1 and n2. This is because the three terms must satisfy the prime factorization on the right hand side. Also, realizing that some terms must be either even or odd (if n2 is even, n2 -1 must be odd) reduces the amount of numbers we must check. Of course, one can always solve the equation as a cubic in terms of n2, but the splitting of factors on both sides is, again, a very efficient guess and check method.

Lucas Chaves Meyles - 3 years, 1 month ago

Very brilliant.

Crystal Wang - 3 years, 1 month ago

Log in to reply

Much appreciated!

Lucas Chaves Meyles - 3 years, 1 month ago

"dreaded" is appropriate

Oskar Limka - 3 years, 1 month ago

Log in to reply

Very much so! :)

Lucas Chaves Meyles - 3 years, 1 month ago

I have a question, why would you want to go through all of this work? If you take a look at the lines above, see that there are five lines pointing up and down, on the other hand, there a four lines going from left to right. Now, there are 20 squares. What is 5 x 4? 20. So twenty squares, but we need 100. So, if we are allowed to use as many lines as we need, there could be many, many possible solutions. For example, you could have 50 lines going top to bottom, and only 2 lines going right to left. 50 x 2? 100. 25 x 4? 100. There you are. :D

Giovanni Braun - 3 years ago

Log in to reply

I go through all this work in order to make sure the solution is rigorous although shortcuts, as you presented, are faster ways of simply reaching an answer.

Lucas Chaves Meyles - 2 years, 11 months ago

Log in to reply

Right. I reached the same answer that the other people did in a smaller amount of time, and in a simpler way.

Giovanni Braun - 2 years, 11 months ago
Jeremy Galvagni
Apr 7, 2018

15 lines is the minimum: 6 one way and 9 the other. This makes a 5 by 8 array of small squares and the following totals:

  • 1x1: 40
  • 2x2: 28
  • 3x3: 18
  • 4x4: 10
  • 5x5: 4

The grand total is 100 squares.

6 lines = 1+4; 8 lines= 1+4+9; 10 = 1+4+9+16; 12 = that plus 25, etc. 14 lines would give 91; Ya, guess it's fifteen!

Robert Bernal - 3 years, 1 month ago

Log in to reply

This was the only helpful ome here

Anysha Kumar - 3 years, 1 month ago

Log in to reply

Yeah, maximum squares (i.e. fewest lines) is given by horizontal = vertical or difference of 1. Starting from 3 lines yields 0 squares, each additional line adds squares according to the series 1,1,3,3,6,6,10,10,15,15,21,21 etc. That is, adding a line to a square matrix adds the same number of squares to the total as the previous line that formed the square, and then adding a line in the opposite direction (forming a bigger square) increases the total by the next term in the series of "sum of all numbers 1 to k". Another way to word this is noticing that each pair of consecutive numbers in that series sums to the next square.

J E - 3 years, 1 month ago

this doesn't show this is the least number of lines required

Peter Kippax - 3 years, 1 month ago

Log in to reply

I suppose not, but it's easy enough to check the answer can't be 14 or fewer. 7 each way gives 140, 6 by 8 must be smaller than 6 by 9. (13 lines best is 6 by 7 which is even smaller, 12 lines best is 6 by 6 gives 91 squares)

Jeremy Galvagni - 3 years, 1 month ago

Does 7 by 7 lines not work?

Diego Akel - 3 years, 1 month ago

Log in to reply

7 by 7 only makes 91: 36+25+16+9+4+1

Jeremy Galvagni - 3 years, 1 month ago

Log in to reply

Note that including 1 more line to a row creates 6 more boxes. That's 1 new 6x6 square, 2 new 5x5 squares, 3 new 4x4 squares, 4 new 3x3 squares, 5 new 2x2 squares, and 6 more 1x1 squares, bringing our grand total to 91 + 1 + 2 + 3 + 4 + 5 + 6 = 112, thus a 7 by 8 grid of lines is a valid solution, which gives us the answer "15".

Dominic Bobay - 3 years, 1 month ago

Log in to reply

@Dominic Bobay The question asks for exactly 100 squares. A 7 by 8 grid does not work. But a 6 by 9 does, so the solution is still 15.

Jeremy Galvagni - 3 years, 1 month ago

7 one way and 8 the other:1 1:42, 2 2:30, 3 3:20, 4 4:12, 5 5:6, 6 6:2. Total:110.

jacobi hwang - 3 years, 1 month ago

Log in to reply

No. The goal is exactly 100 squares.

Jeremy Galvagni - 3 years, 1 month ago
Rishabh Bhardwaj
Apr 15, 2018

Simple,

Start: For n number of lines, we can form maximum number of squares of each type only if the number of horizontal lines equals the number of vertical lines, if n is an even number. Else, one side should have only one more line than the other, for n being odd. (: we don't want rectangles to occupy our space :)

Calculations: Let's calculate for an even n and we will arrive the number which gives 100 squares or just below 100. (let m = n / 2)

The total number of squares of length 1 will be (m-1)x(m-1), 2 will be (m-2)x(m-2) and so on till m-1 i.e. 1.

Sum: 1+2x2 + 3x3 +... + (m-1)x(m-1) = (m-1)(m)(2m-1)/6 (put m-1 in summation of squares formula)

This, for m = 7, gives total number of squares 91. For m = 8, it is 140. So the number of lines can be {2x7+1, 2x8} i.e either 15 or 16. For n = 16(m=8), it is 140 - YES, it is more than 100; what about n=15? - We only considered cases where n is even. Let's add one more line to the 7x7 figure. This line will increase the number of 1x1 squares by 6, 2x2 squares by 5, and no need to calculate further. It already more than 100 (91+6+5).

Still we don't know if n = 15 will give the exact sum 100 for some combination of horizontal (H) and vertical lines(V).

Let's do that: given sum of H and V lines 15, start with a 6x6 square (total number of squares 55 with the derived equation above) and start adding lines to V side (or H, but choose same side for each addition). You will notice the sum will start increasing by 15 (i.e., 5+4+3+2+1). Adding 3 such lines will give us the total 55+15x3 i.e. 100.

We won!!!

Answer: 15

:)

I used the exact same method to solving the problem except I never ran into "(m-1)(m)(2m-1)/6". How did you get that? I'm curious to know.

Simon The Great - 3 years, 1 month ago

Log in to reply

Thanks for your read :)

Let suppose you want to calculate number of squares in the grid with length L (distance between two adjacent lines considered to be unity).

The number of choices you have on the set of vertical lines will be (m - L), for first line you have Lth line, 2nd (L+1)th and so on, i. e., (m-L) number of combinations.

Similar is the case with the set of horizontal lines.

Total number of squares: (m-1)x(m-1)+(m-2)x(m-2)...+1x1

Now, getting back to your question:

The sum of squares of n consecutive natural number starting from 1 is: n (n+1) (2n+1)/6 - easy to proove.

Just key in n as m-1

Thanks :)

Rishabh Bhardwaj - 3 years, 1 month ago

Thang you so much. This is the best and simplest answer I have seen. This should have been at the top.

megha jogi - 3 years, 1 month ago

I have a question, why would you want to go through all of this work? If you take a look at the lines above, see that there are five lines pointing up and down, on the other hand, there a four lines going from left to right. Now, there are 20 squares. What is 5 x 4? 20. So twenty squares, but we need 100. So, if we are allowed to use as many lines as we need, there could be many, many possible solutions. For example, you could have 50 lines going top to bottom, and only 2 lines going right to left. 50 x 2? 100. 25 x 4? 100. There you are.

Giovanni Braun - 3 years ago

Log in to reply

The question asks for the LEAST amount of lines necessary to create 100 squares. It's not asking you to use any number of lines you'd like that would be too easy.

Simon The Great - 3 years ago
Shoaib Muneer
Apr 18, 2018

I found a pattern for a square grid. . Total no. Of squares in a grid of 8x8 (16) lines=49+36+25+16+9+4+1=140 and total no. Squares in a grid of 7x7 (14) lines =36+25+16+9+4+1=91 . . So 100 squares can be obtained by 15 lines .... (i guessed)

First of all, question asks exactly 100 lines. You have to prove that some combination of 15 lines makes exactly 100. If it can't, move to the next number (16) and check.

Rishabh Bhardwaj - 3 years, 1 month ago

Great guess, unfortunately this method also indicates that 15 lines would be needed to make exactly 101 squares (which requires 37 lines), or exactly 99 squares (which requires 102 lines).

Justin Dolman - 3 years, 1 month ago
Patrick Corn
Apr 17, 2018

On an m × n m \times n grid, suppose without loss of generality that m n m \ge n and let m n + 1 = a . m - n + 1 = a. There are m n mn 1 × 1 1 \times 1 squares, ( m 1 ) ( n 1 ) (m-1)(n-1) 2 × 2 2\times 2 squares, and so on down to ( m n + 1 ) 1 (m-n+1)1 n × n n \times n squares. Adding these in reverse, the total is 1 a + 2 ( a + 1 ) + 3 ( a + 2 ) + + n ( a + n 1 ) = n ( n + 1 ) 2 a + ( 1 0 + 2 1 + 3 2 + + n ( n 1 ) ) = n ( n + 1 ) 2 a + n 3 n 3 \begin{aligned} 1 \cdot a + 2(a+1) + 3(a+2) + \cdots + n(a+n-1) &= \frac{n(n+1)}2 a + (1 \cdot 0 + 2\cdot 1 + 3 \cdot 2 + \cdots + n(n-1)) \\ &= \frac{n(n+1)}2 a + \frac{n^3-n}3 \end{aligned} (by an easy induction, or by using the formulas for the sums of the first n n numbers and the sums of the first n n squares. Knowing this formula is actually not necessary for what follows.) If this equals 100 , 100, then n 3 n 300 , n^3-n \le 300, so n 6. n \le 6. Now we can just write down the six equations and see what we get: n = 1 a + 0 = 100 a = 100 m = 100 , n = 1 n = 2 3 a + 2 = 100 no solutions n = 3 6 a + 8 = 100 no solutions n = 4 10 a + 20 = 100 a = 8 m = 11 , n = 4 n = 5 15 a + 40 = 100 a = 4 m = 8 , n = 5 n = 6 21 a + 70 = 100 no solutions \begin{aligned} n = 1 &\Rightarrow a + 0 = 100 \Rightarrow a = 100 \Rightarrow m=100, n = 1 \\ n = 2 &\Rightarrow 3a + 2 = 100 \Rightarrow \text{no solutions} \\ n = 3 &\Rightarrow 6a + 8 = 100 \Rightarrow \text{no solutions} \\ n = 4 &\Rightarrow 10a + 20 = 100 \Rightarrow a = 8 \Rightarrow m=11, n = 4 \\ n = 5 &\Rightarrow 15a + 40 = 100 \Rightarrow a = 4 \Rightarrow m = 8, n = 5 \\ n = 6 &\Rightarrow 21a + 70 = 100 \Rightarrow \text{no solutions} \end{aligned} So there are three solutions, ( 100 , 1 ) , ( 11 , 4 ) , ( 8 , 5 ) . (100,1),(11,4),(8,5). The number of lines needed to draw an m × n m \times n grid is m + n + 2 , m+n+2, so the minimum is 8 + 5 + 2 = 15 . 8+5+2=\fbox{15}.

Poke Kid
Apr 18, 2018

Let us start with perfect squares with the base equal to the height of the square. If we follow the pattern, a 1x1 square has 1^{2} squares, a 2x2 square has 2^{2} +1^{2} squares, a 3x3 square has 3^{2}+2^{2}+1^{2} squares,... and so on. Following the sequence, a 6x6 square would have 91 squares and a 7x7 square would have 140 squares. Clearly, the square with the minimum number of 100 squares is between the two squares. A 6x6 square has 14 lines and a 7x7 square has 16 lines. Averaging the two, the answer is 15 lines being the minimum to make 100 squares.

First of all, question asks exactly 100 lines. You have to prove that some combination of 15 lines makes exactly 100. If it can't, move to the next number (16) and check.

Rishabh Bhardwaj - 3 years, 1 month ago

Great guess, unfortunately this method also indicates that 15 lines would be needed to make exactly 101 squares (which requires 37 lines), or exactly 99 squares (which requires 102 lines).

Justin Dolman - 3 years, 1 month ago
Six Sandlava
Apr 18, 2018

For any given array of lines, the number of squares is equal to:

  • (x-1)(y-1) 1*1 squares
  • (x-2)(y-2) 2*2 squares
  • (x-3)(y-3) 3*3 squares
  • (x-4)(y-4) 4*4 squares...

The method to calculate for any given number of squares is essentially a binomial expansion, but it is also easy to brute force through trial and error.

You should end with either y=6 and x=9, or x=6 and y=9.

That is exactly what I did. Seems very intuitive to me. But I forgot to account for squares larger then 3x3, because of the wording of the question, took it too literally. Stupit me ^_^

Walter Schwarz - 3 years, 1 month ago
Elijah Ensley
Apr 20, 2018
a = a= Minimum # of lines b = b= Number of squares c = c= Difference between b a b_{a} and b a 1 b_{a-1} d = d= Difference between c a c_{a} and c a 1 c_{a-1}
4 1 1 1
5 2 1 0
6 5 3 2
7 8 3 0
8 14 6 3
9 20 6 0
10 30 10 4
11 40 10 0
12 55 15 5
13 70 15 0
14 91 21 6
15 112 21 0

For b 100 b\geq 100 , a 15 a\geq 15 .

Lorenzo Nasi
Apr 20, 2018

If we build a 7x7 square it can fit 36 1x1 squares, 25 2x2 squares, 16 3x3 squares, 9 4x4 squares, 4 5x5 squares, 1 6x6 square=93 squares The amount fo the lines to make it is 14.If we add a line it results more than 100.

Lamer Zhang
Apr 19, 2018

/ Using C++ can easily solve this problem / / We should consider the calculation function...... / /* the code is shown below */

include<iostream>

include<iomanip>

include<cstdio>

include<cstring>

include<algorithm>

include<cstdlib>

define wyh scanf

define zc printf

include<queue>

using namespace std; int cal(int i,int j){//i-1 j-1 int tot=0; for(int d=1;d<=min(i,j);d++){ tot+=(i-d)*(j-d); } return tot; } int main(){ int ans=4546541; for(int i=1;i<=50;i++){ for(int j=1;j<=50;j++){ if(cal(i,j)==100){cout<<i<<' '<<j<<'\n';ans=min(ans,i+j);} } } cout<<ans; return 0; }

Instead of counting the lines, let's start by considering a × b a \times b rectangle ( a a and b b integers), and let's assume a b a\geq b . There will be a + b + 2 a+b+2 lines. Also, there will be a b ab 1 × 1 1\times 1 squares, ( a 1 ) ( b 1 ) (a-1)(b-1) 2 × 2 2\times 2 squares, ( a 2 ) ( b 2 ) (a-2)(b-2) 3 × 3 3\times 3 squares, etc. up till ( 1 + a b ) ( 1 ) (1+a-b)(1) b × b b\times b squares.

Now, let's try some values for b b . Firstly, b = 1 b=1 . This results in a total of a a squares, so a = 100 a=100 to get the correct number of squares. For b = 2 b=2 , we need to sum the number of 1 × 1 1\times 1 and the number of 2 × 2 2\times 2 squares. I.e. there are a b + ( a 1 ) ( b 1 ) = 2 a b + 1 a b = 3 a 1 ab+(a-1)(b-1)=2ab+1-a-b = 3a-1 squares. No matter what integer a a we choose, this cannot be equal to 100 exactly. In a similar manner, for b = 3 b=3 we obtain 6 a 4 6a-4 squares, so no solution, for b = 4 b=4 we obtain 10 a 10 10a-10 squares, i.e. a = 11 a=11 , for b = 5 b=5 we obtain 15 a 20 15a-20 squares, i.e. a = 8 a=8 . Finally, for b = 6 b=6 , there are 21 a 35 21a-35 squares. We don't have to investigate b 7 b\geq 7 , as that would mean a + b 14 a+b\geq 14 , a bigger sum than we obtained for b = 5 b=5 .

So we have seen that the solution a = 8 , b = 5 a=8, b=5 is the optimal solution, i.e. a minimum of 8 + 5 + 2 = 15 8+5+2=15 lines is needed to obtain exactly 100 squares.

Alexander Sanchez
Apr 18, 2018

If a figure has exactly a(a+b) small 1x1 squares, then there is a configuration with (a+1)+(a+b+1) lines (like the one seen above with a grid-like shape) and this is the configuration with the least lines which achieves a(a+b) little square. We count the number of squares to be 2 a 3 + 3 ( 1 + b ) a 2 + ( 1 + 3 b ) a 6 \frac {2a^{3} + 3(1+b)a^{2} + (1+3b)a}{6} .** Direct search on a,b yields (5,3) to be the smallest solution (you know that a<7, as otherwise you're busted from the outset). Hence the answer is 15.

**Counting the squares: we have a perfect axa square right next to an axb rectangle. First count the squares in perfect axa square: 1 axa square, ..., a^2 1x1 squares. Hence, there are k = 1 a k 2 = a 3 3 + a 2 2 + a 6 \sum_{k=1}^{a} k^{2} = \frac{a^{3}}{3} +\frac{a^{2}}{2} + \frac{a}{6} squares in the figure. Next, we count the 'new' squares from the axb rectangle, that is, the squares which themselves contain at least one 1x1 square within the axb rectangle. There are b such axa squares, ..., and ab such 1x1 squares. Hence, there are b k = 1 a k = b ( a 2 2 + a 2 ) b\sum_{k=1}^{a} k = b(\frac{a^{2}}{2} + \frac{a}{2}) new squares. Adding these totals together, we have counted all the squares in the figure, as each tile is either in the axb rectangle or not (but not both).

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...