100 people are sitting at a round table, they are from 25 countries (4 per country). Pick one from each so that no two are adjacent. Any thoughts?
Probabilistic method problem
2
$\begingroup$
probability-theory
-
0Yes. What is the question? – 2011-04-30
-
0@Emre: Any thoughts on how to do this? – 2011-04-30
-
4I'd politely ask them to move as appropriate. – 2011-04-30
-
0@Prbmethod: Please try to frame something that looks like an explicit mathematical **question**. Here is one, which may not be what you have in mind. There are $100$ people in a room, from $25$ countries, $4$ per country. How many ways are there to seat them at a (large) round table, so that no two people from the same country are next to each other? (And you might want to specify when we should consider two seating arrangements to be the same. If you shift all the people in a good arrangement to the right by $1$ chair, is this the same seating arrangement?) – 2011-04-30
-
0@Emre: What if they don't move? – 2011-04-30
-
0@user6312, I have a feeling that what Prbmethod wants is a proof that no matter how the people are seated there is a way to pick one from each country so no two are adjacent. But really it's up to Prbmethod to explain, not up to us to guess. – 2011-04-30
-
0@Gerry Myerson: Well, we now have *two* guesses, yours more interesting than mine. – 2011-04-30
1 Answers
2
Use the Lovász local lemma. When I try to use it the parameters don't work, but I'm sure you can make it work...
-
0The example at the wikipedia page http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma might be instructive. I haven't tried working out the details, but it is very similar. – 2011-04-30