Tuesday, March 14, 2006

Card Tricks. Topic: Logic. Level: Olympiad.

Problem: (2005 MOP Lecture, Reid Barton) A deck of $ 50 $ cards contains two cards labeled $ n $ for each $ n = 1, 2, . . . , 25 $. There are $ 25 $ people seated at a table, each holding two of the cards in this deck. Each minute every person passes the lower-numbered card of the two they are holding to the right. Prove that eventually someone has two cards of the same number.

Solution: This is an interesting problem, which requires a little more than just math to figure out; it's a lot more logic, in fact.

Consider the position of the cards numbered $ 25 $. If a single person holds both, we are done. Or else, they don't move at all (since they are the biggest).

Next consider the position of the cards numbered $ 24 $. Again a single person cannot hold them, or we're done. The only way these can be passed is if someone holds both $ 24 $ and $ 25 $. But then, after a finite number of passes, the cards numbered $ 24 $ will not be passed anymore (since there are only two cards bigger).

Similarly, the cards numbered $ 23, 22, \ldots, 14 $ will be stationary after a finite number of passes (since there are at most $ 22 $ cards bigger than any of them).

Clearly, once all $ 24 $ of these cards are stationary, they must be held by different people. Call the person without one of these cards $ P $.

Then we look at the cards numbered $ 13 $. They will be passed on every move unless person $ P $ obtains it, which must happen in a finite number of moves. After person $ P $ obtains one of the cards, he or she does not pass it because the bigger cards are already distributed among the other people. Hence the other card numbered $ 13 $ will eventually reach person $ P $ as well.

Thus eventually someone will be holding two cards of the same number. QED.

--------------------

Comment: We note that this problem can be extended from $ 25 $ to any odd integer by the same argument. The key to this problem was realizing that the big cards have a lot less possibility of moving (seems obvious) so it's not difficult to "monitor" them.

--------------------

Practice Problem: (2005 MOP Lecture, Reid Barton) A deck contains $n$ cards labeled $1, 2, . . . , n$. Starting with an arbitrary ordering of the cards, repeat the following operation: if the top card is labeled $k$, reverse the order of the top $k$ cards. Prove that eventually the top card will be labeled $1$.

No comments:

Post a Comment