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?

1 comment:

  1. The answer is 510.

    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.

    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

    ReplyDelete