Are Problem Sets used for tiling Dominos?

Probability Level pending

Today, Alice and her two partners have cleared all the problems of ACM within half an hour. But very unfortunately, her partners have left the contest because they have nothing interesting to do, leaving Alice alone, so she has to wait another 4.5 hours. Alice can't leave because she is the captain, so she thought: now that the problems are cleared, why not play a puzzle game using the problem set? So she cuts the problem set into several dominos, and tiling them together to make an m × n m \times n tiles rectangle. Since Alice is an obsessive, she only accepts dominos of the following patterns:

Assume that the dominos are infinite many, and given that each square is 1 × 1 1 \times 1 tile, can she always make an m × n m \times n tiles rectangle for all m ≥ 4 , n ≥ 4 m \geq 4, n \geq 4 ?

Note: This is from one of the problems of my ACM contest today.

Yes No

Alice Smith by Alice Smith , 20, China

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.

1 solution

David Vreken
Nov 15, 2020

You can make a 4 × 3 4 \times 3 , 4 × 4 4 \times 4 , and a 4 × 5 4 \times 5 rectangle as follows:

You can then use a combination of those three rectangles to make any 4 × n 4 \times n rectangle for all integers n ≥ 4 n \geq 4 .

You can also make a 5 × 2 5 \times 2 and a 5 × 5 5 \times 5 rectangle as follows:

You can then use a combination of those two rectangles to make any 5 × n 5 \times n rectangle for all integers n ≥ 4 n \geq 4 .

Then following the following pattern, you can make any 2 × n 2 \times n rectangle for odd integers n ≥ 3 n \geq 3 :

You can then use a combination of these rectangles to make any 2 × n 2 \times n rectangle for all integers n ≥ 6 n \geq 6 .

All the given rectangles above can be used to construct any m × n m \times n rectangle for m ≥ 4 m \geq 4 and n ≥ 4 n \geq 4 . If m m is even, use the width 4 4 rectangles to make a 4 × n 4 \times n rectangle and then 1 2 ( m − 4 ) \frac{1}{2}(m - 4) of the 2 × n 2 \times n rectangles to complete the m × n m \times n rectangle, and if m m is odd, use the width 5 5 rectangles to make a 5 × n 5 \times n rectangle and then 1 2 ( m − 5 ) \frac{1}{2}(m - 5) of the 2 × n 2 \times n rectangles to complete the m × n m \times n rectangle.

Here is an example of a 9 × 8 9 \times 8 rectangle constructed using the method above:

1 Helpful 1 Interesting 4 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...