Difference between revisions of "1988 AIME Problems/Problem 15"
MRENTHUSIASM (talk | contribs) m (→Solution 2) |
m (→Solution 3) |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 35: | Line 35: | ||
Note. The reasoning in <math>\textbf{Case 2}</math> can be extended to cover both cases by observing that in any sequence of <math>k</math> letters not including letter 9, there are <math>k+2</math> 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 | Note. The reasoning in <math>\textbf{Case 2}</math> can be extended to cover both cases by observing that in any sequence of <math>k</math> letters not including letter 9, there are <math>k+2</math> 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 | ||
<cmath> | <cmath> | ||
− | \sum_{k=0}^{7}(k+2)\binom7k=704 | + | \sum_{k=0}^{7}(k+2)\binom7k= \boxed{704} |
</cmath> | </cmath> | ||
possible orderings, in agreement with the answer, found previously. | possible orderings, in agreement with the answer, found previously. | ||
Line 68: | Line 68: | ||
Case 2.8: The 1st letter is typed before the 9th. There are <math>2^6</math> possibilities. | Case 2.8: The 1st letter is typed before the 9th. There are <math>2^6</math> possibilities. | ||
− | <math>\textbf{Sum:}</math> The total sum is <math>2^7 + 2^7 + (7)2^6 = 704</math> | + | <math>\textbf{Sum:}</math> The total sum is <math>2^7 + 2^7 + (7)2^6 = \boxed{704}</math> |
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 | 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 | -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) | ||
== See also == | == See also == |
Latest revision as of 08:02, 15 August 2024
Contents
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
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
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.
The 9th letter was typed up before lunch. In this case, you have
possibilities for which letters have been typed and which have not.
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 , in which any of the letters
could possibly have been typed before lunch. This yields
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 where any of
could have been typed before lunch. This yields
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 could have been typed before lunch. This yields
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 there are
possibilities.
Case 2.5: The 4th letter is typed before the 9th. There are possibilities for
.
Case 2.6: The 3rd letter is typed before the 9th. Again, there are possibilities.
Case 2.7: The 2nd letter is typed before the 9th. Similarly, there are possibilities.
Case 2.8: The 1st letter is typed before the 9th. There are possibilities.
The total sum is
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)
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.