July 2, 2009

How many non-empty subsets S of {1, 2, 3, . . . , 15} have the following two properties?

(1) No two consecutive integers belong to S.

(2) If S contains k elements, then S contains no number less than k.

Interactive version of problem and solution.

Buy Hexaflexagons, Probability, Paradoxes, and the Tower of Hanoi from the MAA Bookstore