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.