3
$\begingroup$

The square floor of a square room was covered with colored 1 square unit tiles.The covering tiles were designed to have different (solid) colored tiles that forms rectangular areas but none of these areas have the same dimension with another area. How many tiles are needed to cover the smallest floor?

$\endgroup$
  • $\begingroup$ do they have to be rectangular areas or can the tiles form square areas of the same colour? $\endgroup$ – Beastly Gerbil Jun 24 '17 at 18:55
  • $\begingroup$ I would advise disallowing square areas because then you can just have '1' as the answer. See my answer $\endgroup$ – Beastly Gerbil Jun 24 '17 at 19:05
  • $\begingroup$ Yes,squares are rectangles with the same dimensions. theyre not allowed $\endgroup$ – TSLF Jun 24 '17 at 19:11
  • 1
    $\begingroup$ Let me check whether I've understood everything correctly, with the help of comments on BG's now-deleted answer. We have a room of size n by n units, for some currently unknown n. It's tiled by rectangles; let's say k of them. So there are 2k rectangle side-lengths, and no two of these are equal. We want the smallest n for which this can be done, and the corresponding value of k. Is that right? Are the tiles' side-lengths required to be integers? $\endgroup$ – Gareth McCaughan Jun 24 '17 at 20:19
  • $\begingroup$ yes ,whole tiles. no cuts $\endgroup$ – TSLF Jun 25 '17 at 3:40
5
$\begingroup$

As others have already said, the arrangement with the fewest rectangles has 5 rectangles. This is because:

  • No rectangle can use up the whole side of the floor. If one did, the rectangular arrangement used in the remainder of the floor could be scaled to fill the whole floor with one fewer rectangle.
  • You therefore need a different rectangle in each corner of the floor.
  • Each rectangle has at least 3 neighbours (otherwise on its two internal sides one of the neighbours has a matching dimension)
  • Four rectangles (one in each corner) cannot work as both diagonally opposite pairs would need to be neighbours.

    So we need at least 5 rectangles. If the fifth rectangle were in the middle of a side, the two adjacent corner rectangles would still need to be adjacent to their diagonally opposite corners to get three neighbours, so that is not possible. The fifth rectangle must therefore be an interior rectangle like this:

    enter image description here

    With 5 rectangles, the smallest dimensions they could have are the numbers 1 to 10, so the square floor has dimensions of at least 11x11. I think there are only two solutions for 11x11.

    Using the letters in the diagram, we clearly have:
    b+c=11
    d+e=11
    f+g=11
    h+a=11
    a+e+i=11
    c+g+j=11
    It turns out that all further equations you can set up (e.g. for total area) are linearly dependent on these.

    {b,c},{d,e},{f,g},{h,a} are four of the five pairs {1,10},{2,9},{3,8},{4,7},{5,6}. This means that {i,j} is the fifth unused pair, and we can deduce that i+j=11.

    So a+e=j and c+g=i. Obviously i,j>=3. This rules out {i,j}={1,10} or {2,9}.

    If j=5, then the only choices for {a,e} are {2,3} and {1,4}. So {a,h,d,e} is either {2,9,3,8} or {1,10,4,7}, and {b,c,f,g} is the other. In neither case can we get c+g=6. The same goes for i=5, so {i,j}={5,6} is not possible.

    If j=3, then the only choice for {a,e} is {1,2}. So {a,h,d,e}={1,10,2,8}, and {b,c,f,g}={4,7,5,6}. From this we cannot get c+g=8. The same goes for i=3, so {i,j}={3,8} is not possible.

    This leaves only {i,j}={4,7}. We can assume wlog that i=4, j=7 because we can rotate everything by 90 degrees to swap i and j. Then {c,g}={1,3}. We can rotate everything by 180 degrees to swap c and g, so we can assume wlog that c=1, g=3. We have {a,e}={2,5}, and a=2 leads to the solution above, and a=5 gives the following solution:

    enter image description here

    In text form, the two solutions are:
    2x10,1x6,5x8,3x9,4x7
    5x10,1x9,2x8,3x6,4x7

    For completeness, suppose we allow some of the areas to be squares, but disallow the trivial solution consisting of a single area. Much of the above argument works, until the point where it was deduced that {i,j} is the remaining pair. It is now possible for i=j to equal only one of the numbers in the remaining pair. One that choice is made, similar arguments to before then either prove there is no solution, or produce 2 solutions. I won't go through the cases in detail, but just list the solutions:

    1x8,3x7,4x9,2x10,6x6
    1x9,2x7,4x8,3x10,6x6

    1x5,6x4,7x9,2x10,3x3
    1x9,2x4,7x5,6x10,3x3

    1x6,5x3,8x7,4x10,2x2
    1x7,4x3,8x6,5x10,2x2

    2x7,4x3,8x5,6x9,1x1
    2x5,6x3,8x7,4x9,1x1

    I found no solution when i=j are equal to 4, 5 or greater than 6.

  • $\endgroup$
    • $\begingroup$ -are there also 2 solutions using nxn rectangle if allowed? $\endgroup$ – TSLF Jun 25 '17 at 19:20
    • 1
      $\begingroup$ @TSLF: I've added the 8 solutions I found if squares are allowed. $\endgroup$ – Jaap Scherphuis Jun 26 '17 at 4:50
    4
    $\begingroup$

    The smallest floor can be covered in

    5 rectangles.

    I know this because

    You cannot have a square area covered in 4 rectangles because there is no way to put 4 rectangles in a square grid without at least 2 of them sharing an edge. I have found an example for 5 rectangles for an 11 by 11 unit room. In that example you have (in clockwise order) a 6*3 rectangle, a 2*8 rectangle, a 1*9 rectangle and a 5*10 rectangle on the edges. This leaves a 4*7 rectangle in the center. I know that an 11 by 11 unit room is the smallest room made up of 5 rectangles because for 5 rectangles you need 10 dimensions and they cannot be 0 or the width of the square.

    Floor Tiles layout:

    enter image description here

    $\endgroup$
    • 1
      $\begingroup$ Wrong, actually - check the central rectangle, it ix in fact 5x7. That duplicates the 7 measurement of the 1x7. Fitting 5 rectangles into 11x11 may be possible but this layout is not a valid solution. (@TSLF you may want to unAccept this until it is fixed) $\endgroup$ – Rubio Jun 25 '17 at 4:32
    • $\begingroup$ I have amended my answer now. Hopefully I didn't make another stupid mistake. $\endgroup$ – Zadok Storkey Jun 25 '17 at 7:23
    • $\begingroup$ @ZadokStorkey-Looks like Jaap's edit was 14min earlier $\endgroup$ – TSLF Jun 25 '17 at 19:21
    2
    $\begingroup$

    The first key observation is that

    where two rectangles meet, they can never do so along a complete edge of both -- for then they would have to have a dimension in common.

    This means that

    the number of rectangles (what I called k in a clarification-seeking comment on the original question, and will continue to call k now) must be at least 5; and I think there is "combinatorially/topologically" exactly one pattern with only 5 rectangles.

    Here is a pretty small way to do it with that layout. I don't have a proof that this makes the room size (what I called n in that comment) as small as possible, and indeed it may very well not be. I doubt it's possible to do much better, though.

    A.A.A.A.A.B.B.B.B.B.B.B.B. A.A.A.A.A.B.B.B.B.B.B.B.B. A.A.A.A.A.B.B.B.B.B.B.B.B. A.A.A.A.A.C.C.C.C.C.C.D.D. A.A.A.A.A.C.C.C.C.C.C.D.D. A.A.A.A.A.C.C.C.C.C.C.D.D. A.A.A.A.A.C.C.C.C.C.C.D.D. A.A.A.A.A.C.C.C.C.C.C.D.D. A.A.A.A.A.C.C.C.C.C.C.D.D. A.A.A.A.A.C.C.C.C.C.C.D.D. A.A.A.A.A.C.C.C.C.C.C.D.D. A.A.A.A.A.C.C.C.C.C.C.D.D. E.E.E.E.E.E.E.E.E.E.E.D.D.

    The dimensions are:

    13x13 (for the room); 12x5, 8x3, 9x6, 10x2, 11x1 for the rectangles.

    $\endgroup$
    -1
    $\begingroup$

    (Assuming I read this correctly; dimensions equivalent means both dimensions are equivalent) If square sub tiles are allowed, then $3*1$ can be tiled with $2*1$ and $1*1$. Otherwise, tile an $5*1$ with a $3*1$ and a $2*1$

    $\endgroup$
    • $\begingroup$ It needs to be a square room though $\endgroup$ – Beastly Gerbil Jun 24 '17 at 18:58
    • $\begingroup$ Oh sure no doubt something looked wrong. $\endgroup$ – Caluc Jun 24 '17 at 18:58
    • $\begingroup$ Hi and welcome to the site! Have you taken the tour yet? $\endgroup$ – MikeQ Jun 24 '17 at 18:59
    • $\begingroup$ OK deleting this as I don't even understand the question properly. $\endgroup$ – Caluc Jun 24 '17 at 19:02
    • $\begingroup$ (But you didn't actually delete it. You might want to before it gets more downvotes.) $\endgroup$ – Rubio Jun 25 '17 at 1:55

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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