Problem 5 (12 points) Suppose we have a horizontal stripe of length in that we w
ID: 3147074 • Letter: P
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
Given,there are 1x1 tiles of red and green colors
1x2 tiles of blue,black and yellow colors
a)
In first case as the length n=0 no tile is needed to strip.
if length n=1 it can be formed by either a single tile of red color or a single tile of green color. So,it can be tiled in 1 way red color or 1 way green color
if length n=2, it can be formed by two 1x1 red tiles in 1 way or it can be formed by two 1x1 green tiles in 1 way or it can be formed by one1x2 blue tile in 1 way or it can be formed by one1x2 black tile in 1 way or it can be formed by one1x2 yellow tile in 1 way
if length n=3,it can be formed by three 1x1 red tiles in 1 way or it can be formed by three 1x1 green tiles in 1 way or it can be formed by one1x2 blue tile and one 1x1 red tile in 2 ways(red followed by blue or blue followed by red) or it can be formed by one1x2 black tile and one 1x1 red tile in 2 ways (red followed by black or black followed by red) or it can be formed by one1x2 yellow tile and one 1x1 red tile in 2ways (red followed by yellow or yellow followed by red) or it can be formed by one1x2 blue tile and one 1x1 green tile in 2 ways(green followed by blue or blue followed by green) or it can be formed by one1x2 black tileand one 1x1 green tile in 2 ways (green followed by black or black followed by green) or it can be formed by one1x2 yellow tile and one 1x1 green tile in 2ways (green followed by yellow or yellow followed by green) .