85.0k views
1 vote
Suppose that poker chips come in four colors-red, white, green, and blue. Find and solve a recurrence relation for the number of ways to stack n of these poker chips so that there are no consecutive blue chips.

User Medriscoll
by
7.9k points

1 Answer

2 votes

Final answer:

The problem involves establishing a recurrence relation for the number of ways to stack n poker chips without consecutive blue chips. The relation is T(n) = T(n-1) + T(n-2) with the base cases T(1) = 4 and T(2) = 7.

Step-by-step explanation:

We are looking to find and solve a recurrence relation for the number of ways to stack n poker chips in such a way that no two blue chips are consecutive. To establish this relation, we can denote the total number of ways to stack n chips without consecutive blues as T(n). There are two scenarios for placing the nth chip: it can either be a non-blue chip (red, white, or green), or it can be a blue one. If the nth chip is non-blue, we can stack the chips in any manner for the first n-1 chips, so it adds T(n-1) possibilities. If the nth chip is blue, we must ensure that the (n-1)th chip is not blue. Thus, the (n-1)th chip must be non-blue, giving us T(n-2) possibilities since the (n-2)th chip can be chosen freely. Combining these scenarios, the recurrence relation is T(n) = T(n-1) + T(n-2), with the base cases T(1) = 4 and T(2) = 7 (since for two chips, we can have any combination except blue-blue).

User Serhii Onishchenko
by
7.6k points