10
$\begingroup$

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.

enter image description here

Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
13
$\begingroup$

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

enter image description here

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$

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Bass
    Commented Mar 6, 2020 at 21:06
  • $\begingroup$ yes, that's the solution I had in mind as well - and nice drawing! $\endgroup$
    – ThomasL
    Commented Mar 7, 2020 at 19:39
3
$\begingroup$

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:

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ nice analysis and definitely +1 $\endgroup$
    – ThomasL
    Commented Mar 7, 2020 at 19:41
2
$\begingroup$

Getting a bit crowded here with

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

empties:

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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