Onmogelijkheid van OP(9;5,4)
Op deze pagina bewijzen we dat het onmogelijk is om negen mensen vier dagen achter elkaar aan een ronde tafel voor vier personen en een ronde tafel voor vijf personen te zetten zodat na deze vier dagen iedereen naast iedereen heeft gezeten.
Om dit te bewijzen zullen we alle niet-isomorfe tafelopstellingen voor de eerste twee dagen proberen te bepalen. Dit levert twee viercykels en twee vijfcykels op in een graaf met negen punten; deze cykels hebben geen edge met elkaar gemeen en in elke vertex zullen precies twee cykels komen. We merken op: een tafelopstelling voor de laatste twee dagen zal er net zo uit moeten zien. We kunnen dus kijken naar de complementen van de tafelopstellingen (grafen) voor de eerste twee dagen. Als deze allemaal ongelijk zijn aan de oorspronkelijke tafelopstellingen voor de eerste twee dagen kunnen we concluderen dat OP(9;5,4) geen oplossing heeft; immers een tafelopstelling voor de eerste twee dagen kan er dan niet zo uitzien als een tafelopstelling voor de laatste twee dagen.
De eerste dag levert ons geen probleem op: er is maar een niet-isomorfe tafelopstelling: deze bestaat uit een viercykel en een vijfcykel. De negen punten uit de graaf (de personen) nummeren we 1 tot en met 9 en we nemen aan dat de personen 1, 2, 3 en 4 naast elkaar aan een tafel zitten. We noteren dit (1 2 3 4). Verder nemen we aan dat de personen 5, 6, 7, 8 en 9 in die volgorde naast elkaar aan een tafel zitten. We noteren dit (5 6 7 8 9). Hierbij zit persoon 5 dus ook naast persoon 9 omdat er sprake is van ronde tafels. Elke tafelopstelling voor de eerste dag is dus isomorf aan: (1 2 3 4)(5 6 7 8 9).
Voor dag twee zullen we helaas flink wat gevalsonderscheidingen moeten maken. We kijken hierbij steeds eerste naar de viercykel van dag twee. We maken een gevalonderscheiding naar het aantal vertices dat deze viercykel in doorsnede heeft met de viercykel van dag 1. Dit kunnen er 0, 1, 2, 3 of 4 zijn; het geval van twee vertices in doorsnede behandelen we helemaal op het eind.
Geen vertex in doorsnede
In dit geval zullen vier vertices van de vijfcykel binnen de viercykel van dag een moeten komen. Dit zijn hoe dan ook vier opeenvolgende vertices waartussen we drie niet eerder gebruikte edges moeten trekken. Dit kunnen er echter nog maar twee zijn. We kunnen zo dus nooit een tafelopstelling krijgen.
Een vertex in doorsnede
We kunnen zonder verlies van algemeenheid aannemen dat de vertex in de doorsnede vertex 1 is. Om een viercykel te krijgen moeten we daarna naar een van de vertices 5, 6, 7, 8 of 9. We kunnen aannemen dat dit 5 is. Dus we hebben (1 5 x x). Naar vertex 6 en 9 mogen we niet meer en vertex 7 en 8 liggen isomorf in de graaf. Zeg dus dat we (1 5 7 x) krijgen. Daarna kunnen we alleen nog naar vertex 9 dus de viercykel komt er als (1 5 7 9) uit te zien. Van de vijfcykel moeten we drie vertices binnen de viercykel van dag 1 kwijt. Daarvan moeten er twee opeenvolgend zijn, dit kunnen alleen nog vertices 2 en 4 zijn. We krijgen dus (2 4 x x x). Vertices 6 en 8 liggen isomorf in de graaf, dus (2 4 6 x x). Omdat vertex 3 niet aan vertex 2 mag grenzen krijgen we dan (2 4 6 3 8). Hiermee krijgen we onze eerste tafelopstelling voor twee dagen: (1 5 7 9)(2 4 6 3 8).
Drie of vier vertices in doorsnede
Met drie vertices in de doorsnede kunnen we aannemen dat we vertex vier niet gebruiken. Voor de viercykel zoeken we dan twee opeenvolgende edges tussen de overige drie punten die nog niet gebruikt zijn. De enige edge die we echter nog kunnen gebruiken is die tussen vertices 1 en 3. Dit kan ons dus geen nieuwe tafelbezetting opleveren. Met vier vertices in de doorsnede hebben we vier edges in de viercykel nodig terwijl alleen de edges (1,3) en (2,4) nog ongebruikt zijn. Ook dit zal ons geen nieuwe tafelbezetting opleveren.
Twee vertices in de doorsnede
Verreweg het meest ingewikkelde geval is met twee vertices in de doorsnede van de twee viercykels. We maken daarom nog een gevalsonderscheiding.
Naast elkaar gelegen vertices
Stel dat de twee vertices van de tweede viercykel in de eerste viercykel naast elkaar liggen. We kunnen dan aannemen dat de tweede viercykel bijvoorbeeld vertices 1 en 2 bevat, maar ook dat deze twee vertices niet door de tweede viercykel rechtstreeks met elkaar verbonden worden (dat gebeurt met de eerste al). We krijgen dan (1 x 2 x). Welk punt uit de vijfcykel we op de eerste plek zetten maakt niet uit; laten we zeggen dat dit vertex 5 is: (1 5 2 x). De overgebleven x kan nu op "afstand" 1 of 2 zitten van vertex 5 (op afstand 1 zitten de vertices 6 en 9; op afstand 2 de vertices 7 en 8).
Stel dat ze op afstand 1 van elkaar zitten. Dan kunnen we zonder verlies van algemeenheid zeggen dat we (1 5 2 6) krijgen. Vertex 3 en 4 mogen in de vijfcykel niet naast elkaar zitten: we krijgen dan (x 3 x 4 x). Van de drie overgebleven punten mogen alleen vertex 7 en 9 nog met elkaar verbonden worden, dus we krijgen (7 3 8 4 9). Dit geeft: (1 5 2 6)(7 3 8 4 9).
Stel dat ze op afstand 2 van elkaar zitten. Dan kunnen we zonder verlies van algemeenheid zeggen dat we (1 5 2 7) krijgen. Vertex 3 en 4 mogen in de vijfcykel niet naast elkaar zitten: we krijgen dan (x 3 x 4 x). Vertex 8 en 9 mogen niet meer met elkaar verbonden worden, maar liggen we identiek in de graaf. We kunnen dus aannemen dat we (6 3 8 4 9) krijgen. Dit geeft: (1 5 2 7)(6 3 8 4 9).
Meer mogelijkheden zijn er niet binnen deze gevalsonderscheiding.
Niet naast elkaar gelegen vertices
Laten we eerst aannemen dat deze twee niet naast elkaar gelegen vertices verbonden zijn. We kunnen zonder verlies van algemeenheid vertices 1 en 3 nemen; we krijgen dan (1 3 x x). De eerste en tweede x hebben, omdat ze met elkaar verbonden worden, een onderlinge afstand van twee nodig in de tafelopstelling van dag 1. We krijgen dus (1 3 5 7).
We kunnen nu eerst aannemen dat vertices 2 en 4 ook met elkaar verbonden zijn. Omdat vertex 8 en 9 niet meer met elkaar verbonden mogen worden maar wel gelijkwaardig in de graaf liggen krijgen we zonder verlies van algemeenheid (2 4 8 6 9). Hiermee krijgen we wederom een tafelopstelling voor dag twee: (1 3 5 7)(2 4 8 6 9).
We kunnen vervolgens aannemen dat vertices 2 en 4 niet met elkaar verbonden zijn. We krijgen dan (2 x 4 x x). Vertex 8 en 9 mogen niet met elkaar verbonden worden en omdat ze gelijkwaardig in de graaf liggen krijgen we (2 8 4 6 9). We hebben dus nog een tafelopstelling voor dag twee: (1 3 5 7)(2 8 4 6 9).
We kunnen nu aannemen dat vertices 1 en 3 niet met elkaar verbonden zijn. Dus (1 x 3 x). Laten we zeggen dat de x'jes afstand 1 tot elkaar hebben, bijvoorbeeld vertices 5 en 6. We krijgen dan (1 5 3 6). Stel dat 2 en 4 met elkaar verbonden zijn. Dan moet de vijfcykel eruit komen te zien als (2 4 x x x). We zoeken dan nog twee niet gebruikte edges uit (7,8), (7,9) en (8,9); dat is niet mogelijk. Dus 2 en 4 zijn niet met elkaar verbonden: (2 x 4 x x). Alleen vertices 7 en 9 mogen nog naast elkaar zitten. We krijgen dus (2 8 4 7 9). Als tafelopstelling krijgen we dan (1 5 3 6)(2 8 4 7 9).
Vervolgens bekijken we het geval dat vertices 1 en 3 niet met elkaar verbonden zijn maar dat de x'jes afstand 2 tot elkaar hebben, bijvoorbeeld vertices 5 en 7. We krijgen dan (1 5 3 7). Stel eerst dat vertices 2 en 4 met elkaar verbonden zijn, dus: (2 4 x x x). Vertex 8 en 9 mogen niet meer met elkaar verbonden worden dus we krijgen (2 4 8 6 9). Als oplossing krijgen we dan: (1 5 3 7)(2 4 8 6 9). Stel vervolgens dat vertices 2 en 4 niet met elkaar verbonden zijn: (2 x 4 x x). Vertex 8 en 9 mogen niet met elkaar verbonden zijn dus (2 8 4 6 9). We krijgen dan als oplossing (1 5 3 7)(2 8 4 6 9).
Uiteindelijke oplossingen
Hiermee zijn we alle mogelijke oplossingen nagegaan en hebben we de volgende tafelopstellingen voor dag twee gevonden:
Met een beetje puzzelen valt het in te zien dat enkele tafelopstellingen nu isomorf zijn. De vierde tafelopstelling is isomorf aan de tweede door de verwisseling [1 2 3 4 5 6 7 8 9] <-> [1 3 5 7 4 2 9 6 8]. De vijfde tafelopstelling is isomorf aan de derde door de verwisseling [1 2 3 4 5 6 7 8 9] <-> [3 1 7 5 2 8 4 6 9]. De zevende tafelopstelling is isomorf aan de zesde door de verwisseling [1 2 3 4 5 6 7 8 9] <-> [1 5 3 7 2 4 8 6 9].
We houden dan nog vijf tafelopstellingen over. Hiervan nemen we de complementen en bekijken we of een van deze complementen isomorf is aan een van de originele. Omdat dit niet zo is kunnen we concluderen dat OP(9;5,4) geen oplossing heeft.