6
$\begingroup$

Problem: Nine delegates, three each from three different countries, should be seated at a round table that seats nine people. How many different ways are there to seat them in such a way that no two delegates from the same country seat near each other? All the delegates are different, and arrangements that differ only by rotation are considered the same.

Solution: I've found a dull solution for the problem. You just fix some guy from one of the countries in the "first" place and build all possible correct arrangements. First you consider all the different ways two other guys from the same country can be placed. And after that one can just see that leftover places are split into one of the three possible groups $1 + 2 + 3$, $1 + 1 + 4$, $2+2+2$. For each of the splits you count number of ways to seat other delegates and thus find the answer. But this method involves drawing a lot of tables and seems like prettified bruteforce solution.

Question: is there another more elegant way of solving the problem? Statement reminds of Lovász local lemma, but this lemma gives only some bound for probability. May be there are some another theorem on coloring or something like this?

Thanks in advance for any ideas.

$\endgroup$
  • 1
    $\begingroup$ What arrangements do you consider different? If two delegates from the same country switch places, is that the same or different? What if everyone stands up and moves one seat to the right? Are you familiar with permutations and combinations? $\endgroup$ – dfeuer Nov 30 '13 at 8:11
  • $\begingroup$ "If two delegates from the same country switch places..." as it is said in the statement all delegates are different. So, these will be different arrangements. "What if everyone stands up and moves one seat to the right? " as it is said in the statement arrangements that differ only by rotation are considered the same. So, these will be the same. $\endgroup$ – Boris Nov 30 '13 at 9:25
2
$\begingroup$

No ,you have to bruteforce in this case in order to get the solution. But if from a certain country, there had been only one person the you could straightaway apply linear permutation.

$\endgroup$
  • $\begingroup$ The reason I'm searching for more simple solution is this problem being marked as "not difficult". And comparing my solution with solutions for other "not difficult" problems I think there should be some shorter way of solving it. $\endgroup$ – Boris Nov 30 '13 at 10:04
  • $\begingroup$ What is the final answer in the book ? $\endgroup$ – user2369284 Nov 30 '13 at 10:08
  • $\begingroup$ There is no final answer in the book. I've got 3168 as the answer via my solution and via full enumeration in Python script. $\endgroup$ – Boris Nov 30 '13 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.