Difference between revisions of "1988 AIME Problems/Problem 15"
Phoenixfire (talk | contribs) (→Solution 2) |
(→Solution 2) |
||
| Line 15: | Line 15: | ||
<math>1 \cdot 2 + 7 \cdot 3 + 21 \cdot 4 + 35 \cdot 5 + 35 \cdot 6 + 21 \cdot 7 + 7 \cdot 8 + 1 \cdot 9 </math> <math>=1 \cdot (2+9) + 7 \cdot (3+8) + 21 \cdot (4+7) + 35 \cdot (5+6) = 64 \cdot 11 = \boxed{704}</math> | <math>1 \cdot 2 + 7 \cdot 3 + 21 \cdot 4 + 35 \cdot 5 + 35 \cdot 6 + 21 \cdot 7 + 7 \cdot 8 + 1 \cdot 9 </math> <math>=1 \cdot (2+9) + 7 \cdot (3+8) + 21 \cdot (4+7) + 35 \cdot (5+6) = 64 \cdot 11 = \boxed{704}</math> | ||
| − | ==Solution 2== | + | ==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. | 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. | ||
Revision as of 00:26, 15 May 2021
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 
.
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 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 
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 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)
==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.
Since letter 9 arrived before lunch, no further letters will arrive, and the number of possible orders is simply the number of subsets of 
which might still be in the box. In fact, each subset of 
is possible, because the secretary might have typed letters not in the subset as soon as they arrived and not typed any others. Since has 8 elements, it has 
subsets (including the empty set).
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 
which might have been left in the box during lunch (in descending order). For instance, if the letters in the box during lunch are 
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 places at which letter 9 could be inserted into a sequence of 
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 
. Thus if letters are in the basket after returning from lunch, then there are places to insert letter 9 (without duplicating any 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\]](http://latex.artofproblemsolving.com/0/a/d/0ad026c0a3e3c41f90637d149cfd457a3190af52.png)
new orderings in 
.
Combining these cases gives 
possible typing orders.
Note. The reasoning in can be extended to cover both cases by observing that in any sequence of letters not including letter 9, there are 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\]](http://latex.artofproblemsolving.com/b/0/8/b0857393d68268cef187ba75ba784988e64d33a5.png)
possible orderings, in agreement with the answer, found previously.
~phoenixfire
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. 
