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

Difference between revisions of "1988 AIME Problems/Problem 15"

(Undo revision 107781 by Derpycarrot123 (talk) (Not sure why my constructive addendum was deleted))
(Tag: Undo)
Line 1: Line 1:
 
== Problem ==
 
== 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 <math>1, 2, 3, 4, 5, 6, 7, 8, 9</math>.
+
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 <math>1, 2, 3, 4, 5, 6, 7, 8, 9</math>.
  
−
While leaving for lunch, the secretary tells a colleague that letter <math>8</math> 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.)
+
While leaving for lunch, the secretary tells a colleague that letter <math>8</math> 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 ==
+
== Solution 1==
−
Re-stating the problem for clarity, let <math>S</math> be a [[set]] arranged in increasing order. At any time an element can be appended to the end of <math>S</math>, or the last element of <math>S</math> can be removed. The question asks for the number of different orders in which the all of the remaining elements of <math>S</math> can be removed, given that <math>8</math> had been removed already.   
+
Re-stating the problem for clarity, let <math>S</math> be a [[set]] arranged in increasing order. At any time an element can be appended to the end of <math>S</math>, or the last element of <math>S</math> can be removed. The question asks for the number of different orders in which all of the remaining elements of <math>S</math> can be removed, given that <math>8</math> had been removed already.   
 
----
 
----
  
Line 14: Line 14:
 
=== A way to compute this quickly (by AlexLikeMath) ===
 
=== A way to compute this quickly (by AlexLikeMath) ===
 
<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==
  
 
== See also ==
 
== See also ==

Revision as of 07:08, 4 March 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 $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

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=148472"