[Mailbag] What Do You Do with the Ideas You Used to Call “Mistakes”

Guillaume ParĂ©, in the very interesting comments of my last post where I
urged us to reconsider mistakes: I do agree with what is written, but I am
still w...
1 week 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 n2 houses by removing House #1 and House #2. This transformation is 2to1, since we would obtain the same ring of n2 houses if the color of house #2 were changed. So there are 2*f(n2) 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 n1 houses by removing House #2. This transformation is 11, so the number of colorings in this case is f(n1).
Since these two cases are exhaustive, we find that f(n)=2*f(n2)+f(n1), 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