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?

(In reply to Interesting Variant Solution for 2 stories blocked, stories > 2 challenge by juju)

Since I didn't make up this variation, I feel I am allowed to give my input on it.

A fibonacci sequence seems to indicate that there is a one-to-one correspondence between the number of qualifying sequences of N buildings and the sum of the number of those of N-1 and N-2 buildings.  The previous sentence is a little hard to say grammatically, so allow me to demonstrate.

For every sequence of 3 or 4 (in the first column), there is a sequence of 5 (in the second column). 

4321T  54321T
4231T  54231T
3412T  53412T
3421T  53421T
4312T  54312T
321T   45321T
312T   45312T
231T   45231T

So if we were to prove that this pattern holds for all n, we would prove that f(n) = f(n-1) + f(n-2), which generates the fibonacci sequence (starting with f(1) = 1, f(2) = 2).

Now, if we were to find the formula for 3 stories, it would probably also be recursive, but not as simple.  If I'm correct, the recursion should look something like this:
f(n) = f(n-1) + f(n-2) + 3f(n-3) for n>3
      = n! for n<=3

And for more stories, I believe the recursion would continue.  The coefficients would form a sequence that by itself also appears to have recursive formula.
1, 1, 3, 13, 71, ...

Posted by Tristan on 2006-05-01 18:35:36