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 "2000 AIME I Problems/Problem 15"

(→‎Solution 3 (Recursion))
m (→‎Solution)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
We try to work backwards from when there are 2 cards left, since this is when the 1999 card is laid onto the table. When there are 2 cards left, the 1999 card is on the top of the deck. In order for this to occur, it must be 2nd on the deck when there are 4 cards remaining, and this means it must be the 4th card when there are 8 cards remaining. This pattern continues until it is the 512th card on the deck when there are 1024 cards remaining. Since there are over 1000 cards remaining, some cards have not even made one trip through yet, 2(1024 - 1000) = 48, to be exact. Once these cards go through, 1999 will be the <math>512 - 48 = 464^\text{th}</math> card on the deck. Since every other card was removed during the first round, it goes to show that 1999 was in position <math>464 \times 2 = 928</math>, meaning that there were <math>\boxed{927}</math> cards are above the one labeled <math>1999</math>.
+
We try to work backwards from when there are 2 cards left, since this is when the 1999 card is laid onto the table. When there are 2 cards left, the 1999 card is on the top of the deck. In order for this to occur, it must be 2nd on the deck when there are 4 cards remaining, and this means it must be the 4th card when there are 8 cards remaining. This pattern continues until it is the 512th card on the deck when there are 1024 cards remaining. Since there are over 1000 cards remaining, some cards have not even made one trip through yet, <math>2(1024 - 1000) = 48</math>, to be exact. Once these cards go through, 1999 will be the <math>512 - 48 = 464^\text{th}</math> card on the deck. Since every other card was removed during the first round, it goes to show that 1999 was in position <math>464 \times 2 = 928</math>, meaning that there were <math>\boxed{927}</math> cards are above the one labeled <math>1999</math>.
  
 
== Solution 2 ==
 
== Solution 2 ==

Revision as of 15:41, 18 July 2021

Problem

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 labeled $1999$?

Solution

We try to work backwards from when there are 2 cards left, since this is when the 1999 card is laid onto the table. When there are 2 cards left, the 1999 card is on the top of the deck. In order for this to occur, it must be 2nd on the deck when there are 4 cards remaining, and this means it must be the 4th card when there are 8 cards remaining. This pattern continues until it is the 512th card on the deck when there are 1024 cards remaining. Since there are over 1000 cards remaining, some cards have not even made one trip through yet, $2(1024 - 1000) = 48$, to be exact. Once these cards go through, 1999 will be the $512 - 48 = 464^\text{th}$ card on the deck. Since every other card was removed during the first round, it goes to show that 1999 was in position $464 \times 2 = 928$, meaning that there were $\boxed{927}$ cards are above the one labeled $1999$.

Solution 2

To simplify matters, we want a power of $2$. Hence, we will add $48$ 'fake' cards which we must discard in our actual count. Using similar logic as Solution 1, we find that 1999 has position $1024$ in a $2048$ card stack, where the fake cards towards the front.

Let the fake cards have positions $1, 3, 5, \cdots, 95$. Then, we know that the real cards filling the gaps between the fake cards must be the cards such that they go to their correct starting positions in the $2000$ card case, where all of them are below $1999$. From this, we know that the cards from positions $1$ to $96$ alternate in fake-real-fake-real, where we have the correct order of cards once the first $96$ have moved and we can start putting real cards on the table. Hence, $1999$ is in position $1024 - 96 = 928$, so $\boxed{927}$ cards are above it. - Spacesam

Solution 3 (Recursion)

Consider the general problem: with a stack of $n$ cards such that they will be laid out $1, 2, 3, ..., n$ from left to right, how many cards are above the card labeled $n-1$?

Let $a_n$ be the answer to the above problem.

As a base case, consider $n=2$. Clearly, the stack, from top to bottom, must be $(1, 2)$, so $a_2=0$.

Next, let's think about how we can construct a stack of $n+1$ cards from a stack of $n$ cards. First, let us renumber the current stack of $n$ by adding $1$ to the label of each of the cards. Then we must add a card labeled "$1$" somewhere in the new deck.

Working backwards, we find that we must move the bottom card to the top, then add "$1$" to the top of the deck. This is because after one move, the number "$1$" will be laid out and the top card will be moved to the bottom, so the deck becomes the same as what we had before, but with everything renumbered correctly such that $2, 3, 4, ...$ will then be laid out in order.

Therefore, if $a_n \ne n-1$ (meaning the card $n-1$ is not at the bottom of the deck and so it won't be moved to the top), then $a_{n+1} = a_n + 2$, since a card from the bottom is moved to be above the $n-1$ card, and the new card "$1$" is added to the top. If $a_n = n-1$ (meaning the card $n-1$ is the bottom card), then $a_{n+1}=1$ because the $n-1$ card will move to the top and the card "$1$" will be added on top of it.

With these recursions and the base case we found earlier, we calculate $a_{2000} = \boxed{927}$. To calculate this by hand, a helpful trick is finding that if $a_n=1$, then $a_{2n-1}=1$ as well. Once we find $a_{1537}=1$, the answer is just $1+(2000-1537)\cdot2$. - Frestho

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

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=2000_AIME_I_Problems/Problem_15&oldid=158687"