Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

How many different rectangles (in terms of area) can fit in a 20-unit-wide square? The rectangles can be squares, and their dimensions are integers.

share|improve this question
    
Is the question supposed to be "How many distinct nonzero areas can be achieved by the pieces in a partition of a 20-by-20 square into rectangles where the constant coordinate of every side is an integer?"? –  Ricky Demer Sep 9 '10 at 7:54
1  
Are you asking us to fit rectangles of pairwise distinct areas into a single square, or are you asking how many numerical values of area are achievable with rectangles of side length at most 20? –  S. Carnahan Sep 9 '10 at 7:57
2  
-1, unclear question. It could also mean "how many different ways are there to partition the 20x20 unit square into subregions of integer size greater than zero width and greater than zero length?" –  sleepless in beantown Sep 9 '10 at 8:21
2  
I'm puzzled by unknown's "@Scott: The latter." I interpret this as meaning the rectangles are not supposed to all be in the square at the same time (which contradicts the "@Ricky: Yes"). If this is the case then we don't have an answer yet, and we must keep in mind things like a 1-by-23 rectangle fitted in along a diagonal. And even if this isn't what unknown meant, it could be an interesting question. –  Gerry Myerson Sep 9 '10 at 12:48
2  
What I am curious about is the origin of this question, especially since the size is fixed. –  Victor Protsak Sep 9 '10 at 16:57
show 2 more comments

3 Answers

up vote 0 down vote accepted

If you're looking for the number of different areas realizable by fitting rectangles in a 20x20 square with (integer-length) edges parallel to the coordinate axes, the answer is the number of elements in {$ \{ x \times y | x,y \in \{ 1..20 \} \} $}. In Haskell, length . List.nub . sort $ [x*y| x<-[1..20] , y<-[1..20]] evaluates to 152.

share|improve this answer
1  
This was how I understood the question as well, but the original poster has been singularly unclear about what he or she actually intended. (Also, under this interpretation, the question should be closed as not of research level.) The associated sequence in the OEIS is here: research.att.com/~njas/sequences/A027424 –  JBL Sep 9 '10 at 14:10
1  
sorting by area conflates the {2x2} rectangle as being the same as the {1x4} or {4x1} rectangle. See the second part of my answer below. –  sleepless in beantown Sep 9 '10 at 15:23
    
This was interpretation I had in mind, not the others. I'm assuming it's not possible to find the number of distinct products there are from 2 integers between 1 to 20 inclusive, without doing prime factorization? –  user9107 Sep 10 '10 at 0:23
    
The question of the number of distinct products was raised and discussed at mathoverflow.net/questions/31663/… –  Gerry Myerson Sep 10 '10 at 6:11
add comment

The answer is 27. The 28th triangular number is 406, so 28 is out, but you can fit rectangles in the square so that 1+...+21+24+25+27+28+30+35=400. 1-20 are 1xn rectangles, and you can arrange them so that you get a 10x19 rectangle left over. Cut off a stripe with 3x9 and 3x10, so you have 7x19 left. Chop off the other direction with 3x7 and 4x7. The remaining 7x12 rectangle is partitioned into 2x12, 5x5, and 5x7.

share|improve this answer
    
And how do you fit those rectangles into the square? –  Ricky Demer Sep 9 '10 at 8:12
2  
The answer may be 28, if you believe rectangles can have zero area. –  S. Carnahan Sep 9 '10 at 8:18
1  
This is a tour de force! –  Victor Protsak Sep 9 '10 at 17:06
add comment

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.

If that is the correct answer, my 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 + 9


19    10+11    19x2 + 1x2*
21    12+13    18x2 + 2x2
23    13+14    17x2 + 3x2
25    15+16    16x2 + 4x2
27    17+18    15x2 + 5x2
29    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}

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


share|improve this answer
    
downvoting because the asker clarified in response to my original comment –  Ricky Demer Sep 9 '10 at 9:34
6  
I don't think the asker successfully clarified anything. –  JBL Sep 9 '10 at 14:18
1  
@JBL, thanks, I agree with you. I found my interpretation more fun to think about. –  sleepless in beantown Sep 9 '10 at 15:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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