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?

Initially I thought representation as binary might help (and indeed it might if understood in enough depth), but the fact that 2000 is not a power of 2 complicates the situation.

DEFINT A-Z
DIM used(2000)
DIM table(2000)

DO
    DO
     upto = upto + 1
     IF upto > 2000 THEN upto = 1
     IF used(upto) = 0 THEN EXIT DO
    LOOP
    place = place + 1
    table(place) = upto
    used(upto) = 1
    IF place = 2000 THEN EXIT DO
    DO
     upto = upto + 1
     IF upto > 2000 THEN upto = 1
     IF used(upto) = 0 THEN EXIT DO
    LOOP
LOOP

FOR i = 1 TO 2000
  PRINT USING "#### "; table(i);
  b$ = ""
  n = table(i)
  FOR j = 1 TO 11
    b$ = LTRIM$(STR$(n MOD 2)) + b$
    n = n \ 2
  NEXT
  PRINT b$

  IF i MOD 40 = 0 OR table(i) = 2000 THEN DO: LOOP UNTIL INKEY$ > ""
NEXT

I show the positions of the last several numbers placed on the table, with binary representation also:

1152 10010000000
1216 10011000000
1280 10100000000
1344 10101000000
1408 10110000000
1472 10111000000
1536 11000000000
1600 11001000000
1664 11010000000
1728 11011000000
1792 11100000000
1856 11101000000
1920 11110000000
1984 11111000000
  96 00001100000
 224 00011100000
 352 00101100000
 480 00111100000
 608 01001100000
 736 01011100000
 864 01101100000
 992 01111100000
1120 10001100000
1248 10011100000
1376 10101100000
1504 10111100000
1632 11001100000
1760 11011100000
1888 11101100000
  32 00000100000
 288 00100100000
 544 01000100000
 800 01100100000
1056 10000100000
1312 10100100000
1568 11000100000
1824 11100100000
 160 00010100000
 672 01010100000
1184 10010100000
1696 11010100000
 416 00110100000
1440 10110100000
 928 01110100000
1952 11110100000

so the 1999, the next to last placed, was originally the 928th card from the top, with 927 cards above it.

The sequence of deck positions of numbers placed on the table starts at 1 with increments of 2, then starting again at 2 with increments of 4, then starting with 4 with increments of 8, then starting with 8 with increments of 16 and then starting with 16 with increments of 32. But then the next one starts with 64 with increments of 64, followed by 96 with increments of 128 and then 32 with increments of 256, etc.

The break with regularity occurred just as the last card in the original deck was placed.

Posted by Charlie on 2009-01-04 15:04:56