Question 1160021: We have two kind of tiles : 1 x 1 and 2 x 2, and use them to cover the 8 x 3 road without overlapping, how many different ways to arrange tiles there?
Answer by greenestamps(13215)   (Show Source):
You can put this solution on YOUR website!
When I read this problem, I thought it was going to be solved by a simple recursive pattern, as in the problem of how many ways can you tile an n-by-2 rectangle with 1-by-2 tiles, or how many ways can you climb a flight of 8 stairs if you can climb either 1 or 2 steps at a time.
But my attempt to find a recursive pattern quickly got ugly.
I turns out this is a MUCH more difficult problem to analyze. (Although there might be solution methods I don't see that might be easier than mine....)
So I tried a different approach.
We can break down the analysis in terms of the numbers of 2-by-2 tiles used.
Consider a diagram of the 3-by-8 road and the possible locations of the CENTERS of the 2-by-2 tiles. Identify each such location with a (row,column) designation.
Here is a text-formatted display of the diagram I used to do my analysis:
+------+------+------+
| | | |
| | | |
| | | |
+-----1,1----1,2-----+
| | | |
| | | |
| | | |
+-----2,1----2,2-----+
| | | |
| | | |
| | | |
+-----3,1----3,2-----+
| | | |
| | | |
| | | |
+-----4,1----4,2-----+
| | | |
| | | |
| | | |
+-----5,1----5,2-----+
| | | |
| | | |
| | | |
+-----6,1----6,2-----+
| | | |
| | | |
| | | |
+-----7,1----7,2-----+
| | | |
| | | |
| | | |
+------+------+------+
The diagram shows that the center of a single 2-by-2 tile can be on any of 7 levels, and in either of 2 columns.
And when there are more than a single 2-by-2 tile, the levels must differ by at least 2.
Finally, note that we don't need to consider the 1-by-1 tiles; whatever regions are not covered by the 2-by-2 tiles will be covered in only one way by the 1-by-1 tiles.
So now on to the counting....
(1) No 2-by-2 tiles....
That one is easy. The entire array is covered by 1-by-1 tiles; there is only 1 way to do this.
(2) One 2-by-2 tile....
This one is also rather easy. The center of the single 2-by-2 tile can be on any of the 7 levels and in either of 2 columns. 7*2 = 14 ways.
(3) Two 2-by-2 tiles....
By enumeration, we find the number of combinations of 2 of the 7 levels, knowing that they cannot be adjacent:
1-3, 1-4, 1-5, 1-6, 1-7; 2-4, 2-5, 2-6, 2-7; 3-5, 3-6, 3-7; 4-6, 4-7; and 5-7.
That's 15 combinations; and in each of the levels chosen the two 2-by-2 tiles can each be in either of 2 columns. 15*2*2 = 60 ways.
(4) Three 2-by-2 tiles....
Again we enumerate the number of combinations of 3 of the 7 levels, again with the same restriction:
1-3-5, 1-3-6, 1-3-7, 1-4-6, 1-4-7 1-5-7, 2-4-6, 2-4-7, 2-5-7, and 3-5-7.
That's 10 combinations; and in each of the levels chosen the three 2-by-2 tiles can each be in either of 2 columns. 10*2*2*2 = 80 ways.
(5) Four 2-by-2 tiles....
There is only one way to choose 4 of the 7 levels with no two adjacent: 1-3-5-7. And on those four levels each of the 2-by-2 tiles can be in either of 2 columns. 1*2*2*2*2 = 16 ways.
Final total: 1+14+60+80+16 = 171 ways.
ANSWER: There are 171 ways to cover a 3x8 array with 2x2 and 1x1 tiles.
|
|
|
