A problem from the 2000 Moscow Mathematical Olympiad:
Some of the cards in a deck are face down and some are face up. From time to time Pete draws out a group of one or more contiguous cards in which the first and last are both face down. He turns over this group as a unit and returns it to the deck in the position from which he drew it. Prove that eventually all the cards in the deck will be face up, no matter how Pete proceeds.
|
SelectClick for Answer |
Assign a digit to each card in the deck, 1 if face up and 2 if face down, working from top to bottom. If these digits are assembled in order, they produce one long number that encodes the arrangement of the cards. For example, if all the cards were face down then this number would be 2222 … 222.
After each of Pete’s operations the value of this number decreases, because the leftmost, or highest-value, digit changes from 2 to 1.
Because there are finitely many n-digit numbers available, this process cannot continue forever. The encoded number must eventually arrive at 1111 … 111, where all the cards are face up.
|
