Question

Una pila de $2000$ cartas está etiquetada con los enteros del $1$ al $2000,$ con enteros diferentes en cartas diferentes. Las cartas de la pila no están en orden numérico. Se retira la carta superior de la pila y se coloca sobre la mesa, y la siguiente carta se mueve al fondo de la pila. La nueva carta superior se retira de la pila y se coloca sobre la mesa, a la derecha de la carta que ya está ahí, y la siguiente carta de la pila se mueve al fondo de la pila. El proceso, colocar la carta superior a la derecha de las cartas que ya están sobre la mesa y mover la siguiente carta de la pila al fondo de la pila, se repite hasta que todas las cartas están sobre la mesa. Se observa que, leyendo de izquierda a derecha, las etiquetas de las cartas están ahora en orden ascendente: $1, 2, 3, \ldots, 1999, 2000.$ En la pila original de cartas, ¿cuántas cartas había encima de la carta etiquetada $1999$ ?

A stack of $2000$ cards is labelled with the integers from $1$ to $2000,$ with different integers on different cards. The cards in the stack are not in numerical order. The top card is removed from the stack and placed on the table, and the next card is moved to the bottom of the stack. The new top card is removed from the stack and placed on the table, to the right of the card already there, and the next card in the stack is moved to the bottom of the stack. The process — placing the top card to the right of the cards already on the table and moving the next card in the stack to the bottom of the stack — is repeated until all cards are on the table. It is found that, reading from left to right, the labels on the cards are now in ascending order: $1, 2, 3, \ldots, 1999, 2000.$ In the original stack of cards, how many cards were above the card labelled $1999?$

Respuesta

Solución:

Numera las posiciones originales de $1$ (arriba) a $2000$ (abajo) y colócalas en una cola. Cada paso retira la posición del frente (que recibe la siguiente etiqueta $1, 2, 3, \ldots$ ) y envía el nuevo frente al fondo. Así que la carta etiquetada $1999$ es la penúltima carta retirada, y debemos hallar qué posición original sobrevive tanto tiempo.

La primera pasada retira las posiciones impares $1, 3, \ldots, 1999$ (etiquetas $1$ a $1000$ ) y, como termina enviando $2000$ al fondo, la siguiente pasada empieza de nuevo retirando el frente de la cola $2, 4, \ldots, 2000.$ Las pasadas sucesivas retiran por tanto $2, 6, \ldots, 1998$ (las posiciones $\equiv 2 \bmod 4$ ), luego $4, 12, \ldots, 1996,$ luego $8, 24, \ldots, 1992,$ luego $16, 48, \ldots, 1968, 2000$ (las $63$ posiciones $\equiv 16 \bmod 32$ ). Esa última pasada recorrió un número impar ( $125$ ) de cartas, así que la alternancia se desplaza: los $62$ múltiplos de $32$ supervivientes quedan ahora en la cola como $64, 96, \ldots, 1984, 32.$

Continuando el mismo patrón de retirada desde esa cola, las siguientes rondas retiran $64, 128, \ldots, 1984;$ luego $96, 224, \ldots, 1888, 32;$ luego $288, 544, \ldots, 1824;$ luego $160, 672, 1184, 1696;$ luego $416, 1440;$ y las dos últimas cartas retiradas son $928$ y $1952.$ Así que la etiqueta $1999$ corresponde a la carta en la posición original $928,$ que tenía $927$ cartas encima.

Number the original positions $1$ (top) through $2000$ (bottom) and put them in a queue. Each step removes the front position (which receives the next label $1, 2, 3, \ldots$ ) and sends the new front to the back. So the card labelled $1999$ is the next-to-last card removed, and we must find which original position survives that long.

The first pass removes the odd positions $1, 3, \ldots, 1999$ (labels $1$ through $1000$ ) and, since it ends by sending $2000$ to the back, the next pass again starts by removing the front of the queue $2, 4, \ldots, 2000.$ Successive passes therefore remove $2, 6, \ldots, 1998$ (the positions $\equiv 2 \bmod 4$ ), then $4, 12, \ldots, 1996,$ then $8, 24, \ldots, 1992,$ then $16, 48, \ldots, 1968, 2000$ (the $63$ positions $\equiv 16 \bmod 32$ ). That last pass ran through an odd number ( $125$ ) of cards, so the alternation shifts: the $62$ surviving multiples of $32$ now sit in the queue as $64, 96, \ldots, 1984, 32.$

Continuing the same removal pattern from that queue, the next rounds remove $64, 128, \ldots, 1984;$ then $96, 224, \ldots, 1888, 32;$ then $288, 544, \ldots, 1824;$ then $160, 672, 1184, 1696;$ then $416, 1440;$ and the final two cards removed are $928$ and $1952.$ So label $1999$ goes to the card at original position $928,$ which had $927$ cards above it.

2000 AIME I Problema 15

Solución:

El Problema 15 en otros años