show/hide this revision's text 4 added 982 characters in body

There is also Scott Carnahan's approach in this question, which yields the answer $27$ using triangle numbers. That should also be

If that is the maximum number of rectangles yielded by correct answer, my approach answer above ; should match it, however, my answer is in the form of a heuristic rather than in closed form.

3rd way Here is an example that divides 20x20 into 29 rectangles: The first column is the running count of rectangles so far, the second column is the y-position of the rectangles, the third column tells how to subdivide the length of that rectangle into two parts.

(count) y-pos   xwidth of rects 2       1      19 + 1 4       2      18 + 2 6       3      17 + 3       ...18       9      11 + 919    10+11    19x2 + 1x2*21    12+13    18x2 + 2x223    13+14    17x2 + 3x225    15+16    16x2 + 4x227    17+18    15x2 + 5x229    19+20    14x2 + 6x2

Notice that the {1x2} rectangle is duplicated vertically in the first line and horizontally in the 10th and 11th lines (marked with an asterisk). This yields $29$ different rectangles, with only one duplication, whereas Scott Carnahan's approach has much more than one duplication of the {1x1} square}

show/hide this revision's text 3 added 275 characters in body

If the unclear question means "how many ways can you partition the 20x20 unit region into multiple subregions each of which is a rectangle integer unit dimensions, with widths and lengths greater than zero?" then you've got a different answer.

There is $1$ way to partition it into $400$ different 1x1 squares.

There is $1$ way to partition in into $1$ large 20x20 square.

There are $0$ ways to partition it using $399$ {1x1} squares, because using $399$ {1x1} squares leaves a {1x1} area to be filled, which can only be filled by a {1x1} square yielding $400$ {1x1} squares, which is already counted above.

Using $398$ {1x1} squares, there are $20\times 19 \times 2 = 760$ ways to partition it: with $398$ 1x1 squares and $1$ 2x1 rectangle. The 2x1 rectangle can be posed vertically at $20$ different $x$-positions by $19$ different $y$ positions, or it can be posed horizontally at $19$ different $x$-positions by $20$ different $y$ positions, yielding $20 \cdot 19 \cdot 2$.

You can do similar combinatorics for using $397$ unit squares = $397$ {1x1} + $1$ {3x1}. Placing the long rectangle vertically yields $20 \ times 18$ ways, horizontally also yields $18 \times 20$ ways, totalling $720$ ways.

It gets more fun at $396$ unit squares, because the four squares you've removed from the first part of the solution above can be drawn as just $1$ {2x2} square, or as $2$ {1x2} squares (both of which can take on vertical or horizontal orientations), or as $1$ {4x1} square drawn either vertically or horizontally. The total number of these combinations can be calculated in a similar manner.

And keep going on up to using $0$ (zero) {1x1} squares: the single $1$ {20x20} square fitting in the area.


If you mean how many differently dimensioned rectangles could be drawn, one at a time, into a region of 20x20, then let

the x-dimension can vary from 1 to 20

the y-dimension can vary from 1 to 20

yielding $20\times 20=400$ different size rectangles if orientation matters. Orientation matters if a vertical {1x20}-sized rectangle is considered as being different from the horizontal {20x1}-sized rectangle.

If orientation does not matter, then in this manner of counting each rectangle is counted twice as an $m \times n$ rectangle and as an $n \times m$ rectangle, so divide that in half resulting in $200$ different dimensioned rectangles could be drawn, one at a time, into a region of 20x20, if orientation does not matter.

There is also Scott Carnahan's approach in this question, which yields the answer $27$ using triangle numbers. That should also be the maximum number of rectangles yielded by my approach above; however, my answer is in the form of a heuristic rather than in closed form.

So of course, the answer depends exactly on what you mean specifically by the question.

show/hide this revision's text 2 clarified {1x1} unit square

If the unclear question means "how many ways can you partition the 20x20 unit region into multiple subregions each of which is a rectangle integer unit dimensions, with widths and lengths greater than zero?" then you've got a different answer.

There is $1$ way to partition it into $400$ different 1x1 squares.

There is $1$ way to partition in into $1$ large 20x20 square.

There are $0$ ways to partition it using $399$ {1x1} squares, because using $399$ {1x1} squares leaves a {1x1} area to be filled, which can only be filled by a {1x1} square yielding $400$ {1x1} squares, which is already counted above.

Using $398$ {1x1} squares, there are $20\times 19 \times 2 = 760$ ways to partition itinto $399$ squares : with $398$ 1x1 squares and $1$ 2x1 rectangle. The 2x1 rectangle can be posed vertically at $20$ different $x$-positions by $19$ different $y$ positions, or it can be posed horizontally at $19$ different $x$-positions by $20$ different $y$ positions, yielding $20 \cdot 19 \cdot 2$.

You can do similar combinatorics for using $398$ 397$ unit squares = $397$ {1x1} + $1$ {3x1}. Placing the long rectangle vertically yields $20 \ times 18$ ways, horizontally also yields $18 \times 20$ ways, totalling $720$ ways.

It gets more fun at $396$ unit squares, because the four squares you've removed from the first part of the solution above can be drawn as just $1$ {2x2} square, or as $2$ {1x2} squares (both of which can take on vertical or horizontal orientations), or as $1$ {4x1} square drawn either vertically or horizontally. The total number of these combinations can be calculated in a similar manner.

And keep going on up to using $0$ (zero) {1x1} squares: the single $1$ {20x20} square fitting in the area.


If you mean how many differently dimensioned rectangles could be drawn, one at a time, into a region of 20x20, then let

the x-dimension can vary from 1 to 20

the y-dimension can vary from 1 to 20

yielding $20\times 20=400$ different size rectangles if orientation matters. Orientation matters if a vertical {1x20}-sized rectangle is considered as being different from the horizontal {20x1}-sized rectangle.

If orientation does not matter, then in this manner of counting each rectangle is counted twice as an $m \times n$ rectangle and as an $n \times m$ rectangle, so divide that in half resulting in $200$ different dimensioned rectangles could be drawn, one at a time, into a region of 20x20, if orientation does not matter.

So of course, the answer depends exactly on what you mean specifically by the question.

show/hide this revision's text 1