10
$\begingroup$

How many different rectangular rooms, if any, is it possible to cover with all the 55 carpets of different dimensions 1 x 1, 1 x 2, 1 x 3,..., 1 x 10, 2 x 2, 2 x 3, ..., 8 x 9, 8 x 10, 9 x 9, 9 x 10, and 10 x 10, each exactly once?

$\endgroup$
4
  • 1
    $\begingroup$ Can a carpet size used more than once? $\endgroup$
    – justhalf
    Oct 26, 2022 at 3:15
  • 1
    $\begingroup$ @justhalf I highly doubt it, since if you could, the answer would trivially be "infinitely many". $\endgroup$ Oct 26, 2022 at 5:47
  • 6
    $\begingroup$ Your list of sizes confuses me. You omit 1x10, I can't tell whether on purpose or not. You also omit 2x2 but include 1x1. And you omit 9x10 at the end too. So I can't easily deduce which rectangles to include. If you want us to use all possible distinct rectangles with integer edges 1 through 10, maybe just say that and omit the confusing list? $\endgroup$ Oct 26, 2022 at 13:04
  • $\begingroup$ What overlaps are allowed? Can carpets overlap each other or the walls? $\endgroup$
    – Vilx-
    Oct 26, 2022 at 13:17

3 Answers 3

7
$\begingroup$

Building on the answer of Ed Murphy, the possiblities can be tested by trial and error. This shows that...

...both the 11x155 and the 31x55 rectangles can be tiled perfectly. Meaning that their upper bound of two is the exact answer (up to rotation).

This image shows a tiling for the 11x155 rectangle (broken into strips to avoid an awkwardly shaped image): 11x155 tiling of the 55 rectangles

And this image shows a tiling for the 31x55 rectangle: 31x55 tiling of the 55 rectangles

$\endgroup$
1
  • 2
    $\begingroup$ It is possible to make five 11x31 rectangles, giving a solution to both at once. $\endgroup$ Oct 26, 2022 at 14:06
7
$\begingroup$

Partial answer, just an upper bound.

Assuming that the carpets can't overlap each other, themselves, or the walls, and that their sizes correspond to all distinct integer solutions of 1 <= x <= y <= 10:

First, let's calculate the

area of all 55 carpets.
x = 1 -> y = 1 to 10 -> total area of these is 1 x (1+2+...+10) = 1 x 55 = 55
x = 2 -> 2 x 54 = 108
x = 3 -> 3 x 52 = 156
x = 4 -> 4 x 49 = 196
x = 5 -> 5 x 45 = 225
x = 6 -> 6 x 40 = 240
x = 7 -> 7 x 34 = 238
x = 8 -> 8 x 27 = 216
x = 9 -> 9 x 19 = 171
x = 10 -> 10 x 10 = 100

Grand total =

1705 = 5 * 11 * 31

Rectangles with this area:

1 x 1705 (too narrow to fit 10 x 10)
5 x 341 (too narrow to fit 10 x 10)
11 x 155
31 x 55

so the upper bound is

two rectangles

$\endgroup$
2
  • $\begingroup$ You've assumed that each room has to use all 55 carpets, which was not stated explicitly. I assumed that all rooms between them use 55 carpets, and made 55 rooms. Who buys 55 carpets for each room? $\endgroup$ Oct 26, 2022 at 13:25
  • $\begingroup$ Pedants on PSE, obv. $\endgroup$
    – Ed Murphy
    Oct 27, 2022 at 1:10
5
$\begingroup$

Note: This answers the first version of the question.

I don't see why it should be a problem.

enter image description here

$\endgroup$
2
  • $\begingroup$ Very nice! I have amended puzzle to avoid this brilliant but trivial solution. $\endgroup$ Oct 25, 2022 at 23:03
  • 2
    $\begingroup$ @BernardoRecamánSantos your edited question doesn't exclude this answer, it seems? It uses all the carpets as requested. Unless you mean each carpet size can only be used once, which you haven't specified in your question. :) $\endgroup$
    – justhalf
    Oct 26, 2022 at 3:14

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.