The Queen of England wants to organize a set of tables for n guests talking different languages. The tables have to be set in a way that every guest can speak to his neighbor on the right and his neighbor on the left.

Four possibilities come up : 1- One table for all guests. 2- One table for all guests, but we alternate between men and women. 3- Guests are grouped 2 by 2 (n/2 tables)

The problem seems to me similar to the Minimum Spanning Tree. The graph would have nodes of guests connected if the two guests can speak the same language. But there seems to be more than this to it. I'm going to continue trying to find a classic graph problem that can represent this problematic. Any help is greatly appreciated. I have an exam in graph theory next week. Wish me luck.

  • $\begingroup$ You say 4 possibilities but I only see 3 possibilities. Well, one approach is to try each of the possibilities in turn. So, that's 3 algorithmic questions. For each one, what are your thoughts? What approaches have you considered? For instance, can you check whether it's possible to find a single table for all guests, and what approaches have you considered/tried already? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Jun 24 '17 at 17:26
  • 2
    $\begingroup$ Ultimately, what is your question? I see only a problem statement, but not a question about the problem. $\endgroup$ – D.W. Jun 24 '17 at 17:28

Your Answer

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

Browse other questions tagged or ask your own question.