Problem:
Find the number of subsets of that contain exactly one pair of consecutive integers. Examples of such subsets are and .
Solution:
Answer (235):
Associate with each subset of a sequence of 10 binary digits, where a 1 in the th position indicates that is in the subset. For example, is associated with the sequence 1010011001 . The answer, then, is the number of such sequences that contain exactly one pair of consecutive 1s.
Let be the number of sequences of binary digits of length that do not contain a pair of consecutive 1 s . Then , and . Any sequence of binary digits that does not contain 11 can be written as 0 followed by such a sequence of binary digits or as 10 followed by such a sequence of binary digits. It follows that , so the are, in fact, the Fibonacci numbers with , , and .
A sequence that contains exactly one pair of consecutive 1 s either
It follows that the required number of sequences is
OR
As above, associate the required subsets with sequences of 10 binary digits that contain exactly one pair of consecutive 1 s . Consider a sequence of , where is one of , or 8 . A sequence of 10 binary digits containing exactly one pair of consecutive 1 s can be constructed by inserting among the
0s, where only two of the 1 s appear together. There are locations to place 1 s . One of these locations gets two 1 s , and of the locations get one 1 . Thus there are ways to insert the 1 s among the 0s. It follows that the number of sequences of 10 binary digits that contain exactly one pair of consecutive 1 s is
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions