## 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$.