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?

We can see in the starting pile, the first card (top card) in the pile is 1, the third card is 2, the fifth card is 3, and so on. However, once these are placed, we have the same situation, except starting with 1000 cards instead of 2000.

Thus, we can see the bottom thousand cards in the pile correspond to numbers with a 0 on the right of their binary representation. The bottom five hundred cards corrospond to numbers with a 00 on the right of their binary representation, and so on.

The accomodation required since 2000 is not a multiple of 2, is that after dealing an odd number of cards (ie one hundred twenty five), the next card will go under the pile instead of on the table, thus the roles of 1 and 0 are changed.

Posted by Gamer on 2009-01-04 18:06:51