Math Is Fun Forum

Toast

Real Member

Registered: 2006-10-08

Posts: 1,321

Painting Apartment Blocks

A painter is employed to paint an apartment block. The owner of the apartment block tells the painter that there are certain conditions as to how the floors of the apartment block can be painted.
- Each floor must be either blue or red.
- No two adjacent floors can both be blue. However they can both be red.

If

is the number of different ways an apartment block of n floors can be painted, express

in terms of

and

.
Prove your answer.

---------------------------------------------------------------------------------------------------
So I drew this diagram, and so far the diagram is the only way I have been able to count how many ways the floors can be painted in.
Using the diagram, I found

and

, so

.

Now it asks me to prove it. How would I go about writing a proof for the formula?
Also, is there any other way to find the number of floors without initially using a diagram?

Thanks.

Last edited by Toast (2007-01-14 19:55:15)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Painting Apartment Blocks

How would I go about writing a proof for the formula?
Also, is there any other way to find the number of floors without initially using a diagram?

Actually, you hit the nail on the head as to how to prove it.  Don't draw a diagram.  If we can't actually see all the combinations, what tool can we use to figure out how many there are?  Reason.

We wish to count P_n.  But P_n is fairly complicated to figure out, so we'll reduce the problem a little.  How many floors in P_n end in blue?  How many in red?

Ending in blue:

Well, lets assume we know what P_n-2 is.  If for every combination in P_n-2, we append a red and then blue floor, we must wind up with a valid combination in P_n which ends with a blue floor.  Also, there is no other valid combination in P_n which ends with a blue floor.  To see this, first note that every combination in P_n which ends with a blue floor must end with {red, blue}.  {blue, blue} isn't valid and neither {red, red} or {blue, red} end in blue.  Also note that P_n-2 makes up all the valid combination in of length n-2.  So this means we must get them all.

So in short, the number in P_n ending in blue is P_n-2.

Ending in red:

To every floor in P_n-1, we may append a red floor and wind up with a valid combination.  By the same logic used above, we know that we aren't missing any combinations.

So the number in P_n ending in red is P_n-1.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: Painting Apartment Blocks

Both you guys are really smart, and I actually understand both of you!!!
Nice diagram and equations Toast.
And cool reasoning by Ricky.
Good Evening.
...Oh I'm back (editting)...
I just went through Ricky's logic while looking intently at the diagram.
It all fits together so nicely.
Really awesome.
The funny thing I wonder is given any number in
this Fibinacci series, what is the least amount of
effort needed to get the two previous numbers.
Also if you were given a number that wasn't in the series, a really big number perhaps,
would you know it wasn't in the series, or the series started off with two values other than 1, 1 ??

Last edited by John E. Franklin (2007-01-16 15:22:21)

---

igloo myrtilles fourmis

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Painting Apartment Blocks

I just wanted to make a note here after reading John's post.  Drawing a diagram to help isn't bad.  I know I've drawn binary trees out to 7 levels to try to see a pattern that I couldn't find.  But reasoning is (just about) always better.  It can be extremely difficult and often puzzling to extrapolate a diagram, especially if you're drawing it by hand.  On the other hand, coming up with a formula through logic alone is very easy to extrapolate, so long as you do so inductively (as I did).

When ever you deal with fib-like sequences, the reasoning I used is the reasoning you should (just about) always use.  It's kind of like a pattern.  Just like the pattern for doing proofs about irrational numbers is by contradiction, doing combinatorial arguments (sometimes called proofs) with fib sequences you start in P_n-2, append something to get it to P_n, and then do the same for P_n-1.

Anyways, that's my rant.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."