Vereinfachend sei angenommen, dass jeder Tisch einen Platz im Norden, einen im Osten, einen im Süden und einen im Westen hat. Es gibt nun Lösungen, bei denen die Gäste in allen Runden in gleicher Himmelrichtung sitzen. Man kann solche Lösungen sehr schön finden, wenn man zum Erzeugen der Sitzordnung die bitweise
XOR Verknüpfung auf die Nummer n = 0..7 der Gäste einer Himmelsrichtung (Nordgäste, Ostgäste, ...) verwendet. Die acht Tische seinen von t = 0..7 nummeriert und in jeder Runde legt man für jede Himmelrichtung eine Zahl z = 0..7 fest, so dass mit t = n XOR z die acht Leute n = 0..7 einer Himmelsrichtung auf die acht Tische verteilt werden.
EinmalbedingungOffenbar sind niemals zwei Gäste einer Himmelsrichtung in einer Gruppe, denn sonst müssten z.B. zwei Stühle an der Nordseite eines Tisches stehen. Angenommen die Einmalbedingung wäre für Gäste aus verschiedenen Himmelsrichtungen verletzt.
ZB. Nordgast n und Südgast m sitzen in Runde 1 und 3 zusammen in einer Gruppe.
t = n XOR z(N,1) = m XOR z(S,1) ---> n XOR m = z(N,1) XOR z(S,1)
t' = n XOR z(N,3) = m XOR z(S,3) ---> n XOR m = z(N,3) XOR z(S,3)
---> z(N,1) XOR z(S,1) = z(N,3) XOR z(S,3) (**)
Genau dann, wenn Gleichung (**) nie (für keine zwei verschiedene Himmelrichtungen und keine zwei verschiedenen Runden) erfüllt ist, wird die "Einmalbedingung" erfüllt.
Jetzt kann man geeignete z Werte für jede Runde und Himmelsrichtung suchen. Mit nur 3 Himmelsrichtungen z.B. Norden, Osten und Süden ist es nicht schwer.
Runde: 1, 2, 3, 4
N = {0, 1, 2, 3}
O = {0, 2, 3, 1}
S = {0, 3, 1, 2}
Offenbar ist N XOR O = S wobei die XOR Verknüpfung paarweise auf die Vektorkomponenten der Vektoren N und O angewendet wird.
Dann gilt auch N XOR S = O und O XOR S = N. Da nun die Komponenten jedes Vektors auf der rechten Seite der letzten drei Gleichungen
verschieden sind, wird Gleichung (**) nie erfüllt.
Fährt man mit
W = {0, 1, 3, 2}
fort dann erhält man:
N XOR W = {0, 0, 1, 1}
O XOR W = {0, 3, 0, 3}
S XOR W = {0, 2, 2, 0}
Hier wird (**) für jede Kombination mit W, genau zweimal erfüllt. Das kann man beheben, wenn man an geeigneten Komponenten in N, O und W eine 4 addiert:
Runde: 1, 2, 3, 4
N = {0, 4+1, 2, 4+3}
O = {0, 2, 4+3, 4+1}
S = {0, 3, 4+1, 4+2}
W = {0, 1, 3, 2}
Durch die Addition der 4 bleibt die Einmalbedingung zwischen N, O und S weiterhin erfüllt und nun ist sie auch für alle Kombinationen mit den Westgästen erfüllt.
ThemenNun muss noch geprüft werden, ob jedes Thema von jedem Gast besprochen wurde. Wenn an Tisch t und Tisch t+4 über das gleiche Thema gesprochen wird, erwischt jeder Gast jedes Thema, da jeder Vektor N, O, S und W in den vier Komponenten alle 4 Bitkombinationen der beiden niederwertigen Bits enthält. Das hab ich natürlich schon vorher berücksichtigt und nur solche Vektoren N, O, S und W ausprobiert. Da man die Sitzordnung mit den unten gefundenen Vektoren N, O, S und W ausrechnen kann, erspare ich mir, diese hier aufzuschreiben.