Problem 5 (12 points) Suppose we have a horizontal stripe of length in that we w

Question

Problem 5 (12 points) Suppose we have a horizontal stripe of length in that we wish to tile. The tiles are available in the following shapes and colors: • 1x1 squares available in two colors: red and green • 1x2 rectangles available in three colors: blue, black, and yellow The figure below shows an example of a tiling for n = 11 (the tiles from left to right are 1x1 red, 1x2 blue, 1x1 red, 1x2 black, 1x2 yellow, 1x2 blue, 1x1 green): a. How many different ways can we tile a stripe of length o? How many different ways can we tile a stripe of length 1? 2? 3? For full credit, make sure it is clear how you came up with your results (i.e., just giving the numeric values will not be sufficient). Note that tiles of the same shape and color are indistinguishable and the order of the colors in the stripe does matter. For example, there is only one way to have a stripe with 3 red tiles (since red tiles are not distinguished) and there are two ways to have a stripe with one red tile and one blue tile: (1) a red tile followed by a blue tile and (2) a blue tile followed by a red tile. b. Find a recurrence relation for the number of ways a stripe of length n can be tiled. Make sure to justify your answer. c. One technique we can use to solve a recurrence relation is described in Problems 3 and 4: write out the first few terms of the sequence, guess the solution, and then prove the solution using induction. Another technique is to use the following: Given a sequence {an} described by the recurrence relation an = C10n-1+ C2an-2 where c1, c2 €R and where re-cr - C2 = 0 has 2 distinct roots r and r2. The solution to the recurrence relation is an = ar" + Br2" for n = 0, 1, 2, ... where a and b are constants. Solve your recurrence relation from part busing this second technique (you can use the quadratic formula e, if necessary). d. How many ways can a stripe of length 11 be tiled? (Show your work and simplify your answer as much as possible.)

Explanation / Answer

a. For stripe of length 0 , we can not tile it at all. For stripe of length 1, we can tile it in 2 ways either green or red,

stripe of length 2 can be tiled in 7 ways ( 1way: 2 red tiles, 2nd way: 2 green tiles, 3rd way one red and one green, 4th way one green and one red in another order, 5th way blue tile, 6th way black tile , 7th way yellow tile).

stripe of length 3 can be tiled in combos of:

1. blue and red

2. red and blue in different order

3. blue and green

4. green and blue in reverse order

5.similarly for black and yellow tiles too we will have 4 combos. so 12.

6. 3 red

7. 3 green

8. red red green

9. red green red

10. green red red

11. green green red

12. green red green

13. red green green

So 20 ways of tiling stripe of length 3

b. recurrence relation for tiling a stripe of length n is:

for 1: 2ways ,both with red and green   

for 2: 7 ways ,4 with red and green and 3 with others

for 3 : 20 ways ,8 with red and green and 12 with combos of all 5

d.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.