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

  • $\begingroup$ 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 $\endgroup$ – Gerry Myerson Nov 27 '12 at 1:42
  • 1
    $\begingroup$ @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$ $\endgroup$ – Ross Millikan Nov 27 '12 at 1:54

Call a player with two cards $13$ or less a low player. A player cannot become low by passing, so a player who is low at some point has always been low. As you showed in your answer to the question you linked to, the $24$ high cards will eventually spread out among $24$ players and become static. Thus eventually there will be exactly one low player, and she will have been low all along. We can show by induction that as long as she never has two $13$s, after $k$ moves the $k$ players to her right have a low card and a high card (since they'll eventually have a high card, they're never passed one, and they're always passed low cards as long as she doesn't pass them a $13$). Thus after $24$ moves she must have had two $13$s at some point.


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.