Yoak: More Goings On At The ‘Crazy Buttocks’ Party
In Living With Crazy Buttocks, Stephen Morris told us of a rather interesting party. The story continues…
After winning their trip to Paris, the guests became elated and celebrated with the consumption of some adult beverages. Ever responsible, the host confiscated the keys to all cars to ensure that no one drove home drunk. Later on, when things started to calm down, party-goers started to request the return of their keys claiming to be sober enough for the drive home.
Having once been out-done by the guests, our host took another whack. He distributed all of the keys, but did so randomly. He then presented a challenge he felt sure they’d only be able to satisfy if they were indeed sober enough to drive. They were allowed to exchange keys, but only in rounds. During each round, each party-goer could either do nothing or pair up with another party-goer and exchange the sets of keys each was holding. (Each party-goer could be part of at most one pairing per round.) No one would be allowed to drive home unless everyone recovered their own keys.
The host wished to allow only a fixed number of rounds. To be fair, he wanted to be sure that it would indeed be possible to make the change. However, he also wanted to make it as difficult as possible for the party-goers. What is the minimum number of rounds must allow them to ensure that an exchange would be possible?
For clarity, all key recipients can discuss, share information such as who has the keys of whom, and agree upon a strategy. Also, careful readers will realize that there were 20 guests at the party originally. Sadly, it was a rather disorderly party and some guests did leave early, but many more appeared. Everyone present at the key ceremony had a key confiscated, and everyone with a key confiscated received a key for this challenge, but neither you nor the host knows just how many there are.
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
Stephen Morris said,
December 5, 2009 at 12:49 pm
Anyone who has their own key can go home straight away.
The others line up so that their key is held by the person to their left. This will split the group into circles.
Each circle closes up so that it becomes two lines. Each guest swaps keys with the person in front of them. There may be some odd people at the ends of the lines who don’t swap keys.
Everyone in the middle of a line gets the key of the person to their left in the opposite line. This is symmetrical so now we have paired everyone off. This works for the people at the ends too, but you might want to draw it to see it.
So we can do it in two rounds of swapping.
jyoak said,
January 10, 2010 at 11:18 pm
For some time I’ve meant to show another way that this can be done. Now knowing that it can be done in two rounds, write out blanks for the states the coins will have. We’ll order the people arbitrarily and list which keys they’ll have, and what they’ll have after each of the two swaps. Let’s assume 6 people, as it doesn’t matter. Let’s say they start with:
6 3 1 2 5 4
_ _ _ _ _ _
1 2 3 4 5 6
The first line of underscores indicates what key each person will have after the first switches and the second is the state we plan to reach where they all have their own keys after the second switch. So arbitrarily assume that the first person doesn’t switch the first time. We get:
6 3 1 2 5 4
6 _ _ _ _ _
1 2 3 4 5 6
But notice that trades have to be two-way, and we now know that 1 and 6 swapped in the second stage. So we can conclude that this must have been true:
6 3 1 2 5 4
6 _ _ _ _ 1
1 2 3 4 5 6
But notice to get there, The 4 key and the 1 key much have switched during the first round, so this implies:
6 3 1 2 5 4
6 _ 4 _ _ 1
1 2 3 4 5 6
Similarly, now, we know that 4 swaps with 3 in the second round.
6 3 1 2 5 4
6 _ 4 3 _ 1
1 2 3 4 5 6
and that 2 and 3 swapped in the first round:
6 3 1 2 5 4
6 2 4 3 _ 1
1 2 3 4 5 6
And we’re done. (5 initially held his own key and hangs on to it throughout.)
This method of reaching a solution actually resolves a cycle of any length as did Steve’s. In this case, we resolved two cycles, one of length 5 and one of length 1. With each new cycle of greater than length one, just bring a single person down (no trades in first round) and follow the same process.