# Ten squares inside a rectangle

You are given 10 squares with side length of 1 to 10 units each. You want to put them in a rectangle such that there is no overlapping and no piece of a square is outside the rectange. The sides of the squares must be parallel or perpenticular to the sides of the rectangle.
How big is the uncovered area (square units) of the smallest rectange that fit all squares?

Example: in case of 4 squares with side length 1,2,3,4 the size of the smallest rectangle is 5x7 and 5 square units are uncovered. • This reminds me of My Mother's Dish Collection. Mar 6 '20 at 20:43
• For those interested in the answer for other numbers than 10, see this OEIS entry. Mar 8 '20 at 14:05

Here is my attempt, and it is probably optimum if I didn't miss something:

It is

27x15 with 20 empty squares.

the idea is simply;

Put biggest squares at the top, put the rest to the bottom accordingly.

In other words,

$$10+5 = 15$$, $$9+6=15$$, $$8+7=15$$

• I think (but am not absolutely certain) that I've checked all the possible rectangles with area between 385 (minimum) and 405 (this). The $17\times23$ was ridiculously close to fitting (2 units of unavoidable overlap), while the rest had no real chance at all. So indeed this seems to be the optimum.
– Bass
Mar 6 '20 at 21:06
• yes, that's the solution I had in mind as well - and nice drawing! Mar 7 '20 at 19:39

Looking at one of the tags*, it is not possible to:

exactly fill a rectangle with all of the squares, because
the sum of the squares of 1 to 10 is 385
which factorises to 5 x 7 x 11

There are four possible exact rectangles with that area:
385 x 1 – only the 1 x 1 square can be placed
77 x 5 – the 6 thru 10 squares cannot be placed
55 x 7 – the 8 thru 10 squares cannot be placed
35 x 11 – the 10 square can be placed

But the 35 x 11 leaves a strip size 1 x 10 where only the 1 x 1 can go.
So the minimum wastage from this point of view is 9 cells.
*lateral-thinking

This is how I was attempting to solve it: • nice analysis and definitely +1 Mar 7 '20 at 19:41

Getting a bit crowded here with

$$17 \times 24 - 385 = \mathbf{23}$$

empties: