Apartment Buildings

Pretend for a moment that you are an exterior painter; a person who takes jobs painting the outsides of various buildings. Let's say that the builder who has hired you to paint some new apartment bulidings has a certain subjective design requirement that goes something like the following:

The builder is trying to decide on how many stories each apartment building should have for the most variety of color. He wants to use two colors of paint: red and blue. His only rules are that the exterior of each story of the building be either red or blue, and that no two floors adjacent to each other vertically may be red. Each building must be painted differently. How many different combinations of colors can make up apartment buildings with various numbers of floors?

(Two (2) combinations)

Since there is only one floor, and we only have two colors of paint, there are two different-looking apartment buildings.

Next, let's find the combinations for buildings with two floors:

(Three (3) combinations)

Before you say "What about a buliding with two red floors?" remember that the problem requires that red floors not to be next to each other (one on top of the other). If you've been wondering what all of this has to do with the Fibonacci Series, start looking for patterns as we continue.

Apartments with three stories:

(Five (5) combinations)

So if a building has three floors, there are five ways to paint it. Seeing a pattern? 2, 3, 5. Do those numbers remind you of something? Let's continue.

Apartments with four levels:

(Eight (8) combinations)

Oh yeah! 2, 3, 5, 8. After 1 and 1, those are the next four values of the Fibonacci Series (1, 1, 2, 3, 5, 8, 13, 21, etc). Let's do just one more to test that.

Apartments with 5 stories:

(Thirteen (13) combinations)

So the pattern continues with 13, the 7th number in the Fibonacci Series. This pattern will hold true for any number of stories. How do we know this is not just a coincidence? Click here to see why.

Random Fibonacci number from the 1st through the 200th:

All contents, unless otherwise specified, are © 1999 by Matt Anderson, Jeffrey Frazier, and Kris Popendorf.
Created by Team 27890 for the 1999 competition.