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?

So the variant of the problem for 2 stories not being seen (1 2 3 T is NOT legal) gives the fibonacci sequence, which I thought was very interesting recursive solution. Try 1 building + tower, then 2 buildings + tower, 3 buildings + tower etc. to see it at work. So 89 is the right answer for 10 buildings.

However, after trying to solve it for 3 stories not being seen, I could not come up with a satisfactory recursive general solution like I did for the 2 story case. I have only worked on it for 25 mins, so I will continue to work when I have free time this week. Anyone else have any progress towards 3 or more stories in coming up with a general solution? Ex. (2 4 1 3 T is legal, but 1 3 4 2 T is NOT legal)

Recursive solutions are OK!

-dexcelprep

Posted by juju on 2006-05-01 16:29:37