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?

Imagine for a moment that there's a marker of some sort placed at the bottom of the deck and moved to the bottom again whenever it appears. This is just a convenient way to identify how many passes through the deck have been made and changes nothing about the problem.

Also note that by moving cards to the bottom of the pile the relative order of those cards is unchanged -- the first card so moved is above the next and so on.

After the first pass, 1000 of the 2000 cards are placed, and the cards in even positions remain in the deck, order unchanged.

After the second pass, 500 of the remaining cards are placed, and the cards still in the even positions (which were therefore in positions = 0 mod 4 in the original deck) again remain in the deck unchanged.

Ditto for the third pass which lays out 250 more cards and leaves cards originally in positions = 0 mod 8 in the deck and again for the fourth pass which lays out 125 more cards and leaves cards originally in positions  = 0 mod 16 in the deck.

Now it gets more interesting.

On the fifth pass, with an odd number of cards, 62 cards are laid out and 62 moved to the bottom of the deck (making 124) and then the 125th card is laid out. The NEXT run through the deck, then, starts with moving a card to the bottom instead of with laying a card out since our division into "passes" is an artificial one -- in real life the deck is continuously dealt. That means after pass 5 there are 62 cards remaining which were all originally in 0 mod 32 positions and the sixth pass is different.

The sixth pass starts with moving a card to the back, and so moves a total of 31 cards to the back and lays out 31 cards. The cards so moved are those that are in even positions mod 32 but odd positions mod 64 in the original deck so these are positions that are 32 mod 64.

The seventh pass starts like the sixth and puts 15 more cards back, laying out 15 more, and then puts an additional 16th card to the back. The 16 cards remaining are those that were in odd positions, so they're = 32 mod 128. And now we're back to the original parity of layout first then pushing to the back.

The eigth pass lays out 8 more cards, leaving 8 that were in positions 32+128 mod 256

The ninth pass lays out 4 cards, leaving 4 and that were in positions 32+128+256 mod 512 

The tenth pass lays out 2 of the last four cards, leaving those originally in positions 32+128+256+512 mod 1024.

In the eleventh pass, the top card is laid out and then the bottom (technically the bottom is placed beneath itself and then laid out but that doesn't change anything.) So the penultimate card is the TOP card in pass ten and is in position 32+128+256+512 = 928 of 2000. This is card 1999 and so it must have started out with 927 cards above it. (The 2000th card is of course 1024 later at position 1952.)

It's interesting to note that the numbers summed to find the positions of the last two cards are the same as the "1" bits in the binary representation of 2000 shifted left once. 2000 = 111 1101 0000 and 928 = 1 1101 00000. Perhaps this can be generalized to find the position of the final two cards in a deck of size N dealt out in this manner?

Posted by Paul on 2009-01-05 17:39:13