1988 AIME Problems/Problem 15
Problem
In an office at various times during the day, the boss gives the secretary a letter to type, each time putting the letter on top of the pile in the secretary's in-box. When there is time, the secretary takes the top letter off the pile and types it. There are nine letters to be typed during the day, and the boss delivers them in the order 
.
While leaving for lunch, the secretary tells a colleague that letter 
has already been typed, but says nothing else about the morning's typing. The colleague wonders which of the nine letters remain to be typed after lunch and in what order they will be typed. Based upon the above information, how many such after-lunch typing orders are possible? (That there are no letters left to be typed is one of the possibilities.)
Solution
Re-stating the problem for clarity, let 
be a set arranged in increasing order. At any time an element can be appended to the end of , or the last element of can be removed. The question asks for the number of different orders in which the all of the remaining elements of can be removed, given that had been removed already.
Since had already been added to the pile, the numbers 
had already been added at some time to the pile; 
might or might not have been added yet. So currently is a subset of 
, possibly with at the end. Given that has 
elements, there are 
intervals for to be inserted, or might have already been placed, giving 
different possibilities.
Thus, the answer is 
.
A way to compute this quickly (by AlexLikeMath)
See also
| 1988 AIME (Problems • Answer Key • Resources) | ||
| Preceded by Problem 14 |
Followed by Last Question | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
