Dominion Strategy Forum
Dominion => Dominion General Discussion => Topic started by: Qvist on September 06, 2012, 12:09:31 pm
-
Don't ask me how I came up with this riddle and it has probably a simple solution, but I don't have any. It isn't really a riddle, but, eh, just read it. And it has nothing to do with Dominion, but here are so many Logic and Math experts that might help me. Here it is (I hope I can explain it understandable):
-----------------------
A group of X people is in the same room, each one sitting on a chair.
No-one knows any other person in the room.
The chairs are not be placed in the room in a specific pattern, they are distributed all over the room.
Suddenly a man enters the room, challenging the people in the room with following task:
"Each one of you has to sit on a different chair than the one you're currently sitting on.
But you aren't allowed to choose the chair you're going to sit on on your own, so let's just say you have to sit on a random different chair.
You may use supporting tools for that as long you can find it in a normal household.
Do that as fast as you can."
What method would you use for a group of 10 people / 100 people / unlimited big group of people?
Would it change the method
- if the chairs would be form a specific pattern, like a circle?
- if you would be the host, knowing the names of all people in the room?
- if you would have to change chairs multiple times?
-----------------------
Don't laugh at me for that crazy question, but this really bugs me. I'm looking forward to read some interesting ideas.
If there are any open questions that are not covered here, feel free to ask...
-
Make a computer program.
EDIT: That is, give each person and chair a label, then have a computer randomize who sits where, with the initial conditions, and the fact that you can't sit in the same spot twice.
-
Takes a lot of time to make that computer program. I'm sure there's a faster solution.
EDIT: Maybe not a lot of time, but it takes some time. And with X being big, assigning a number to each chair is also time consuming.
-
With a circle of chairs it's really easy: Someone flips a coin. If it's heads, everyone moves one chair to the right; if tails, one chair to the left.
-
write the numbers 1-N on two sets of cards. Use one set to label each chair. Each person remembers what number chair they were on and stands up. Shuffle the other set of cards. Draw a card, and tell the person who was in chair 1 to go to that chair. Redraw if you drew the 1. Repeat for chairs 2-N.
-
What's the definition of "choice" here? That is, what can you do before it is "choosing" a chair, and thus illegal?
My solution:
Everyone picks up their chair. They wander around randomly for a minute or two (maybe with eyes closed, if we don't mind some injuries). Everyone pairs up randomly with someone else and they swap chairs. If necessary, an odd man out can join a pair.
Does that count as random?
-
I think you need to clarify "you aren't allowed to choose the chair you're going to sit on on your own". So who chooses it? If you agree with someone else, is that not choosing it on your own? Like if you group up in groups of 2-3 and switch/rotate chairs does this solve it? You're not choosing on your own really...
-
Thanks for your answers so far.
I hoped that the wording don't make any problems, so here are some clarifications:
- "random" means that no matter what method is used, you may end up on any other chair.
- One rule was missing: You aren't allowed to move any chair.
- "choose on your own" is hard to clarify. That basically means that no-one can "manipulate" on what chair he will end up. You have to minimize the impact that you may have in the outcome.
shMerker, really good and elegant solution, but unfortunately I didn't clarify what I meant with "random", so this doesn't work.
noon, yeah, this is the most obvious solution, which is good for a low number of people. It doesn't scale very well and will not work with 1000 people or more.
HME, this isn't allowed which hopefully is clear now after my clarification.
eHalcyon, I really like your solution, except for picking up the chair which I forgot to exclude. But you could modify that easily, e.g.
Everyone puts a item/cloth on his/her chair and closes his/her eyes and spins round and then walks around the room with eyes still closed. After a certain time/deadline the first person you collide with is your partner. You and your partner lead each other to the chair you were sitting on. You can identify it by the item on the chair.
This solution is way better than my best so far. But there are still ways to "manipulate" like not closing the eyes. But if we assume that no-one will "cheat", that's a fine solution.
The best solution I came up with so far, which solves the problem of the time spent writing "signs" for each chair:
Everyone takes off his/her shoes and puts one of them on his/her chair. Then you bring the other shoe to a specific place (e.g. to the man who entered the room).
The first person just gives it to him and waits. Every other person exchanges his/her shoe with the shoe in the hand of the man and searches for the other shoe. That chair is his/her new chair. The remaining shoe is the shoe for the first person waiting.
-
Since my solution involved pairing off, there were states that are unreachable (i.e. the random state where four players rotated chairs somehow).
If that's now allowed, easy enough to combine yours and mine.
Take off your shoes. Put one on your chair, toss the other one into a pile. Each person closes their eyes and grabs a shoe at random. Toss it back and repeat if you picked your own shoe. Find the chair with your new shoe. If an odd man out is stuck with their own shoe, it's easy enough to fix by swapping with someone else.
This is faster if you can use seat numbers so you don't have to waste time finding a matching shoe.
Shoe solution breaks if there are shoe duplicates.
-
I'm not sure if this is slower with a big group of people because a big pile of shoes with 1000 or more people there's still the need of a waiting queue which doesn't scale well.
And shoe solution doesn't really break with duplicates because you aren't allowed to take the same shoe that you had and if there are 2 or more possibilites you just have to take the chair/shoe you first found.
-
Again, it depends on your definition of random. Is it enough that anyone can end up with any chair (which my solution satisfies) or does every permutation need to be possible? For example, say there were just four people A-D, and four chairs 1-4. We start A1, B2, C3, D4. My solution would never have them end up with A2 B3 C4 D1, because they always pair off. Each individual person may end up at any chair, but only a subset of permutations is possible.
-
One way:
variation on the improv game "go" (not to be confused with the board game)
person A asks person B where he/she should go. Person B points to person C's chair. A walks to person C while B asks C where he/she should sit. This continues.
It only seats 1 at a time, but it pretty much guarantees success.
-
I'm not sure what you are going for here but here is a possible option:
Everyone flips a coin. Heads stay seated and raise their right hands. Tails get up, find a person with their right hand up, and swaps chairs with that person (i.e. I flip heads, I raise my right hand, you flip tails you come over tell me where your chair is, you sit in mine without raising a hand, I go sit in yours without raising a hand). Because it is quite likely that we won't have parity, the leftovers can repeat the exercise amongst just themselves. Odd man out swaps chairs with the individual nearest him.
Virtually everyone will swap chairs locally, so time spent is minimal for most folks. There is a small time delay while people have to be directed across long distances and then some delay for repeating the exercise (after figuring out if it is the surplus heads or tails who need to repeat). However, the larger the sample size, the smaller the surplus (in proportion to the population).
This ensures that all permutations are possible, but not all permutations are equally likely (due to the time preference for local sorting first).
-
Also, if you want to get rid of the coin, you could just use birth dates. If the month you were born is even, stay seated, if odd get up and find a chair. For the leftovers, use the day for odd/even. Third iteration use the year for odd/even. I believe three rounds should be sufficient to make any remainder a trivial sorting problem that doesn't need to scale.
-
Also, if you want to get rid of the coin, you could just use birth dates. If the month you were born is even, stay seated, if odd get up and find a chair. For the leftovers, use the day for odd/even. Third iteration use the year for odd/even. I believe three rounds should be sufficient to make any remainder a trivial sorting problem that doesn't need to scale.
Not really. One in ten people will still be in their original seat.
-
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
That's the best you're going to do. This is nearly functionally equivalent to noon's solution. If you're OK with some permutations not being possible, faster solutions are possible, but not fully random.
And as far as wero's first reply, you don't need to write the program yourself: http://www.random.org/lists/
-
Also, if you want to get rid of the coin, you could just use birth dates. If the month you were born is even, stay seated, if odd get up and find a chair. For the leftovers, use the day for odd/even. Third iteration use the year for odd/even. I believe three rounds should be sufficient to make any remainder a trivial sorting problem that doesn't need to scale.
Not really. One in ten people will still be in their original seat.
No. Assume there are 100 people. 55 people have odd birthdays, 45 have even birthdays. All of the evens swap seats with an odd.
Now 5 people remain. They do months. 3 have odd months, 2 have even. The two evens each swaps with an odd. The odd man left swaps with whoever is nearest him.
The number of people unable to swap during each iteration is limited to the degree to which parity between evens and odds is not maintained. Statistics predict that the larger your sample size, the smaller the relative disparity between evens and odds. I do not see how you can get a 10% figure here; the disparity between even and odd birthdays is nowhere near high enough for that.
-
I think the computer program is the best solution. It wouldn't be a complex program, just a simple shuffle array, check for duplicates, reloop. I imagine an accomplished programmer could write the program in under 10 minutes.
-
Something that may be of help: a substantial fraction of permutations are derangements (that is, permutations where no object stays in its original position). In fact, as n->infinity, the fraction of permutations on n objects that are also derangement, d_n/p_n, approaches 1/e, or about 0.3679, where e is the base of the natural logarithm.
Therefore, any method that can give you a uniformly random permutation, together with a method to check for whether or not anyone left their original chair, can be modified to solve this problem. You simply keep trying until you get a random derangement, and on average, you only need to make e (about 2.7183) attempts. 98.98% of the time, you will find a derangement in 10 attempts or fewer.
EDIT: d_n/p_n = 0.3333, 0.375, 0.3667, and 0.3681, for n = 3, 4, 5, and 6, respectively, so the convergence to 1/e is very fast (note that the ratio is always falling, and hence, approaches 1/e from above), and hence, this technique is always valid.
-
Also, if you want to get rid of the coin, you could just use birth dates. If the month you were born is even, stay seated, if odd get up and find a chair. For the leftovers, use the day for odd/even. Third iteration use the year for odd/even. I believe three rounds should be sufficient to make any remainder a trivial sorting problem that doesn't need to scale.
Not really. One in ten people will still be in their original seat.
No. Assume there are 100 people. 55 people have odd birthdays, 45 have even birthdays. All of the evens swap seats with an odd.
Now 5 people remain. They do months. 3 have odd months, 2 have even. The two evens each swaps with an odd. The odd man left swaps with whoever is nearest him.
The number of people unable to swap during each iteration is limited to the degree to which parity between evens and odds is not maintained. Statistics predict that the larger your sample size, the smaller the relative disparity between evens and odds. I do not see how you can get a 10% figure here; the disparity between even and odd birthdays is nowhere near high enough for that.
What if it is a "people born on 29th February Party" ?
-
Also, if you want to get rid of the coin, you could just use birth dates. If the month you were born is even, stay seated, if odd get up and find a chair. For the leftovers, use the day for odd/even. Third iteration use the year for odd/even. I believe three rounds should be sufficient to make any remainder a trivial sorting problem that doesn't need to scale.
Not really. One in ten people will still be in their original seat.
No. Assume there are 100 people. 55 people have odd birthdays, 45 have even birthdays. All of the evens swap seats with an odd.
Now 5 people remain. They do months. 3 have odd months, 2 have even. The two evens each swaps with an odd. The odd man left swaps with whoever is nearest him.
The number of people unable to swap during each iteration is limited to the degree to which parity between evens and odds is not maintained. Statistics predict that the larger your sample size, the smaller the relative disparity between evens and odds. I do not see how you can get a 10% figure here; the disparity between even and odd birthdays is nowhere near high enough for that.
What if it is a "people born on 29th February Party" ?
Cute. Start with the year and work with the hours of birth (if you don't know, guess).
-
Ask someone else (anyone else) where to sit.
-
Ok, thanks again for your input.
I agree that it depends on the definition of randomness. Let's just assume, like I said earlier, that not all permutations must be possible, but at least you could end up on any chair.
jomini, the problem with your coin solution is - if I understood it right - that you still have a choice between half of the chairs which shouldn't be possible. You shouldn't have a choice at all.
cayvie, rod-, your solution is interesting. As I assumed that no person knows another person and random means "cheating should be avoided", that seems like a possible solution. So, your choice is sort of indirect. You may choose whom you ask, but you can't know where you end up.
-----
What I find interesting with the riddle and the solutions so far, that there's no simple solution. The biggest problem is to identify the chairs as they are unordered. If they already had numbers on them or would be ordered in a circle or another simple pattern, all would be so much easier. So, I like the "shoe solution" so far. You don't need to take time to write a number on each chair what needs way to much time. But still the time you need for the rest increases with more chairs. What I still like to find out: Isn't there a solution where the time increases less than proportional to the number of chairs in the room? So, let's just assume 1 million people and chairs, what is the fastest solution?
-
Ok, thanks again for your input.
I agree that it depends on the definition of randomness. Let's just assume, like I said earlier, that not all permutations must be possible, but at least you could end up on any chair.
jomini, the problem with your coin solution is - if I understood it right - that you still have a choice between half of the chairs which shouldn't be possible. You shouldn't have a choice at all.
cayvie, rod-, your solution is interesting. As I assumed that no person knows another person and random means "cheating should be avoided", that seems like a possible solution. So, your choice is sort of indirect. You may choose whom you ask, but you can't know where you end up.
-----
What I find interesting with the riddle and the solutions so far, that there's no simple solution. The biggest problem is to identify the chairs as they are unordered. If they already had numbers on them or would be ordered in a circle or another simple pattern, all would be so much easier. So, I like the "shoe solution" so far. You don't need to take time to write a number on each chair what needs way to much time. But still the time you need for the rest increases with more chairs. What I still like to find out: Isn't there a solution where the time increases less than proportional to the number of chairs in the room? So, let's just assume 1 million people and chairs, what is the fastest solution?
Okay so doing my solution with zero choice is fairly simple. Swap chairs with the person closest with their hand up. In the event of ties for distance from you, swap with the person closest to the 12 o'clock position and work clockwise from there (this can be modified if needed to deal with 3d dimensional seating plans or higher if needed). First come, first serve, so in the event that you and another person are supposed to swap with the person nearest, you both head toward that person and the slower one then has to find the closest hand up remaining (if you need an absolute tie breaker you and the other guy flip a coin for who swaps there and who moves onward).
This removes any element of choice and scales below proportionality for the number of people. The larger the sample size, the closer we expect the heads and tails counts to be relative to the sample size (fewer iterations needed). Because most seat swapping is done locally and in parallel (unlike the linear shoe pile), adding more people doesn't greatly increase the shuffling time.
This still has a local bias so while any state is possible and there is no element of choice now, not all states are equally accessible (this is why it is faster than the canonical shuffles - we are mostly sampling only the fastest permutations).
-
And how do you determine the closest person? Dealing out ~500000 foot rules?
-
And how do you determine the closest person? Dealing out ~500000 foot rules?
Echolocation obviously.
Just shout really hard and see where it bounces back.
-
I came up with the circle and coin flipping solution too, but that kind of fails with no chair moving stipulated. So here's my new solution:
Progress around the room taking blood samples from each victim. Uh, person, I mean.
Sequence their DNA individually, then use a computer program to translate each persons unique sequence into a unique musical tune playable on a pentatonic scale. Teach each person their tune, and equip them with sufficient singing skills that they can sing it perfectly.
Next randomly create your own tune, based on the same scale but derived from the length between the nose and tail tip of a random sample of household canines.
Next have each person sing their tune into a recording device, and calculate who is closest to your tune, in order. Then randomly allocate different colours to each chair, and paint each chair that colour.
Finally, match the colours to different tunes based on intuitive reasoning methods and inner genius and chi.
If this method results in someone being matched to their original chair, then begin the process again, but alter the parameters of the original computer program that turned DNA into music. Repeat until no-one matches their original chair.
Simple, huh?
-
+1 for creativity. Still you got 0 points. :P
-
And how do you determine the closest person? Dealing out ~500000 foot rules?
Use of the distance estimation capabilities inherent to stereoscopic vision (remember we have a million people here so it is not just your vision in play, but everyone who can point you to the nearest person).
The point isn't that you have to calculate the closest person, just that you have to make a reasonable estimate that precludes conscious choice. So if A is swapping with B (350 ft away) and C (320 ft away), it really doesn't matter if the distance estimate is wrong. Because A is the one that moves (and then directs B xor C back to his chair), a deterministic estimate is enough to choose (in the deterministic mathematical sense) and sort.
I'm not sure what you want here. Is it a way to shuffle people around that will give you a truly random mapping from one state to another with the sole non-random element being that no one can have the same seat? If so, then there is no way I can see to do that without numbering the chairs/people (or doing something that is even more time intensive, like the shoes).
Is it just getting people into different chairs? If so, then the fastest sorting methods are going to be those that sample faster permutations. We are dealing with presumably intelligent people here - this means we can count on them to self sort to a very high degree locally. This means that they can estimate things like distance and that they can relay information to each other (like locations of chairs). This just begs to be made into a parallel task with most of the sorting occurring locally - that allows you to scale on a log function. Further, a solution which is "good enough" can be iterated just a handful of times and will likely be faster than a centrally directed method.
-
I'm not sure what you want here. Is it a way to shuffle people around that will give you a truly random mapping from one state to another with the sole non-random element being that no one can have the same seat? If so, then there is no way I can see to do that without numbering the chairs/people (or doing something that is even more time intensive, like the shoes).
Anyway, even if you would come around that, shuffling a set is obviously harder than shuffeling an array (just ignore any additional information that the array carries), and shuffling an array takes linear time, so you can't be faster than linear. If you're linear anyway, you can let the people line up and draw numbers.
Is it just getting people into different chairs? If so, then the fastest sorting methods are going to be those that sample faster permutations. We are dealing with presumably intelligent people here - this means we can count on them to self sort to a very high degree locally. This means that they can estimate things like distance and that they can relay information to each other (like locations of chairs). This just begs to be made into a parallel task with most of the sorting occurring locally - that allows you to scale on a log function. Further, a solution which is "good enough" can be iterated just a handful of times and will likely be faster than a centrally directed method.
I'm not quite sure how to do that. Have started a post but erased it. It's quite easy to get a graph on the people (Voronoi diagram), and starting from this graph you also get a linear ordering in something like log-time, but I don't get it without 'gaps', so I don't get a real mapping {set of people} -> {1, .. , N}. And I don't see how I should proceed with my linear ordering with gaps.
And having done something random local, and iterate that should also not work faster than linear, because at least in 2 dimensions, you have a graph of diameter sqrt(N), so you expect also linear time until randomness spread through this graph by Central Limit Theorem.
-
I'm relying on the fact that our set consists of intelligent (self-ordering) individuals. While there will be gaps, but the individuals in the gaps have the ability to intelligently deal with that.
We have done something random, global (everyone has been sorted into one two nearly equal subsets). Now we just need to map the subsets to each other and deal with the remainder. For most people, the mapping is simple - most odds will be able to easily identify the nearest even and swap in a trivially fast fashion. This leaves an increasingly small fraction of folks who couldn't swap because:
1. They nearest odd & even pair cannot be located.
2. The numbers of odds xor evens is too high.
The first will be dealt with by dint of people pointing, calling, asking, etc. The second can be dealt with using iteration.
I've seen this work in the real world (using digits from serial numbers) to sequentially sort people into unique pairs. There is little appreciable difference into the time needed for a company or a brigade to so randomly pair off.
-
This sort of reminds me of this problem [ to which I have yet to come up with a solution ]:
http://www.acritch.com/media/math/Self-assigned_student_numbers.pdf
"Consider an isolated group of n students. They wish to assign themselves unique student numbers from 1 to n (no repetitions!) in such a way that each student will know his own student number, but each student should have no information about any other student's number."
[ further details / clarifications in the pdf ]
-
I'm relying on the fact that our set consists of intelligent (self-ordering) individuals. While there will be gaps, but the individuals in the gaps have the ability to intelligently deal with that.
We have done something random, global (everyone has been sorted into one two nearly equal subsets). Now we just need to map the subsets to each other and deal with the remainder. For most people, the mapping is simple - most odds will be able to easily identify the nearest even and swap in a trivially fast fashion. This leaves an increasingly small fraction of folks who couldn't swap because:
1. They nearest odd & even pair cannot be located.
2. The numbers of odds xor evens is too high.
The first will be dealt with by dint of people pointing, calling, asking, etc. The second can be dealt with using iteration.
I've seen this work in the real world (using digits from serial numbers) to sequentially sort people into unique pairs. There is little appreciable difference into the time needed for a company or a brigade to so randomly pair off.
I think my problem here is while you have a positive probability to get to chairs at the other end of the graph for each fixed graph, the probability that this happens converegs to 0 when you enlarge the graph. If you want to get rid of tht, you would have to repeat the proceduce O(N) times.
-
And how do you determine the closest person? Dealing out ~500000 foot rules?
Use of the distance estimation capabilities inherent to stereoscopic vision (remember we have a million people here so it is not just your vision in play, but everyone who can point you to the nearest person).
The point isn't that you have to calculate the closest person, just that you have to make a reasonable estimate that precludes conscious choice. So if A is swapping with B (350 ft away) and C (320 ft away), it really doesn't matter if the distance estimate is wrong. Because A is the one that moves (and then directs B xor C back to his chair), a deterministic estimate is enough to choose (in the deterministic mathematical sense) and sort.
I'm not sure what you want here. Is it a way to shuffle people around that will give you a truly random mapping from one state to another with the sole non-random element being that no one can have the same seat? If so, then there is no way I can see to do that without numbering the chairs/people (or doing something that is even more time intensive, like the shoes).
Is it just getting people into different chairs? If so, then the fastest sorting methods are going to be those that sample faster permutations. We are dealing with presumably intelligent people here - this means we can count on them to self sort to a very high degree locally. This means that they can estimate things like distance and that they can relay information to each other (like locations of chairs). This just begs to be made into a parallel task with most of the sorting occurring locally - that allows you to scale on a log function. Further, a solution which is "good enough" can be iterated just a handful of times and will likely be faster than a centrally directed method.
Sorry, I didn't meant to offend you in any way. It's a good idea. The probem is still - if I understood you correctly - that you may not end up on any other chair.
This sort of reminds me of this problem [ to which I have yet to come up with a solution ]:
http://www.acritch.com/media/math/Self-assigned_student_numbers.pdf
"Consider an isolated group of n students. They wish to assign themselves unique student numbers from 1 to n (no repetitions!) in such a way that each student will know his own student number, but each student should have no information about any other student's number."
[ further details / clarifications in the pdf ]
Great. First approach:
1.) Turn off the light / Everyone closes their eyes.
2.) Everyone walks around the room.
3.) If someone hits another student, he has to put his hand on the other student's shoulder. While the other student keeps walking, he has to keep his hand on the shoulder.
4.) Repeat until all students are in one line.
5.) From person 1 (the person on the front) to person n (the last person), each one has to count his position by touching everyone who is in front of him.
-
So, I've took all your input and came up for a solution which scales very well. Let's see if anybody can improve it. First again all revised rules with the corrections from your input:
------------
A large group of people (you can assume ~100000) is in the same room, each one sitting on a chair.
No-one knows any other person in the room.
The chairs are not be placed in the room in a specific pattern, they are distributed all over the room.
Suddenly a man enters the room, challenging the people in the room with following task:
"Each one of you has to sit on a different chair than the one you're currently sitting on.
But you aren't allowed to choose the chair you're going to sit on on your own, so let's just say you have to sit on a random different chair.
The probabilites of ending up on each chair haven't to be equally likely, but you may end up on any other chair except the one you're currently sitting on.
You may use supporting tools for that as long you can find them in a normal household or carrying them with you.
You aren't allowed to move any chair. Do that as fast as you can."
------------
0.) While steps 1 to 7 will be processed, the man who entered the room has to determine a random time frame.
You can stop the time it takes for finishing these steps 1 to 7 or shuffle a music library on your PC and take the time of the first song.
1.) Everyone stands up.
2.) Everyone points at his nearest neighbor.
3.) If two people point at each other they found a partner and can sit down.
4.) If anybody pointed at someone who already had found a partner, point at the next nearest neighbor who still stands.
5.) Repeat until no-one or exactly one person remains. If exactly one person remains, this person isn't allowed to take part in steps 6 to 13. For example he can leave the room meanwhile.
6.) One person of each two-person group randomly assigns himself to Group A or Group B. He can flip a coin or guess in which hand his partner has an item.
7.) Everyone from Group A takes of his shoes, stands up, putting one of his shoes on his chair and holding the other one in his hand.
8.) The neutral person switches off the light and everyone from Group A walks around the room. He switches the light on when the time is over. Everyone from Group A has to stop.
9.) Everyone raises one hand.
10.) Everyone points at his nearest neighbor who is in the other group with the other hand.
11.) If two people point at each other they found a partner and can lower their hands.
12.) If anybody pointed at someone who already had found a partner, point at the next nearest neighbor who is in the other group and still has his hand in the air.
13.) Repeat until no-one is left. If in step 5 one person was remaining, repeat until 2 people are left and the remaining person returns to his chair, waiting there standing up.
14.) Everyone from Group A sits on the chair of his partner and gives him his shoe.
15.) Everyone from Group B has to find the chair with the corresponding shoe. His partner can show him the direction to find the chair faster.
16.) If in step 5 one person was remaining, the person from group B who was left over in step 13, has to go to the remaining person and give him his shoe.
17.) He has to find the last chair which is empty.
Some notes:
If two or more people have the exact same shoes, that doesn't matter. In step 15, they sit down if they found the first fitting corresponding shoe.
To be sure, that everyone may end up on any other chair the time frame has to be at least as long as it takes to walk from one end of the room to the other end of the room.
-
Doing this in real life will look a lot like a Monty Python sketch.
-
I'm relying on the fact that our set consists of intelligent (self-ordering) individuals. While there will be gaps, but the individuals in the gaps have the ability to intelligently deal with that.
We have done something random, global (everyone has been sorted into one two nearly equal subsets). Now we just need to map the subsets to each other and deal with the remainder. For most people, the mapping is simple - most odds will be able to easily identify the nearest even and swap in a trivially fast fashion. This leaves an increasingly small fraction of folks who couldn't swap because:
1. They nearest odd & even pair cannot be located.
2. The numbers of odds xor evens is too high.
The first will be dealt with by dint of people pointing, calling, asking, etc. The second can be dealt with using iteration.
I've seen this work in the real world (using digits from serial numbers) to sequentially sort people into unique pairs. There is little appreciable difference into the time needed for a company or a brigade to so randomly pair off.
I think my problem here is while you have a positive probability to get to chairs at the other end of the graph for each fixed graph, the probability that this happens converegs to 0 when you enlarge the graph. If you want to get rid of tht, you would have to repeat the proceduce O(N) times.
If I understand you correctly (graph theory was long, long ago for me), you are saying that a person starting at say the west side of the room has a decreasing chance of ending up on the east side of the room as the size of the room increases.
This is true. I have said throughout that while my method might give rise to any possible permutation of people; it is heavily biased against some (most) of them. The objective I had was to quickly seat individuals in different chairs without individuals choosing their new seats. My method does not give a truly random (in the strictest mathematical sense) rearrangement; of course the problem itself precludes a truly random rearrangement.
If you want to maximize entropy, subject to the must change seats rule, you have to follow one of the canonical sorting algorithms. I can beat those, but only with local parallel sorting and biasing towards the faster achievable permutations.
-
This sort of reminds me of this problem [ to which I have yet to come up with a solution ]:
http://www.acritch.com/media/math/Self-assigned_student_numbers.pdf
"Consider an isolated group of n students. They wish to assign themselves unique student numbers from 1 to n (no repetitions!) in such a way that each student will know his own student number, but each student should have no information about any other student's number."
[ further details / clarifications in the pdf ]
Ooh, interesting. The clarifications help.
I think I suck at this. I can't come up with a solution that doesn't involve computers or handguns.
-
Great. First approach:
1.) Turn off the light / Everyone closes their eyes.
2.) Everyone walks around the room.
3.) If someone hits another student, he has to put his hand on the other student's shoulder. While the other student keeps walking, he has to keep his hand on the shoulder.
4.) Repeat until all students are in one line.
5.) From person 1 (the person on the front) to person n (the last person), each one has to count his position by touching everyone who is in front of him.
Won't work, they will recognize each other by scent, as said.
-
This sort of reminds me of this problem [ to which I have yet to come up with a solution ]:
http://www.acritch.com/media/math/Self-assigned_student_numbers.pdf
"Consider an isolated group of n students. They wish to assign themselves unique student numbers from 1 to n (no repetitions!) in such a way that each student will know his own student number, but each student should have no information about any other student's number."
[ further details / clarifications in the pdf ]
Ooh, interesting. The clarifications help.
I think I suck at this. I can't come up with a solution that doesn't involve computers or handguns.
I think I have a starting point. Not sure if it works. If it does not, not sure what to do to make it work. Lack of even pencil and paper makes it a little more difficult.
1. Students number themselves off. This is just an initial ID, before randomization.
2. Students pair off and privately play a game of chance to randomly determine what to do next. Rock Paper Scissors would work. Or maybe both students simultaneously show a number of fingers; if the sum of their numbers is ODD then do A, if Even then do B. Something like that.
3. Based on the result of the game, Students either swap numbers or they don't.
3. Students repeat steps 2 and 3 again and again with different partners.
The main issue with this is that, immediately following a swap, partners will know the other's number. So how do we get to a stopping condition? Maybe students can stop after they've played X games without swapping. But that might end in a small group of students who know their own subset of remaining numbers, due to switching.
Perhaps throughout the exercise pairs could sometimes decide not to swap at all.
So the question is, through this process, is it still possible for a player to track the potential movement of a number, or can it get to the point where a number might be anywhere? A way to confound this is to keep pairings secret. Say there is one central meeting place where all the students begin, and an adequate number of private rooms where they can carry out the above steps to shuffle their IDs. After a pair finishes their swapping game, they wait some time and then one of them returns to the public place. That person waits until another student returns, and they form a new pair, going to a new private room and playing the swapping game. Their original partners will do the same after waiting some more.
That way, students won't know who other students have partnered with and when they may have done so.
If all of this is an adequate solution, then the hard-mode question is if this could be simplified into a specific algorithm that puts a bound on the number of interactions while remaining adequate.
-
Hold on, I assumed that "assign themselves" means they get to pick their own number. This becomes a lot more achievable if they are assigning themselves a random number.