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?

(In reply to non-computer solution by Paul)

Here are some samples of the original positions of the last two cards on the table, for random deck sizes between 1000 and 2000.

For example, the first set indicates that for a deck size of 1473, the last two on the table (the 1472nd and 1473rd) came from positions 1410 and 898 in the original deck. The binary equivalents are to the right.  There's a pattern, but not exactly the same at the left side in each instance.

1473 10111000001
1410 10110000010
 898 01110000010

1089 10001000001
 642 01010000010
 130 00010000010

1332 10100110100
1128 10001101000
 616 01001101000

1765 11011100101
 458 00111001010
1482 10111001010

1671 11010000111
 270 00100001110
1294 10100001110

1274 10011111010
1012 01111110100
 500 00111110100

1687 11010010111
 302 00100101110
1326 10100101110

1224 10011001000
 912 01110010000
 400 00110010000

1970 11110110010
 868 01101100100
1892 11101100100

1600 11001000000
 128 00010000000
1152 10010000000

1291 10100001011
1046 10000010110
 534 01000010110

1908 11101110100
 744 01011101000
1768 11011101000

1002 01111101010
 468 00111010100
 980 01111010100

1737 11011001001
 402 00110010010
1426 10110010010

1685 11010010101
 298 00100101010
1322 10100101010

1815 11100010111
 558 01000101110
1582 11000101110

1191 10010100111
 846 01101001110
 334 00101001110

1699 11010100011
 326 00101000110
1350 10101000110

1459 10110110011
1382 10101100110
 870 01101100110

1768 11011101000
 464 00111010000
1488 10111010000

1758 11011011110
 444 00110111100
1468 10110111100

1970 11110110010
 868 01101100100
1892 11101100100

1978 11110111010
 884 01101110100
1908 11101110100

1458 10110110010
1380 10101100100
 868 01101100100

Posted by Charlie on 2009-01-05 19:27:42