Question

En una oficina, en distintos momentos del día, el jefe entrega a la secretaria una carta para mecanografiar y cada vez la pone encima de la pila de su bandeja de entrada. Cuando tiene tiempo, la secretaria retira la carta superior y la mecanografía. Hay nueve cartas para mecanografiar durante el día, y el jefe las entrega en el orden $1,$ $2,$ $3,$ $4,$ $5,$ $6,$ $7,$ $8,$ $9.$

Al salir a almorzar, la secretaria le dice a un colega que la carta $8$ ya fue mecanografiada, pero no cuenta nada más sobre el trabajo de la mañana. El colega se pregunta cuáles de las nueve cartas quedan para después del almuerzo y en qué orden se mecanografiarán. Según la información anterior, ¿cuántas secuencias de mecanografiado para después del almuerzo son posibles? (Que no quede ninguna carta es una de las posibilidades.)

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 $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 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.)

Respuesta

Respuesta: 704

Conceptos:arreglos con restricciones subconjuntos principio de multiplicación

Nivel de dificultad: 2520

Pista pequeña:

Después de mecanografiar $8$ , las cartas restantes entre $1,\ldots,7$ deben mecanografiarse luego en orden decreciente

After $8$ has been typed, any remaining letters among $1,\ldots,7$ must later be typed in decreasing order

Pista grande:

Separa los casos según que $9$ haya sido mecanografiada antes del almuerzo o quede por insertar en el orden posterior

Separate the cases according to whether $9$ was typed before lunch or remains to be inserted into the later order

Solución:

Cualquier subconjunto de $1,\ldots,7$ puede permanecer en la pila después de mecanografiar $8$ , y esas cartas restantes deben mecanografiarse luego en orden decreciente. Si $9$ ya fue mecanografiada, elegir ese subconjunto da $2^7=128$ órdenes posibles.

Si $9$ permanece, elige $k$ de las siete cartas menores e inserta $9$ en cualquiera de las $k+1$ posiciones de su orden decreciente. Esto da $\begin{aligned}\sum_{k=0}^7\binom7k(k+1)&=7\cdot2^6+2^7\\&=576.\end{aligned}$ Toda secuencia de este tipo puede realizarse mediante una organización adecuada de las entregas y la mecanografía durante la mañana, por lo que el total es $128+576=704.$

Any subset of $1,\ldots,7$ can remain in the stack after $8$ has been typed, and those remaining letters must later be typed in decreasing order. If $9$ was already typed, choosing that subset gives $2^7=128$ possible orders.

If $9$ remains, choose $k$ of the seven smaller letters and insert $9$ into any of the $k+1$ positions in their decreasing order. This gives $\begin{aligned}\sum_{k=0}^7\binom7k(k+1)&=7\cdot2^6+2^7\\&=576.\end{aligned}$ Every such order can be realized by suitable morning choices, so the total is $128+576=704.$

1988 AIME Problema 15

Respuesta: 704

Nivel de dificultad: 2520

Pista pequeña:

Pista grande:

Solución:

El Problema 15 en otros años