Difference between revisions of "2000 AIME I Problems/Problem 15"
(→Solution 4 (very bashy)) |
(→Solution 3 (Recursion on number of cards below 1999)) |
||
| (13 intermediate revisions by 2 users not shown) | |||
| Line 2: | Line 2: | ||
A stack of <math>2000</math> cards is labelled with the integers from <math>1</math> to <math>2000,</math> 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: <math>1,2,3,\ldots,1999,2000.</math> In the original stack of cards, how many cards were above the card labeled <math>1999</math>? | A stack of <math>2000</math> cards is labelled with the integers from <math>1</math> to <math>2000,</math> 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: <math>1,2,3,\ldots,1999,2000.</math> In the original stack of cards, how many cards were above the card labeled <math>1999</math>? | ||
| − | == Solution == | + | == Solution 1 == |
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>. | 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>. | ||
| Line 10: | Line 10: | ||
Let the fake cards have positions <math>1, 3, 5, \cdots, 95</math>. 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 <math>2000</math> card case, where all of them are below <math>1999</math>. From this, we know that the cards from positions <math>1</math> to <math>96</math> alternate in fake-real-fake-real, where we have the correct order of cards once the first <math>96</math> have moved and we can start putting real cards on the table. Hence, <math>1999</math> is in position <math>1024 - 96 = 928</math>, so <math>\boxed{927}</math> cards are above it. - Spacesam | Let the fake cards have positions <math>1, 3, 5, \cdots, 95</math>. 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 <math>2000</math> card case, where all of them are below <math>1999</math>. From this, we know that the cards from positions <math>1</math> to <math>96</math> alternate in fake-real-fake-real, where we have the correct order of cards once the first <math>96</math> have moved and we can start putting real cards on the table. Hence, <math>1999</math> is in position <math>1024 - 96 = 928</math>, so <math>\boxed{927}</math> cards are above it. - Spacesam | ||
| − | ==Solution 3 (Recursion)== | + | ==Solution 3 (Recursion on number of cards below 1999)== |
| + | We work backwards. To reverse the process, we must move the bottom card to the top, and add a new number to the top. Let <math>d_n</math> equal the number of cards below 1999 after <math>n</math> process reversals. Reversing one process, our deck only has <math>2000</math>, so we reverse again to obtain <math>1999, 2000</math>. So, <math>d_2 = 1</math>. When <math>d_{n-1} > 0</math>, after a process reversal, the bottom card is moved to the top (it goes above <math>1999</math>), so we subtract by one to account for this (the addition of the new card doesn't matter since it goes above <math>1999</math>), giving us <math>d_n = d_{n-1} - 1</math>. So, <math>d_3 = 0</math>. Then, when <math>d_{n-1} = 0</math>, after a process reversal, <math>1999</math> moves to the top and one more card is added above <math>1999</math>. Since at <math>d_{n}</math>, <math>n</math> cards have been added, there must be <math>n - 2</math> cards below <math>1999</math>. So, <math>d_4 = 2</math>. Then, consider all <math>d_{n-1} = 0</math>. Then, <math>d_n = n-2</math> as previously stated. After <math>n-2</math> process reversals, we go back to <math>d_{2n - 2} = n - 2 - (n - 2) = 0</math>. Then, <math>d_{2n-1} = 2n - 3</math>. Next, we can simply calculate <math>2 \cdot 4 - 1 = 7</math>, <math>2 \cdot 7 - 1 = 13</math>, and so on (which is a very simple bash, as <math>2000</math> is a small number. If you don't want to do this, define sequence <math>a_n = 2a_{n-1} - 1</math>, and solve for the closed form, which is very easy). Consequently, we derive <math>d_{1537} = 1537 - 2 = 1535</math>. <math>2000 - 1537 = 463</math> steps remain. So, <math>d_{2000} = d_{1537} - 463 = 1072</math>. Finally, there are <math>2000 - 1 - 1072 = \boxed{\textbf{927}}</math> numbers above <math>1999</math>. | ||
| + | |||
| + | ~[https://artofproblemsolving.com/wiki/index.php?title=User:Crazyvideogamez CrazyVideoGamez] | ||
| + | |||
| + | ==Solution 4 (Recursion)== | ||
Consider the general problem: with a stack of <math>n</math> cards such that they will be laid out <math>1, 2, 3, ..., n</math> from left to right, how many cards are above the card labeled <math>n-1</math>? | Consider the general problem: with a stack of <math>n</math> cards such that they will be laid out <math>1, 2, 3, ..., n</math> from left to right, how many cards are above the card labeled <math>n-1</math>? | ||
| Line 26: | Line 31: | ||
- Frestho | - Frestho | ||
| − | ==Solution | + | ==Solution 5 (very bashy)== |
Let us treat each run through the deck as a separate "round". For example, in round one, you would go through all of the <math>2000</math> cards initially in the deck once, in round two, you would go through all <math>1000</math> cards initially in the deck once, so on and so forth. For each round, let us record what the initial and final actions are (<math>r</math> for moving the card to the right, <math>b</math> for moving the card to the bottom), the number of cards moved to the right, the number of cards left, and what the position of the cards moved to the right were in the original <math>2000</math> card deck (as <math>n = a + ck</math> where <math>n</math> is the position, <math>c</math> is the spacing of the cards moved, <math>a</math> is an integer such that the correct first card is moved, and <math>k</math> is an integer greater than or equal to <math>1</math> which represents which card out of all the cards moved to the right you are finding the position of). Then, | Let us treat each run through the deck as a separate "round". For example, in round one, you would go through all of the <math>2000</math> cards initially in the deck once, in round two, you would go through all <math>1000</math> cards initially in the deck once, so on and so forth. For each round, let us record what the initial and final actions are (<math>r</math> for moving the card to the right, <math>b</math> for moving the card to the bottom), the number of cards moved to the right, the number of cards left, and what the position of the cards moved to the right were in the original <math>2000</math> card deck (as <math>n = a + ck</math> where <math>n</math> is the position, <math>c</math> is the spacing of the cards moved, <math>a</math> is an integer such that the correct first card is moved, and <math>k</math> is an integer greater than or equal to <math>1</math> which represents which card out of all the cards moved to the right you are finding the position of). Then, | ||
| Line 54: | Line 59: | ||
This card must be labeled 1999 since it is second to last. Then, since it is the <math>58th</math> in the deck of <math>125</math>, it must be the <math>58 * 8 = 928th</math> card in the original deck, and because we've been numbering from the top of the deck to the bottom (also because AIME answers are 000-999), there were <math>928 - 1 = \boxed{927}</math> cards above it in the deck - Romulus and minimaxweii | This card must be labeled 1999 since it is second to last. Then, since it is the <math>58th</math> in the deck of <math>125</math>, it must be the <math>58 * 8 = 928th</math> card in the original deck, and because we've been numbering from the top of the deck to the bottom (also because AIME answers are 000-999), there were <math>928 - 1 = \boxed{927}</math> cards above it in the deck - Romulus and minimaxweii | ||
| + | |||
| + | ==Solution 6 (Bashing with Modular Arithmetic)== | ||
| + | Similar to Solution 5, we treat each run-through of the deck from the lowest-indexed card to the highest-indexed card as a separate round. Notice that after each round, approximately half the deck will remain, with the other half having been cast aside to the right in sorted order. Then, we can model each round as if we are running a "Sieve" through the deck with powers of 2s, filtering out the cards to put to the right and the cards to be pushed to the bottom. | ||
| + | |||
| + | At the beginning, when all <math>2000</math> cards are still in the deck, notice that the first run-through of the deck consists of removing all the cards such that their index <math>I\equiv 1\pmod{2}</math>, while we leave behind all the cards such that their index <math>I\equiv 2\pmod{2}</math>. (Since the cards are not <math>0</math>-indexed, using <math>2</math> instead of <math>0\pmod{2}</math> is simpler to keep track of the cards. This will appear again later.) The remaining <math>1000</math> cards, then, will all share the attribute that their index numbers are even. To split this further for round 2, we look more specifically at each index, categorizing them further as <math>I\equiv 2\pmod 4</math> or <math>I\equiv 4\pmod 4</math> in that order (The card with the smaller remainder will always be the card on the top of the new deck). Then, in Round 2, we will remove all the cards with index values that leave a remainder of <math>2</math> when divided by <math>4</math>, while leaving the multiples of <math>4</math> behind. Notice that each time, in each new deck, we are removing all the cards with an odd position in that specific deck, and leaving behind all the cards with an even position in that specific deck. | ||
| + | |||
| + | This process will continue until we reach Round 5, where the number of cards that remain (<math>125</math>) is no longer a multiple of 2. Therefore, when we remove all the cards with indices <math>I\equiv 16\pmod{32}</math> and leave behind all the cards with indices <math>I\equiv 32\pmod{32}</math>, the last card in the deck will be removed instead of being placed to the bottom, with <math>125-63=62</math> cards remaining. Because of this, when Round 6 begins, we cannot follow our normal procedure, since the top card of the Round 6 deck would have been moved to the bottom! Therefore, when we are using our sieve with <math>I\equiv 32\pmod{64}</math> and <math>I\equiv 64\pmod{64}</math>, the order at which the remainders are presented have flipped, so all the cards with indices that are multiples of 64 will be removed, while all the cards with indices that are 32 more than a multiple of 64 will remain. The <math>62</math> cards from Round 6 will be reduced to <math>31</math>, and the last card in the deck will be removed just like in Round 5, which means Round 7 will be affected the same way. Of the choices of <math>I\equiv 32\pmod{128}</math> and <math>I\equiv 32+64=96\pmod{128}</math>, we will remove the latter, leaving behind the cards with indices that are 32 more than a multiple of 128. However, since 31 is an odd number, the last card of the deck will NOT be removed, which means our sieving process will return to normal after Round 7, with <math>31-15=16</math> cards remaining. Since <math>16</math> is a perfect power of <math>2</math>, we will not need to worry about this scenario again in the following rounds. | ||
| + | |||
| + | Round 8: <math>I\equiv 32\pmod{256}</math> removed; <math>I\equiv 32+128=160\pmod{256}</math> remains; <math>16-8=8</math> cards left. | ||
| + | |||
| + | Round 9: <math>I\equiv 160\pmod{512}</math> removed; <math>I\equiv 160+256=416\pmod{512}</math> remains; <math>8-4=4</math> cards left. | ||
| + | |||
| + | Round 10: <math>I\equiv 416\pmod{1024}</math> removed; <math>I\equiv 416+512=928\pmod{1024}</math> remains; <math>4-2=2</math> cards left. | ||
| + | |||
| + | Round 11: <math>I\equiv 928\pmod{2048}</math> removed; <math>I\equiv 928+1024=1952\pmod{2048}</math> remains; <math>2-1=1</math> card left. | ||
| + | |||
| + | Round 12: The last card in position <math>1952</math> is sorted into place (This is card #<math>2000</math>!). | ||
| + | |||
| + | It is obvious that the single card put into place in Round 11 is the second-to-last card in the deck, which is our target #<math>1999</math>. Then, its position in the original deck leaves a remainder of <math>928</math> when divided by <math>2056</math>. It is easy to see that <math>928</math> is the only index that satisfies this, so there will be <math>928-1=\boxed{927}</math> cards above card #<math>1999</math>. | ||
| + | |||
| + | ~chz3369 | ||
== See also == | == See also == | ||
{{AIME box|year=2000|n=I|num-b=14|after=Last Question}} | {{AIME box|year=2000|n=I|num-b=14|after=Last Question}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
Latest revision as of 18:16, 6 January 2024
Contents
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 
?
Solution 1
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, 
, to be exact. Once these cards go through, 1999 will be the 
card on the deck. Since every other card was removed during the first round, it goes to show that 1999 was in position 
, meaning that there were 
cards are above the one labeled .
Solution 2
To simplify matters, we want a power of 
. Hence, we will add 
'fake' cards which we must discard in our actual count. Using similar logic as Solution 1, we find that 1999 has position 
in a 
card stack, where the fake cards towards the front.
Let the fake cards have positions 
. 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 card case, where all of them are below . From this, we know that the cards from positions to 
alternate in fake-real-fake-real, where we have the correct order of cards once the first have moved and we can start putting real cards on the table. Hence, is in position 
, so cards are above it. - Spacesam
Solution 3 (Recursion on number of cards below 1999)
We work backwards. To reverse the process, we must move the bottom card to the top, and add a new number to the top. Let 
equal the number of cards below 1999 after 
process reversals. Reversing one process, our deck only has , so we reverse again to obtain 
. So, 
. When 
, after a process reversal, the bottom card is moved to the top (it goes above ), so we subtract by one to account for this (the addition of the new card doesn't matter since it goes above ), giving us 
. So, 
. Then, when 
, after a process reversal, moves to the top and one more card is added above . Since at 
, cards have been added, there must be 
cards below . So, 
. Then, consider all . Then, 
as previously stated. After 
process reversals, we go back to 
. Then, 
. Next, we can simply calculate 
, 
, and so on (which is a very simple bash, as is a small number. If you don't want to do this, define sequence 
, and solve for the closed form, which is very easy). Consequently, we derive 
. 
steps remain. So, 
. Finally, there are 
numbers above .
Solution 4 (Recursion)
Consider the general problem: with a stack of cards such that they will be laid out 
from left to right, how many cards are above the card labeled 
?
Let 
be the answer to the above problem.
As a base case, consider 
. Clearly, the stack, from top to bottom, must be 
, so 
.
Next, let's think about how we can construct a stack of 
cards from a stack of cards. First, let us renumber the current stack of by adding to the label of each of the cards. Then we must add a card labeled "" somewhere in the new deck.
Working backwards, we find that we must move the bottom card to the top, then add "" to the top of the deck. This is because after one move, the number "" 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 
will then be laid out in order.
Therefore, if 
(meaning the card is not at the bottom of the deck and so it won't be moved to the top), then 
, since a card from the bottom is moved to be above the card, and the new card "" is added to the top. If 
(meaning the card is the bottom card), then 
because the card will move to the top and the card "" will be added on top of it.
With these recursions and the base case we found earlier, we calculate 
. To calculate this by hand, a helpful trick is finding that if 
, then 
as well. Once we find 
, the answer is just 
.
- Frestho
Solution 5 (very bashy)
Let us treat each run through the deck as a separate "round". For example, in round one, you would go through all of the cards initially in the deck once, in round two, you would go through all 
cards initially in the deck once, so on and so forth. For each round, let us record what the initial and final actions are (
for moving the card to the right, 
for moving the card to the bottom), the number of cards moved to the right, the number of cards left, and what the position of the cards moved to the right were in the original card deck (as 
where is the position, 
is the spacing of the cards moved, 
is an integer such that the correct first card is moved, and 
is an integer greater than or equal to which represents which card out of all the cards moved to the right you are finding the position of). Then,
Round 1: to , to right, left in deck, 
,
Round 2: to , 
to right, left in deck, 
,
Round 3: to , 
to right, left in deck, 
,
Round 4: to , 
to right, left in deck, 
.
Let us treat the remaining deck of cards as a totally independent deck, note that the positions of card in this deck are 
. Also note that the first action of a new round is never the same action as the last action of the previous round because actions alternate. Also note that for every new round, the spacing between cards moved doubles, and that the cards remaining in the beginning of a new round have position 
for the values 
of the previous round. Also note that if there are an odd number of cards in an initial deck, the first and last actions are the same. Then,
Round 5: to , 
to right, 
left in deck, ,
Round 6: to , 
to right, left in deck, 
, because 
positioned cards are left at the beginning of this round and the first card is sent to the bottom, only every second card is sent to the right, and because spacing doubles every round,
Round 7: to , 
to right, 
left in deck, 
, because 
positioned cards are left at the beginning and only every second card is sent to the right, and because spacing doubles every round,
Round 8: to , 
to right, left in deck, 
, by similar reasoning, since the cards 
are left and spacing doubles every round, from here on things get real easy,
Round 9: to , 
to right, left in deck, 
,
Round 10: to , to right, left in deck, 
,
Round 11: to , to right, left in deck, 
, since 
.
This card must be labeled 1999 since it is second to last. Then, since it is the 
in the deck of , it must be the 
card in the original deck, and because we've been numbering from the top of the deck to the bottom (also because AIME answers are 000-999), there were 
cards above it in the deck - Romulus and minimaxweii
Solution 6 (Bashing with Modular Arithmetic)
Similar to Solution 5, we treat each run-through of the deck from the lowest-indexed card to the highest-indexed card as a separate round. Notice that after each round, approximately half the deck will remain, with the other half having been cast aside to the right in sorted order. Then, we can model each round as if we are running a "Sieve" through the deck with powers of 2s, filtering out the cards to put to the right and the cards to be pushed to the bottom.
At the beginning, when all cards are still in the deck, notice that the first run-through of the deck consists of removing all the cards such that their index 
, while we leave behind all the cards such that their index 
. (Since the cards are not 
-indexed, using instead of 
is simpler to keep track of the cards. This will appear again later.) The remaining cards, then, will all share the attribute that their index numbers are even. To split this further for round 2, we look more specifically at each index, categorizing them further as 
or 
in that order (The card with the smaller remainder will always be the card on the top of the new deck). Then, in Round 2, we will remove all the cards with index values that leave a remainder of when divided by , while leaving the multiples of behind. Notice that each time, in each new deck, we are removing all the cards with an odd position in that specific deck, and leaving behind all the cards with an even position in that specific deck.
This process will continue until we reach Round 5, where the number of cards that remain () is no longer a multiple of 2. Therefore, when we remove all the cards with indices 
and leave behind all the cards with indices 
, the last card in the deck will be removed instead of being placed to the bottom, with 
cards remaining. Because of this, when Round 6 begins, we cannot follow our normal procedure, since the top card of the Round 6 deck would have been moved to the bottom! Therefore, when we are using our sieve with 
and 
, the order at which the remainders are presented have flipped, so all the cards with indices that are multiples of 64 will be removed, while all the cards with indices that are 32 more than a multiple of 64 will remain. The cards from Round 6 will be reduced to , and the last card in the deck will be removed just like in Round 5, which means Round 7 will be affected the same way. Of the choices of 
and 
, we will remove the latter, leaving behind the cards with indices that are 32 more than a multiple of 128. However, since 31 is an odd number, the last card of the deck will NOT be removed, which means our sieving process will return to normal after Round 7, with 
cards remaining. Since is a perfect power of , we will not need to worry about this scenario again in the following rounds.
Round 8: 
removed; 
remains; 
cards left.
Round 9: 
removed; 
remains; 
cards left.
Round 10: 
removed; 
remains; 
cards left.
Round 11: 
removed; 
remains; 
card left.
Round 12: The last card in position 
is sorted into place (This is card #!).
It is obvious that the single card put into place in Round 11 is the second-to-last card in the deck, which is our target #. Then, its position in the original deck leaves a remainder of 
when divided by 
. It is easy to see that is the only index that satisfies this, so there will be 
cards above card #.
~chz3369
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. 
