Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Davio]

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.

[Asklepios]

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?

[Qvist]

+1 for creativity. Still you got 0 points. 

[jomini]

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.

[DStu]

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.

[jomini]

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.

[moomoo]

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 ]

[DStu]

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.

[Qvist]

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.

[Qvist]

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.

[Davio]

Doing this in real life will look a lot like a Monty Python sketch.

[jomini]

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.

[Asklepios]

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.

[Grujah]

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.

[eHalcyon]

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.

[Asklepios]

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.