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.

Quoting from this question:

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.

We presume there is no match originally or the game ends with zero passes.

Egor Skriptunoff and I showed the game terminates, but Egor's answer doesn't give a number of moves and mine is quadratic in the number of players (it gives a limit of $90$ moves for $25$ players due to ignoring the overlap of the times placing the lower numbers with the times placing the higher numbers). How many is the true maximum?

The best I can do is $24$ moves for a $25$ player game. Call any card below $13$ Low and any above $13$ High. Give player $1$ a $13$ and a Low. Give player $2$ a High and a $13$. Give all others a High and a Low. The second mentioned cards will rotate around until the second $13$ gets to player $1$. I believe this is maximal, but cannot prove it. Similarly, if we give players $1$ and $25$ a $13$ and a Low, players $2-13$ two Highs, and players $14-24$ two Lows (making sure we never pair Highs or Lows) the front edge of the highs moves forward every other turn and the $13$ moves from $25$ to $1$ at move $24$.

If we choose player $1$ to be the one who eventually matches the $13$'s, he can never have a High card and so cannot pass on a $13$. The other $13$ can only be $24$ spaces away, but it could get stuck waiting for a push from a High behind it. I think it can only get stuck as many turns as it is closer to player $1$.

share|improve this question
    
I guess it's not easy to get a good bound out of my solution at austms.org.au/Publ/Gazette/2008/Jul08/PuzzleCorner.pdf –  Gerry Myerson Nov 27 '12 at 1:42
    
@GerryMyerson: In fact, I wrote almost the same in response to the original question. I believe it leads to the upper limit of $90$ as $2\sum_{i=1}^{11}i +24$ –  Ross Millikan Nov 27 '12 at 1:54

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.