Home > General
| 2000 cards (Posted on 2009-01-04) |
 |
There are cards labeled from 1 to 2000. The cards are arranged and placed in a pile.
The top card is placed on the table, then the next card at the bottom of the pile.
Then the next card is placed on the table to the right of the first card, and the next card is placed at the bottom of the pile.
This process is continued until all the cards are on the table.
The final order (from left to right) is 1, 2, 3, ... , 2000.
In the original pile, how many cards were above card labeled 1999?
|
|
Submitted by pcbouhid
|
|
No Rating
|
|
|
Solution:
|
(Hide)
|
Work backwards.
It is easy to see that shortly before the end, the pile is 1998, 2000, 1999.
Move 1999 to the top and put 1997 above it, giving 1997, 1999, 1998, 2000.
Move 2000 to the top and put 1996 above it, giving 1996, 2000, 1997, 1999, 1998.
Move 1998 to the top and put 1995 above it, giving 1995, 1998, 1996, 2000, 1997, 1999.
Now denote the state by (n, m), where the pile has n cards and there are m below the 1999. We see that (n, m) is preceded by (n+1, m-1) for m > 0, and (n, 0) is preceded by (n+1, n-1).
Thus from (3, 0) we went to (4, 2), (5, 1), (6, 0), (7, 5), ... , (12, 0), ... , (24, 0), ... , (48, 0), ... , (96, 0), ... , (192, 0), ..., (384, 0), ... , (768, 0), ... , (1536, 0), (1537, 1535), (1538, 1534), (1539, 1533), ... , (2000, 1072).
Hence at the start there are 2000 - 1073 = 927 cards above 1999.
|
Comments: (
You must be logged in to post comments.)
|
|
Please log in:
Forums (0)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (12)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
|
