In this diagram, there are twelve 1 × 1 , six 2 × 2 , and two 3 × 3 squares for a total of 20 squares.
What is the least number of lines needed in total to have exactly 100 squares?
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.
The numbers 5 and 12 also make it work.
Log in to reply
Thanks for letting me know; I’ll fix that.
5+12 = 17, 17>15 therefore it is not the least number of lines.
There exist a lot of number satisfy the equation. Such as n 2 = 2 , n 1 = 1 0 1 , n 2 = 4 , n 1 = 3 5 . Hence, your last line conclusion is wrong.
Log in to reply
Thanks for letting me know, I’ll fix that.
The question asks not merely for solutions that give 100 squares but for the least number of lines which gives 100 squares.
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
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.
Very brilliant.
"dreaded" is appropriate
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
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.
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.
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:
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!
Log in to reply
This was the only helpful ome here
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.
this doesn't show this is the least number of lines required
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)
Does 7 by 7 lines not work?
Log in to reply
7 by 7 only makes 91: 36+25+16+9+4+1
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".
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.
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.
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.
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 :)
Thang you so much. This is the best and simplest answer I have seen. This should have been at the top.
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.
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.
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.
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).
On an m × n grid, suppose without loss of generality that m ≥ n and let m − n + 1 = a . There are m n 1 × 1 squares, ( m − 1 ) ( n − 1 ) 2 × 2 squares, and so on down to ( m − n + 1 ) 1 n × n squares. Adding these in reverse, the total is 1 ⋅ a + 2 ( a + 1 ) + 3 ( a + 2 ) + ⋯ + n ( a + n − 1 ) = 2 n ( n + 1 ) a + ( 1 ⋅ 0 + 2 ⋅ 1 + 3 ⋅ 2 + ⋯ + n ( n − 1 ) ) = 2 n ( n + 1 ) a + 3 n 3 − n (by an easy induction, or by using the formulas for the sums of the first n numbers and the sums of the first n squares. Knowing this formula is actually not necessary for what follows.) If this equals 1 0 0 , then n 3 − n ≤ 3 0 0 , so n ≤ 6 . Now we can just write down the six equations and see what we get: n = 1 n = 2 n = 3 n = 4 n = 5 n = 6 ⇒ a + 0 = 1 0 0 ⇒ a = 1 0 0 ⇒ m = 1 0 0 , n = 1 ⇒ 3 a + 2 = 1 0 0 ⇒ no solutions ⇒ 6 a + 8 = 1 0 0 ⇒ no solutions ⇒ 1 0 a + 2 0 = 1 0 0 ⇒ a = 8 ⇒ m = 1 1 , n = 4 ⇒ 1 5 a + 4 0 = 1 0 0 ⇒ a = 4 ⇒ m = 8 , n = 5 ⇒ 2 1 a + 7 0 = 1 0 0 ⇒ no solutions So there are three solutions, ( 1 0 0 , 1 ) , ( 1 1 , 4 ) , ( 8 , 5 ) . The number of lines needed to draw an m × n grid is m + n + 2 , so the minimum is 8 + 5 + 2 = 1 5 .
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.
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).
For any given array of lines, the number of squares is equal to:
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 ^_^
a = Minimum # of lines | b = Number of squares | c = Difference between b a and b a − 1 | d = Difference between c a and 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 ≥ 1 0 0 , a ≥ 1 5 .
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.
/ Using C++ can easily solve this problem / / We should consider the calculation function...... / /* the code is shown below */
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 rectangle ( a and b integers), and let's assume a ≥ b . There will be a + b + 2 lines. Also, there will be a b 1 × 1 squares, ( a − 1 ) ( b − 1 ) 2 × 2 squares, ( a − 2 ) ( b − 2 ) 3 × 3 squares, etc. up till ( 1 + a − b ) ( 1 ) b × b squares.
Now, let's try some values for b . Firstly, b = 1 . This results in a total of a squares, so a = 1 0 0 to get the correct number of squares. For b = 2 , we need to sum the number of 1 × 1 and the number of 2 × 2 squares. I.e. there are a b + ( a − 1 ) ( b − 1 ) = 2 a b + 1 − a − b = 3 a − 1 squares. No matter what integer a we choose, this cannot be equal to 100 exactly. In a similar manner, for b = 3 we obtain 6 a − 4 squares, so no solution, for b = 4 we obtain 1 0 a − 1 0 squares, i.e. a = 1 1 , for b = 5 we obtain 1 5 a − 2 0 squares, i.e. a = 8 . Finally, for b = 6 , there are 2 1 a − 3 5 squares. We don't have to investigate b ≥ 7 , as that would mean a + b ≥ 1 4 , a bigger sum than we obtained for b = 5 .
So we have seen that the solution a = 8 , b = 5 is the optimal solution, i.e. a minimum of 8 + 5 + 2 = 1 5 lines is needed to obtain exactly 100 squares.
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 6 2 a 3 + 3 ( 1 + b ) a 2 + ( 1 + 3 b ) a .** 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 = 3 a 3 + 2 a 2 + 6 a 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 ( 2 a 2 + 2 a ) 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).
Problem Loading...
Note Loading...
Set Loading...
Let n 1 and n 2 denote the number of lines for either a row or column, respectively. Without loss of generality, let n 1 ≥ n 2 . The number of 1 × 1 squares in an n 1 × n 2 figure is ( n 1 − 1 ) ( n 2 − 1 ) . The number of 2 × 2 squares in an n 1 × n 2 figure is ( n 1 − 2 ) ( n 2 − 2 ) . This pattern repeats until the number of n 2 − 1 × n 2 − 1 squares are counted. Therefore, the number of total squares in an n 1 × n 2 figure is 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 ) = 1 0 0 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 = 1 0 0 n 1 n 2 ( n 2 − 1 ) − ( n 1 + n 2 ) ( 2 ( n 2 − 1 ) ( n 2 ) ) + 6 ( n 2 − 1 ) ( n 2 ) ( 2 n 2 − 1 ) After much rearranging and dreaded algebra we get 3 n 1 n 2 2 − 3 n 1 n 2 − n 2 3 + n 2 = 6 0 0 After some factoring we get ( n 2 ) ( n 2 − 1 ) ( 3 n 1 − ( n 2 + 1 ) ) = 2 3 × 3 × 5 2 The two numbers that satisfy the equation and minimize the sum of n 1 and n 2 are n 2 = 6 and n 1 = 9 so the answer is 1 5 .