Problem:
A stack of cards is labeled with the integers from to , 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 in the stack 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. This 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: . In the original stack of cards, how many cards were above the card labeled
Solution:
Run the process backwards. Start by picking up the card labeled . Next pick up the card labeled , place it on the top of the stack, and bring the bottom card to the top of the stack. Next pick up the card labeled , place it on top of the stack, and bring the bottom card to the top of the stack. The card labeled is now at the top of a three-card stack. Notice that the top card of an -card stack will become the top card of a -card stack after more cards have been picked up (and cards have been moved from the bottom of the stack to the top). It follows by induction that the card labeled is the top card when the number of cards in the stack is for any nonnegative integer that satisfies . In particular, the last time that this happens is just after cards have been picked up. The cards remaining on the table are labeled through . After each of the cards labeled is picked up and placed on top of the stack, another card is brought from the bottom of the stack to the top. Finally, the card labeled is placed on top of the stack and the stack is in its original state. This puts cards on top of the card labeled .
Because the process causes the cards on the table to appear in ascending order, the card labeled is the next-to-last card placed on the table. To keep track of that card, first notice that, when a stack of cards is dealt in this way, the next-to-last card placed on the table begins at position in the stack; then apply the process to a stack of cards. After of the cards have been placed on the table and more cards have been moved from the top of the stack to the bottom, a -card stack remains. Remove the cards that are on the table. The next-to-last card that will be placed on the table from the -card stack is the card that began at position in the -card stack. The position of that card in the -card stack is , so the number of cards above it is .
The problems on this page are the property of the MAA's American Mathematics Competitions