There are n playing cards lined up face-down in a row. Every turn, a pair of adjacent cards with the left card face-down is randomly selected (i.e., a pair of cards has no chance of being selected if the left card is face-up, otherwise all pairs are equally likely to be selected). Both cards are then flipped over (face-down to face-up or face-up to face-down).
Prove that after enough turns, it will eventually be impossible to select a pair of cards with the left card face-down.
When you reach this card flipping endgame, will the rightmost card be face-up or face-down?
Solution
Represent the row of cards using binary numbers: 1 for face-down cards and 0 for face-up cards. So you would start with a n-digit number like 111…11.
When you flip over a pair with the left card face-down, either 11 becomes 00 or 10 becomes 01 – either way, it means the number becomes strictly smaller, so eventually the number will reach 1 or 0 and it will be impossible to select any more pairs like this.
Notice that when you flip over a pair, the number of face-down cards either stays the same (10 to 01) or decreases by exactly two (11 to 00). That means if the number of face-down cards was initially odd, the number of face-down cards will always be odd. That means the rightmost card will be face-down if n was odd, and face-up if n was even.