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?

  • $\begingroup$ do they have to be rectangular areas or can the tiles form square areas of the same colour? $\endgroup$ Commented Jun 24, 2017 at 18:55
  • $\begingroup$ I would advise disallowing square areas because then you can just have '1' as the answer. See my answer $\endgroup$ Commented Jun 24, 2017 at 19:05
  • $\begingroup$ Yes,squares are rectangles with the same dimensions. theyre not allowed $\endgroup$
    – TSLF
    Commented Jun 24, 2017 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
    Commented Jun 24, 2017 at 20:19
  • $\begingroup$ yes ,whole tiles. no cuts $\endgroup$
    – TSLF
    Commented Jun 25, 2017 at 3:40

4 Answers 4


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:
    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:

    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:





    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
      Commented Jun 25, 2017 at 19:20
    • 1
      $\begingroup$ @TSLF: I've added the 8 solutions I found if squares are allowed. $\endgroup$ Commented Jun 26, 2017 at 4:50

    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

    • 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
      Commented Jun 25, 2017 at 4:32
    • $\begingroup$ I have amended my answer now. Hopefully I didn't make another stupid mistake. $\endgroup$ Commented Jun 25, 2017 at 7:23
    • $\begingroup$ @ZadokStorkey-Looks like Jaap's edit was 14min earlier $\endgroup$
      – TSLF
      Commented Jun 25, 2017 at 19:21

    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.


    (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$

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

    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.