Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1988 AIME Problems/Problem 15

Revision as of 07:17, 4 March 2021 by Phoenixfire (talk | contribs) (→‎Solution 2)

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

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\left(\begin{array}{l} 7 \\ k \end{array}\right)=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)\left(\begin{array}{l} 7 \\ k \end{array}\right)=704\] possible orderings, in agreement with the answer, found previously.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1988_AIME_Problems/Problem_15&oldid=148474"