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 inbox. 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 $1, 2, 3, 4, 5, 6, 7, 8, 9$ .

While leaving for lunch, the secretary tells a colleague that letter $8$ 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 on 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 1

Re-stating the problem for clarity, let $S$ be a set arranged in increasing order. At any time an element can be appended to the end of $S$ , or the last element of $S$ can be removed. The question asks for the number of different orders in which all of the remaining elements of $S$ can be removed, given that $8$ had been removed already.

Since $8$ had already been added to the pile, the numbers $1 \ldots 7$ had already been added at some time to the pile; $9$ might or might not have been added yet. So currently $S$ is a subset of $\{1, 2, \ldots 7\}$ , possibly with $9$ at the end. Given that $S$ has $k$ elements, there are $k+1$ intervals for $9$ to be inserted, or $9$ might have already been placed, giving $k+2$ different possibilities.

Thus, the answer is $\sum_{k=0}^{7} {7 \choose k}(k+2)$ $= 1 \cdot 2 + 7 \cdot 3 + 21 \cdot 4 + 35 \cdot 5 + 35 \cdot 6 + 21 \cdot 7 + 7 \cdot 8 + 1 \cdot 9$ $= \boxed{704}$ .

A way to compute this quickly (by AlexLikeMath)

$1 \cdot 2 + 7 \cdot 3 + 21 \cdot 4 + 35 \cdot 5 + 35 \cdot 6 + 21 \cdot 7 + 7 \cdot 8 + 1 \cdot 9$ $=1 \cdot (2+9) + 7 \cdot (3+8) + 21 \cdot (4+7) + 35 \cdot (5+6) = 64 \cdot 11 = \boxed{704}$

Solution 2

(MAA official solution)

At any given time, the letters in the box are in decreasing order from top to bottom. Thus the sequence of letters in the box is uniquely determined by the set of letters in the box. We have two cases: letter 9 arrived before lunch or it did not.

$\textbf{Case 1:}$ Since letter 9 arrived before lunch, no further letters will arrive, and the number of possible orders is simply the number of subsets of $\mathrm{T}=\{1, 2, \ldots, 6, 7, 9\}$ which might still be in the box. In fact, each subset of $\mathrm{T}$ is possible, because the secretary might have typed letters not in the subset as soon as they arrived and not typed any others. Since $\mathrm{T}$ has 8 elements, it has $2^{8}=256$ subsets (including the empty set).

$\textbf{Case 2:}$ Since letter 9 didn't arrive before lunch, the question is: Where can it be inserted in the typing order? Any position is possible for each subset of $\mathrm{U}=\{1,2, \ldots, 6,7\}$ which might have been left in the box during lunch (in descending order). For instance, if the letters in the box during lunch are $6,3,2,$ then the typing order 6,3,9,2 would occur if the boss would deliver letter 9 just after letter 3 was typed. There would seem to be $k+1$ places at which letter 9 could be inserted into a sequence of $\mathrm{k}$ letters. However, if letter 9 is inserted at the beginning of the sequence (i.e., at the top of the pile, so it arrives before any after-lunch typing is done), then we are duplicating an ordering from $\textbf{Case 1}$ . Thus if $k$ letters are in the basket after returning from lunch, then there are $k$ places to insert letter 9 (without duplicating any $\textbf{Case 1}$ orderings). Thus we obtain $\sum_{k=0}^{7} k\binom 7k=7\left(2^{7-1}\right)=448$ new orderings in $\textbf{Case 2}$ .

Combining these cases gives $256+448=704$ possible typing orders.

Note. The reasoning in $\textbf{Case 2}$ can be extended to cover both cases by observing that in any sequence of $k$ letters not including letter 9, there are $k+2$ places to insert letter 9, counting the possibility of not having to insert it (i.e., if it arrived before lunch) as one of the cases. This yields $\sum_{k=0}^{7}(k+2)\binom7k=704$ possible orderings, in agreement with the answer, found previously.

~phoenixfire

Solution 3

We can think of this as a problem of arrangements.

Notice how, after the morning session, any of the first 7 letters could have been typed up. However, the letters that still remain must be in order from least to greatest.

$\textbf{Case 1:}$ The 9th letter was typed up before lunch. In this case, you have $2^{7}$ possibilities for which letters have been typed and which have not.

$\textbf{Case 2:}$ The 9th letter is to be typed up after lunch. In this case, we can take cases on the number typed up immediately before the 9th letter (still after lunch).

Case 2.1: The 9th letter is typed first. The order of typing is now $\{9, 7, 6, 5, 4, 3, 2, 1\}$ , in which any of the letters $\{1, 2\ldots7\}$ could possibly have been typed before lunch. This yields $2^7$ possibilities.

Case 2.2: The 7th letter comes before the 9th letter. In this case, we are forcing the 7th letter to be typed after lunch. The order of typing is $\{7, 9, 6, 5, 4\ldots1\}$ where any of $\{1\ldots6\}$ could have been typed before lunch. This yields $2^6$ possibilities.

Case 2.3: The 6th letter is typed before the 9th letter. In this case, the 6th letter is forced to be typed after lunch, however the 7th letter is not. Any of $\{7, 5, 4, 3, 2, 1\}$ could have been typed before lunch. This yields $2^6$ possibilities.

Case 2.4: The 5th letter is typed before the 9th. The 5th and 9th letters are forced to be typed after lunch, but the others are not. For the letters $\{7, 6, 4, 3, 2, 1\}$ there are $2^6$ possibilities.

Case 2.5: The 4th letter is typed before the 9th. There are $2^6$ possibilities for $\{7, 6, 5, 3, 2, 1\}$ .

Case 2.6: The 3rd letter is typed before the 9th. Again, there are $2^6$ possibilities.

Case 2.7: The 2nd letter is typed before the 9th. Similarly, there are $2^6$ possibilities.

Case 2.8: The 1st letter is typed before the 9th. There are $2^6$ possibilities.

$\textbf{Sum:}$ The total sum is $2^7 + 2^7 + (7)2^6 = 704$

Clarification: For subcases of 2, the reason the letter immediately before the 9 is forced to be typed is to ensure that it is mutually exclusive from the other subcases considered

-NiranjanR

Note

This problem is very similar to AoPS Intermediate Counting and Probability problem 4.8(which is another AIME problem but I don't know which one)

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

Page

Toolbox

Search