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 AZ
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 20090104 15:04:56 