Posts
Area Man Who Talks a Lot About Teaching Teaches His First Full Day in >10
Years
-
I have taught demo and observational classes regularly since I left
full-time teaching but yesterday was the first time I taught every class
for the day. L...
3 years ago
The answer is 510.
ReplyDeleteLet f(n) be the number of ways to color a ring of n houses.
Suppose that we wish to color a ring of n houses, where n > 3. We consider two cases.
Case 1. House #1 and House #3 have the same color. In this case, we can produce a ring of n-2 houses by removing House #1 and House #2. This transformation is 2-to-1, since we would obtain the same ring of n-2 houses if the color of house #2 were changed. So there are 2*f(n-2) colorings with the property that House #1 and House #3 have the same color.
Case 2. In this case, we can produce a ring of n-1 houses by removing House #2. This transformation is 1-1, so the number of colorings in this case is f(n-1).
Since these two cases are exhaustive, we find that f(n)=2*f(n-2)+f(n-1), and it is easy to calculate f(9) using this recurrence.
f(2) = 6
f(3) = 6
f(4) = 2*6 + 6 = 18
f(5) = 2*6 + 18 = 30
f(6) = 2*18 + 30 = 66
f(7) = 2*30 + 66 = 126
f(8) = 2*66 + 126 = 258
f(9) = 2*126 + 258 = 510