Tiling With Squares

A floor with dimensions 11 × 11 11 \times 11 will be covered by some tiles with dimensions 1 × 1 , 2 × 2 , 1 \times 1, 2 \times 2, or 3 × 3 3 \times 3 without overlapping. Find the least possible number of 1 × 1 1 \times 1 tiles that will be needed.

0 1 2 3

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Rj Fernandez
Oct 24, 2016

You have only shown that "1" is possible. How do you know that "0 1x1 tile" is impossible?

Pi Han Goh - 4 years, 7 months ago

Do you know how to explain that 1 is indeed the minimium?

Calvin Lin Staff - 4 years, 7 months ago

How did you figure out this tiling?

Agnishom Chattopadhyay - 4 years, 7 months ago

@gavin how do you fill 11 spaces with 2x2 tiles with no remainder?

Reid Stonoga - 4 years, 7 months ago

0 is possible, tile 2x2s along the top and left, leaving a 9x9 space unfilled, then use 3x3 to easily fill the remaining space

Gavin Stewart - 4 years, 7 months ago

Log in to reply

Can we use 2X2's to tile across 11 tiles?

Calvin Lin Staff - 4 years, 7 months ago
Calvin Lin Staff
Oct 30, 2016

From RJ's configuration, we see that we can use just a single 1 × 1 1 \times 1 tile. It remains to show that we cannot use 0 1 × 1 1 \times 1 tiles. We will prove this by contradiction.

Suppose there exist a tiling with only 2 × 2 2 \times 2 and 3 × 3 3 \times 3 tiles.
Color each alternating row blue and then green.
Then, each 2 × 2 2 \times 2 tile covers 2 blue and 2 green tiles, and each 3 × 3 3 \times 3 tile either covers 6 blue and 3 green, or 3 blue and 6 green tiles. Let the number of such tiles be A , B A, B and C C respectively.

Since there are 6 × 11 = 66 6 \times 11 = 66 blue tiles and 5 × 11 = 55 5 \times 11 = 55 green tiles, hence we get the system of equations

2 A + 6 B + 3 C = 66 2 A + 3 B + 6 C = 55 2A + 6 B + 3 C = 66 \\ 2A + 3B + 6C = 55

Taking the difference of the two equations, we get that 3 ( B C ) = 11 B C = 11 3 3(B-C) = 11 \Rightarrow B-C = \frac{11}{3 } . This is not possible since B B and C C are integers, hence we have a contradiction.


Follow up questions: This solution shows that if 6 ∤ n 6 \not \mid n , then we will need at least 1 tile. Can we figure out the answer for general n n ? I suggest looking at cases based on n ( m o d 6 ) n \pmod{6} .

  1. The cases of 6 n + 2 6n+ 2 , 6 n + 3 6n+3 , 6 n + 4 6n + 4 are easy to deal with
  2. What about 6 n + 5 6n+5 which is like this? Is 1 tile enough? Can we use the 11 × 11 11 \times 11 example in our construction?
  3. What about 6 n + 1 6n + 1 ? Is 1 tile enough?

wrong the answer is 2

Richard Gaudet - 4 years, 6 months ago

Log in to reply

Given that there is a configuration which uses only a single 1 × 1 1 \times 1 square (IE Rj's solution), the minimum number needed is at most 1.

Calvin Lin Staff - 4 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...