Problem:
Let be a list of the first 10 positive integers such that for each either or or both appear somewhere before in the list. How many such lists are there?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
If , then the list must be an increasing sequence. Otherwise let . Then the numbers 1 through must appear in increasing order from right to left, and the numbers from through 10 must appear in increasing order from left to right. For there are ways to choose positions in the list for the numbers from 1 through , and the positions of the remaining numbers are then determined. The number of lists is therefore
The problems on this page are the property of the MAA's American Mathematics Competitions