Print

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

[Qvist]

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...

[werothegreat]

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.

[Qvist]

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.

[shMerker]

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.

[noon]

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.

[eHalcyon]

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?

[HiveMindEmulator]

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...

[Qvist]

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.

[eHalcyon]

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.

[Qvist]

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.

[eHalcyon]

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.

[cayvie]

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.

[jomini]

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).

[jomini]

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.

[Jedit]

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. 

[Kirian]

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/

[jomini]

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.

[Piemaster]

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.

[sherwinpr]

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.

[Grujah]

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" ?

[jomini]

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).

[rod-]

Ask someone else (anyone else) where to sit. 

[Qvist]

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?

[jomini]

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).

[Qvist]

And how do you determine the closest person? Dealing out ~500000 foot rules?