2
$\begingroup$

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?

  • 0
    @Gerry Myerson: Well, we now have *two* guesses, yours more interesting than mine.2011-04-30

1 Answers 1

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

  • 0
    The 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