wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Rotating Circle of Cards
        
(Message started by: william wu on Dec 11^th, 2007, 10:26am)

Title: Rotating Circle of Cards
Post by william wu on Dec 11^th, 2007, 10:26am

A deck of 50 cards contains two cards labeled n for each n = 1, 2, ..., 25. There are 25 people seated at a round table, each holding two of the cards in this deck. Each minute, every person passes the lower-numbered card of the two they are holding to the
right. Prove that eventually someone has two cards of the same number.

Source: Reid Barton

Title: Re: Rotating Circle of Cards
Post by towr on Dec 11^th, 2007, 11:02am

[hide]At each step more cards remain stationary. In step one, either some person has a double, or both 25 cards remain stationary. In step two either some person has a double, or both 25 and a 24 cards remain stationary. We can go on till the first 12-card . In further rounds all the other cards (1,1,2,2..11,11,12) will move round the table, until, at last, the second 12-card ends up with it's sibling.[/hide]

There's probably a nicer way to put it.

Title: Re: Rotating Circle of Cards
Post by SMQ on Dec 11^th, 2007, 11:06am

[hide]Call a card "frozen" if it is the high card in a player's hand and there are no unfrozen cards of higher rank. A player will never pass a frozen card (and, obviously, any player's hand can have at most one frozen card). Let the game end when any player is holding two cards of the same rank. Consider the longest possible game:
[/hide]
[hide]- Initially, both 25s are frozen.
- Some number of turns later, both 24s are frozen, as they can only be passed by players holding 25s.
- Some number of turns later, both 23s are frozen, as they can only be passed by players holding 25s or 24s.
...
- Some number of turns later, one of the 13s is frozen. Since 25 cards are now frozen -- one in the hand of each player -- the other 25 must remain circulating.
- Some number of turns later, one player will hold both 13s, ending the game.
[/hide]
[hide]Therefore, all games end. Q.E.D.[/hide]

Edit: same solution as towr

--SMQ

Title: Re: Rotating Circle of Cards
Post by towr on Dec 11^th, 2007, 11:35am

on 12/11/07 at 11:06:37, SMQ wrote:

Edit: same solution as towr

Except that I ended with the wrong card :-X

Title: Re: Rotating Circle of Cards
Post by Joe Fendel on Dec 11^th, 2007, 1:29pm

on 12/11/07 at 11:06:37, SMQ wrote:

[hide]Consider the longest possible game:[/hide]

Hmm, what is the longest possible game (without anyone holding a pair)? I can see a game with [hide]25EDIT: 24 moves[/hide], but can we do better? (I don't think so, but I haven't proved it.)

The example I'm thinking of is:
[hideb]One player starts with 25 and 24. To their left, the player holds 24 and 23, to their left 23 and 22, etc, until the last player holds 1 and 25. Then one of the 13s will stay still, but the other will take 25 turns to move around.[/hideb]

Title: Re: Rotating Circle of Cards
Post by Grimbal on Dec 12^th, 2007, 12:57am

My solution:
[hide]The highest value someone holds can only increase with time. Since the maximum is bound, eventually it will stop increasing for everybody.
From that moment on, there is a set of 25 cards that never move and a set of 25 cards that always turn.
Since 25 is odd, there must be a pair having a card in each set. These cards are bound to meet.

Unfortunately, it doesn't say how long it takes to end.[/hide]

Title: Re: Rotating Circle of Cards
Post by Hippo on Dec 17^th, 2007, 1:27pm

[hideb]My first solution was freezing, too. Now I am thinking about easy potential function ... what about sum of moved numbers? It never increases, but how long it can be stable? A number at least 13 is moved and a number at most 13 stay stil. They eventualy meet ... therefore potential decreases (or the process ends).[/hideb]

I didn't estimate the longest game so far.

Title: Re: Rotating Circle of Cards
Post by Joe Fendel on Dec 17^th, 2007, 3:38pm

Ah, okay, I've got the "longest game" proof.

Before I give it, here's a related follow-up to the original problem:

We forgot to mention that when a player has a pair, they shout "PAIR!" to end the game. After the 24th turn passing in silence, Tony, without even looking at the card he was passed from his left, smiles and shouts "PAIR!"

"Drat," says Lucy from across the table, "I guess Tony has the 13s."

How did Tony know without looking he now held a pair, and how did Lucy know it was 13s?