3
$\begingroup$

There are 25 people sitting around a table and each person has two cards. One of the numbers 1,2,..., 25 is written on each card, and each number occurs on exactly two cards. At a signal, each person passes one of her cards, the one with the smaller number to her right hand neighbor. Prove that sooner or later, one of the players will have two cards with the same numbers.

I am thinking it will have to do with the 12 and 13 card because there is a 50% chance of giving it to their partner but I can't find a way to back that up

$\endgroup$
4
$\begingroup$

Edited: The two $25$'s must be separate (or we already have a match)and are stationary. Each $24$ can only move twice, as it can only move when matched with a $25$. After two moves, the $24$s are stationary (or they get matched and we are done.) Now the $23$'s can only move four times. Going on like this, all the cards above $13$ come to rest somewhere, actually much faster than this, occupying $24$ spaces. Each of the $13$'s gets passed to the remaining hand and must match.

I will be posting a follow-up regarding the maximum number of moves.

$\endgroup$
1
$\begingroup$

Let $\Large a_{min}(i)$ be equal to minimal card value on hands of person #i.
Let $\Large a_{max}(i)$ be equal to maximal card value on hands of person #i.
Let $\Large A_{max}=\sum_{i=1}^{25}a_{max}(i)$
$\Large A_{max}$ is limited by some constant (say, 25*25) and can not decrease during the game.
Thus, sooner or later $\Large A_{max}$ would stay unchanged during 25 moves.
This implies that $\Large\forall\ i,j\ \ \ a_{min}(i)\lt a_{max}(j)$, which is impossible due to two cards having median value 13.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.