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 \geq n_2$ . The number of $1\times 1$ squares in an $n_1 \times n_2$ figure is $(n_1 - 1)(n_2 - 1)$ . The number of $2\times2$ squares in an $n_1 \times n_2$ figure is $(n_1 - 2)(n_2 - 2)$ . This pattern repeats until the number of $n_2 -1 \times n_2 - 1$ squares are counted. Therefore, the number of total squares in an $n_1 \times n_2$ figure is $\sum_{i = 1}^{n_2-1}(n_1-i)(n_2-i)$ Solving this for 100 squares leads to $\sum_{i = 1}^{n_2-1}(n_1-i)(n_2-i) = 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)\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 $3n_1n_2^{2} - 3n_1 n_2 - n_2^{3} + n_2 = 600$ After some factoring we get $(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$ and $n_2$ are $n_2 = 6$ and $n_1 = 9$ so the answer is $15$ .

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.

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

On an $m \times n$ grid, suppose without loss of generality that $m \ge n$ and let $m - n + 1 = a.$ There are $mn$ $1 \times 1$ squares, $(m-1)(n-1)$ $2\times 2$ squares, and so on down to $(m-n+1)1$ $n \times n$ squares. Adding these in reverse, the total is $\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$ numbers and the sums of the first $n$ squares. Knowing this formula is actually not necessary for what follows.) If this equals $100,$ then $n^3-n \le 300,$ so $n \le 6.$ Now we can just write down the six equations and see what we get: $\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).$ The number of lines needed to draw an $m \times n$ grid is $m+n+2,$ so the minimum is $8+5+2=\fbox{15}.$

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.

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.

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

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 */

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 \times b$ rectangle ( $a$ and $b$ integers), and let's assume $a\geq b$ . There will be $a+b+2$ lines. Also, there will be $ab$ $1\times 1$ squares, $(a-1)(b-1)$ $2\times 2$ squares, $(a-2)(b-2)$ $3\times 3$ squares, etc. up till $(1+a-b)(1)$ $b\times b$ squares.

Now, let's try some values for $b$ . Firstly, $b=1$ . This results in a total of $a$ squares, so $a=100$ to get the correct number of squares. For $b=2$ , we need to sum the number of $1\times 1$ and the number of $2\times 2$ squares. I.e. there are $ab+(a-1)(b-1)=2ab+1-a-b = 3a-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 $6a-4$ squares, so no solution, for $b=4$ we obtain $10a-10$ squares, i.e. $a=11$ , for $b=5$ we obtain $15a-20$ squares, i.e. $a=8$ . Finally, for $b=6$ , there are $21a-35$ squares. We don't have to investigate $b\geq 7$ , as that would mean $a+b\geq 14$ , 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=15$ 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 $\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 $\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\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).