Problem:
Let be a list of the first 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. 120
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 must appear in increasing order from left to right. For there are ways to choose positions in the list for the numbers from through , and the positions of the remaining numbers are then determined. The number of lists is therefore
If is not or , then numbers larger than must appear in reverse order in the list, and numbers smaller than must appear in order. However, and cannot both appear first in the list, so the placement of either or would violate the given conditions. Hence or . By similar reasoning, when reading the list from right to left the number that appears next must be the smallest or largest unused integer from to . This gives choices for each term until there is one number left. Hence there are choices.
The problems on this page are the property of the MAA's American Mathematics Competitions