Author |
Topic: Rotating Circle of Cards (Read 667 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Rotating Circle of Cards
« on: Dec 11th, 2007, 10:26am » |
 Quote  Modify
|
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
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Rotating Circle of Cards
« Reply #1 on: Dec 11th, 2007, 11:02am » |
Quote Modify
|
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.
There's probably a nicer way to put it.
|
| « Last Edit: Dec 11th, 2007, 11:04am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Rotating Circle of Cards
« Reply #2 on: Dec 11th, 2007, 11:06am » |
Quote Modify
|
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:
- 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.
Therefore, all games end. Q.E.D.
Edit: same solution as towr
--SMQ
|
| « Last Edit: Dec 11th, 2007, 11:07am by SMQ » |
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Rotating Circle of Cards
« Reply #3 on: Dec 11th, 2007, 11:35am » |
Quote Modify
|
on Dec 11th, 2007, 11:06am, SMQ wrote:| Edit: same solution as towr |
|
Except that I ended with the wrong card 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Rotating Circle of Cards
« Reply #4 on: Dec 11th, 2007, 1:29pm » |
Quote Modify
|
on Dec 11th, 2007, 11:06am, SMQ wrote:| Consider the longest possible game: |
|
Hmm, what is the longest possible game (without anyone holding a pair)? I can see a game with 25EDIT: 24 moves, but can we do better? (I don't think so, but I haven't proved it.)
The example I'm thinking of is:
| hidden: | | 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. |
|
| « Last Edit: Dec 11th, 2007, 1:38pm by Joe Fendel » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Rotating Circle of Cards
« Reply #5 on: Dec 12th, 2007, 12:57am » |
Quote Modify
|
My solution:
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.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Rotating Circle of Cards
« Reply #6 on: Dec 17th, 2007, 1:27pm » |
Quote Modify
|
| hidden: | | 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). |
I didn't estimate the longest game so far.
|
| « Last Edit: Dec 17th, 2007, 1:29pm by Hippo » |
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Rotating Circle of Cards
« Reply #7 on: Dec 17th, 2007, 3:38pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print