I will post a challenging math problem each day. The level of difficulty will vary, but most problems should not require any specialized knowledge beyond calculus. Problems are also posted on Twitter using the hashtag #mathpotd.
Wednesday, September 23, 2009
Houses on a circular road
Nine houses are built on a circular road. Each house is to be painted either red, white, or blue. Adjacent houses must have different colors. How many color combinations are possible?
Let 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.
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