A stairway has 100 steps. You can climb it by one step at a time, or by two steps. How many different ways to ascend this stairway exist?

(In reply to A Toughie by TomM)

Since the total number of subsets of N = {1, 2, 3, ..., 100} is 2 ^ 100, the number of subsets that satisfy the condition must be less than that number. (We should strictly say "less than or equal to" until we show that there are subsets that don't meet the condition. But we can do that just by considering the set that represents the skipped steps when we take the stairs hree at a time.)

We should also note that every "good" subset will have 50 or fewer members, so if (A sub m) is good, and it is not the subset of all odds or all evens, then its opposite is not good. However, the reverse is not true. {3, 4} is not good, but neither is its opposite

Unfortunately, all I can say from this is that the number is noticibly (but not necessarily substantialy) less than 2 ^ 99, which does not narrow the field sufficiently.

Posted by TomM on 2002-09-05 19:19:41