# A less challenging trivia problem

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

-
I don't know the original source of this problem, but I first saw it in the Australian Math Society Gazette, austms.org.au/Publ/Gazette/2008/Mar08/PuzzleCorner.pdf --- solutions would be in a later issue. – Gerry Myerson Nov 20 '12 at 6:00
Adding an exactly equal problem (math.stackexchange.com/questions/241409/card-game-problem) do not help. Just ask where are you stuck here, there are no problem in giving more hint. – carlop Nov 20 '12 at 17:04
A generalization on the no.of players will give us that it should always be an odd number to achieve the required state. Isn't it ? – Milli Nov 21 '12 at 7:26
@GerryMyerson: Actually, your solution was published in the later issue :-) austms.org.au/Publ/Gazette/2008/Jul08/PuzzleCorner.pdf – joriki Oct 9 '15 at 10:42
See also my anwer to Ross's follow-up question on the maximum length of the game. – joriki Oct 9 '15 at 10:43

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.

-

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.

-