Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
add comment

2 Answers 2

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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