jump to navigation

Problem of the Day #296: Card Shuffling, Part II January 9, 2012

Posted by Alex in : potd , trackback

Everyday, Albert is shuffling his cards. He uses this procedure:

1) Divide the deck evenly into two piles. If there is an odd number of cards, Albert eats the leftover card.
2) As long as both of the two piles contain cards, randomly choose one of the piles and place the top card of that pile into the shuffled deck.
3) When one of the two piles runs out, take the K remaining cards of the single pile and throw them away.

Today, Albert wants to shuffle 2012 cards. What is the expected number of shuffles needed to reduce the size of the deck to zero?

Comments»

1. Seungln - January 10, 2012

Everyday he’s (still) shufflin’.