Difference between revisions of "2000 AIME I Problems/Problem 15"
Silversheep (talk | contribs) |
Silversheep (talk | contribs) |
||
| Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
| − | We try to work backwards. At the end all cards are in a row from left to right in sequential order. We reverse the step: Place the rightmost card on the pile, then place the bottom card on top. Let <math>p_{k}</math> be the position of card 1999 counting from the bottom of the stack when there are <math>2\leq k\leq 2000</math> cards in the stack. We have <math>p_{2}=2</math>. Setting up an recurrence, <math>p_{n+1}=n</math> if <math>p_{n}=1</math> and <math>p_{n+1}=p_{n}-1</math> else. Calculating a few terms we see the pattern <math>p_{3 \cdot 2^k - n}= n+1</math> for <math>n< | + | We try to work backwards. At the end all cards are in a row from left to right in sequential order. We reverse the step: Place the rightmost card on the pile, then place the bottom card on top. Let <math>p_{k}</math> be the position of card 1999 counting from the bottom of the stack when there are <math>2\leq k\leq 2000</math> cards in the stack. We have <math>p_{2}=2</math>. Setting up an recurrence, <math>p_{n+1}=n</math> if <math>p_{n}=1</math> and <math>p_{n+1}=p_{n}-1</math> else. Calculating a few terms we see the pattern <math>p_{3 \cdot 2^k - n}= n+1</math> for <math>n<3 \cdot 2^{k-1}</math>. |
<math>927</math> cards are above the one labeled <math>1999</math>. | <math>927</math> cards are above the one labeled <math>1999</math>. | ||
Revision as of 20:34, 28 March 2008
Problem
A stack of 
cards is labelled 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 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: 
In the original stack of cards, how many cards were above the card labeled 1999?
Solution
We try to work backwards. At the end all cards are in a row from left to right in sequential order. We reverse the step: Place the rightmost card on the pile, then place the bottom card on top. Let 
be the position of card 1999 counting from the bottom of the stack when there are 
cards in the stack. We have 
. Setting up an recurrence, 
if 
and 
else. Calculating a few terms we see the pattern 
for 
.
cards are above the one labeled 
.
See also
| 2000 AIME I (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 | ||
