Levik has invested a lot in real estate, and now owns all the land on one side of Flooble Blvd, ending with his very own Perplexus Tower. He now has 10 clients who each want to lease some land in order to build.

Each client plans to build something with a different number of stories from 1 to 10. Levik wants to be able to see all these buildings from the top of Perplexus Tower. This is impossible if any building is immediately behind another that is two or more stories higher.

In how many different orders can Levik lease the narrow strip of land to his 10 clients? What if, after building Perplexus Tower even higher, buildings can only be obscured if the one directly in front of it is three or more stories higher? Four? More?

If the 10-story building is the first one (closest to the tower), then the 9-story building must be immediately behind it.  Similarly, the 8-story building must be immediately behind that, etc:

1 2 3 4 5 6 7 8 9 10 Tower

So if the 10-story building is first, there is only one possible ordering.

If the 10-story building is second, then all of the above applies, and you will be left with just the 1-story building, which will be placed in the first spot.  One possible ordering.

2 3 4 5 6 7 8 9 10 1 Tower

If the 10-story building is third, then all of the above applies and you will be left with the 1-story and 2-story buildings, which can be placed in 2 different orderings. 

3 4 5 6 7 8 9 10 1 2 Tower
3 4 5 6 7 8 9 10 2 1 Tower

If the 10-story building is fourth, then we will be left with the 1, 2, and 3-story buildings, which can be placed in 4 different orderings

4 5 6 7 8 9 10 1 2 3 Tower
4 5 6 7 8 9 10 2 3 1 Tower
4 5 6 7 8 9 10 3 1 2 Tower
4 5 6 7 8 9 10 3 2 1 Tower

A pattern is emerging.  If the 10-story building is fifth, there are 8 different orderings:

5 6 7 8 9 10 1 2 3 4 Tower
5 6 7 8 9 10 2 3 4 1 Tower
5 6 7 8 9 10 3 4 1 2 Tower
5 6 7 8 9 10 3 4 2 1 Tower
5 6 7 8 9 10 4 1 2 3 Tower
5 6 7 8 9 10 4 2 3 1 Tower
5 6 7 8 9 10 4 3 1 2 Tower
5 6 7 8 9 10 4 3 2 1 Tower

I'll stop there.  The pattern is:

10-story     # of
bldg spot  orderings
--------------------
   1          1
   2          1
   3          2
   4          4
   5          8
   6         16
   7         32
   8         64
   9        128
  10      + 256
            ---
            512

So there are 512 (2^9) possible orderings for the buildings in the first case.  I'm sure there's a fancy mathematical proof for that, but this is how I figured it out.  I haven't worked on the other cases yet, but this is a start...

Posted by tomarken on 2006-04-27 10:10:21