Het cirkelprobleem van Moser: waarom na 1, 2, 4, 8, 16 geen 32 komt

Zet enkele punten op een cirkel en verbind elk tweetal met een recht lijnstuk. In hoeveel stukken wordt de cirkelschijf verdeeld? De eerste tekeningen lijken een bijzonder eenvoudige regel te verklappen. Maar net wanneer je denkt dat je het patroon doorhebt, gaat het mis.

1. Een patroon dat bijna niet fout kan zijn

We plaatsen de punten op de omtrek. Het lijnstuk tussen twee punten heet een koord. We tekenen alle mogelijke koorden, ook die tussen naburige punten. Met het aantal delen bedoelen we het aantal afzonderlijke gebieden binnen de cirkel. Hun oppervlakten hoeven niet gelijk te zijn.

Eén punt levert nog geen koord op: de schijf blijft één geheel. Twee punten geven één koord en twee delen. Bij drie punten ontstaat een driehoek: één gebied binnen de driehoek en drie gebieden tussen de driehoekszijden en de cirkelboog. Samen vier.

Een, twee en drie punten op een cirkel, met alle koorden. De cirkelschijven zijn verdeeld in respectievelijk één, twee en vier gekleurde gebieden.

Eén punt: één deel. Twee punten: twee delen. Drie punten: vier delen.

Bij vier punten tekenen we de vier zijden en de twee diagonalen van een ingeschreven vierhoek. De schijf krijgt acht delen. Met vijf punten worden het er zestien.

Vier en vijf punten op een cirkel, met alle koorden. De eerste schijf heeft acht gekleurde gebieden, de tweede zestien.

Ook de volgende twee tekeningen passen bij een verdubbeling.

De rij begint dus met

    \[ 1,\quad 2,\quad 4,\quad 8,\quad 16. \]

De verleiding is groot: elk extra punt verdubbelt het aantal delen! Voor n punten zou dat betekenen

    \[ R(n)\stackrel{?}{=}2^{n-1}. \]

Dit heet weleens de ‘2^n-regel’, maar met n punten is de precieze gok 2^{n-1}. Schrijf je het aantal punten als n+1, dan voorspelt hetzelfde vermoeden 2^n delen.

Met zes punten verwachten we dan 32 delen. Toch zijn het er hoogstens 31. In deze tekening kun je ze natellen:

Zes punten op een cirkel met alle vijftien koorden. De 31 ontstane gebieden hebben een kleur en zijn genummerd van 1 tot en met 31.

Het zesde geval doorbreekt het patroon: 31 delen, geen 32.

Dit is het cirkelprobleem van Moser, genoemd naar Leo Moser. Het laat zien hoe overtuigend een patroon kan zijn, zolang het bewijs ontbreekt.

2. Eerst een belangrijke afspraak: we zoeken het maximum

Het aantal delen hangt ook af van de plaats van de punten. Zet je zes punten op gelijke afstanden op de cirkel, dan gaan drie diagonalen door het middelpunt. Die extra symmetrie heeft een onverwacht gevolg: je krijgt slechts 30 delen.

Links een regelmatige zeshoek met alle koorden: drie diagonalen ontmoeten elkaar in het middelpunt en er ontstaan dertig gebieden. Rechts een ongelijke plaatsing zonder drievoudige kruising, met 31 gebieden.

Een mooi regelmatige tekening geeft hier niet het grootste aantal delen.

We zoeken daarom het grootst mogelijke aantal delen bij n verschillende randpunten. Dat maximum noemen we R(n).

Voor de berekening kiezen we de punten zo dat geen drie koorden door hetzelfde punt binnen de cirkel gaan. Dit heet hier een ligging zonder drievoudige kruisingen. Dat veel koorden bij een randpunt samenkomen, is uiteraard wel toegestaan.

Zo’n plaatsing is altijd mogelijk. Als je een nieuw randpunt kiest, hoef je maar eindig veel plaatsen te vermijden: de plaatsen waarvoor een nieuw koord precies door een bestaande inwendige kruising zou lopen. Op de cirkel blijven nog oneindig veel andere plaatsen over.

We berekenen eerst het aantal delen voor zo’n plaatsing. Verderop leggen we uit waarom samenvallende kruisingen nooit méér delen kunnen geven.

3. Van een tekening naar een graaf

Alle gebiedjes tellen wordt snel onoverzichtelijk. De grafentheorie, de wiskunde van knopen en verbindingen, helpt ons om iets gemakkelijker telbaars te gebruiken.

We maken van de hele tekening een netwerk:

  • Elk oorspronkelijk randpunt wordt een knoop.
  • Elke kruising binnen de cirkel wordt eveneens een knoop.
  • Elk stukje koord tussen twee opeenvolgende knopen wordt een rand.
  • Ook de cirkelbogen tussen twee opeenvolgende randpunten tellen als randen.

Een graafrand mag dus gebogen zijn. Bovendien zijn een koord tussen twee naburige punten en de cirkelboog tussen dezelfde punten twee verschillende randen: samen omsluiten ze een gebiedje.

De cirkeltekening voor vier punten, naast dezelfde tekening als vlakke graaf. De vier randpunten zijn groen en de ene inwendige kruising is goud. Er zijn vijf knopen, twaalf randen en negen vlakken als ook het buitengebied wordt meegeteld.

Een kruising wordt een echt knooppunt. Daardoor eindigen de graafranden daar en lopen ze niet meer over elkaar heen.

Het resultaat is een vlakke graaf: een netwerk in het vlak waarvan de randen elkaar alleen bij knopen ontmoeten. Het netwerk is ook samenhangend: je kunt van elke knoop langs de randen naar elke andere knoop wandelen.

Eerst de kruisingen in knopen veranderen! Euler meteen toepassen op alleen de randpunten en de oorspronkelijke koorden zou een verkeerde telling geven.

4. De formule van Euler

Voor een samenhangende vlakke graaf geldt

    \[ V-E+F=2. \]

Hierin zijn V, E en F het aantal knopen, randen en vlakken. Bij de vlakken telt ook het onbegrensde buitengebied mee. De formule geldt ook voor onze graaf met gebogen en meervoudige randen.

Waarom is die formule aannemelijk? Begin met een samenhangend netwerk zonder gesloten rondweg. Zo’n netwerk heet een boom. Een boom heeft één rand minder dan knopen: vanaf één knoop voeg je telkens een nieuwe knoop toe met één verbinding naar het bestaande netwerk. Er ontstaat geen afgesloten gebied. Het vlak blijft één geheel, dus F=1. Daarom

    \[ V-(V-1)+1=2. \]

Voeg nu de overige randen van een samenhangende vlakke graaf één voor één toe, zonder nieuwe knopen te maken. Elke toegevoegde rand sluit een rondweg en splitst één bestaand vlak in tweeën. Zowel E als F stijgt met één; V-E+F blijft gelijk.

Dit is ook een bewijs: elke eindige samenhangende graaf bevat een boom die alle knopen bereikt. Je vindt die door randen uit gesloten rondwegen weg te nemen zolang dat kan; de samenhang blijft behouden. Daarna kun je de verwijderde randen terugplaatsen.

Links een boom met vier knopen, drie randen en één vlak. Rechts is één rand toegevoegd die een gesloten rondweg maakt: er zijn nu vier randen en twee vlakken. In beide gevallen is V min E plus F gelijk aan twee.

Een extra rand die een vlak opsplitst, geeft tegelijk één extra vlak. Het verschil blijft gelijk.

Bij onze cirkel zijn er R gebieden binnen de cirkel en één erbuiten. Dus F=R+1. De formule van Euler wordt

    \[ V-E+(R+1)=2, \]

en daarmee

    \[ \boxed{R=E-V+1.} \]

We hoeven nu alleen nog de knopen en randen te tellen.

5. Twee randpunten kiezen, vier randpunten kiezen

Hoeveel koorden zijn er?

Elk koord ligt vast zodra je twee verschillende randpunten kiest. De volgorde doet er niet toe: het koord van A naar B is hetzelfde als dat van B naar A.

Het aantal manieren om twee van n punten te kiezen, schrijven we als \binom n2, uitgesproken als ‘n kies twee’. Elk van de n punten kan met n-1 andere worden verbonden. Omdat we elke verbinding zo tweemaal tellen, is het aantal koorden

    \[ C=\binom n2=\frac{n(n-1)}2. \]

Voor zes punten zijn dat 6\cdot5/2=15 koorden.

Hoeveel inwendige kruisingen zijn er?

Kies vier randpunten en noem ze A, B, C en D, in de volgorde waarin je ze langs de cirkel tegenkomt. Ze vormen een bolle vierhoek. De diagonalen AC en BD kruisen elkaar precies eenmaal binnen de cirkel.

Van de drie manieren om deze vier punten in twee paren te verdelen, levert dus maar één een inwendige kruising op. AB en CD kruisen niet, en AD en BC evenmin.

Zes randpunten met vier geselecteerde punten A, B, C en D in cirkelvolgorde. De koorden AC en BD zijn in twee kleuren benadrukt; hun ene inwendige kruising is goud.

Vier randpunten bepalen één kruisend koordenpaar. De overige verbindingen zijn licht getekend.

Omgekeerd heeft elk kruisend koordenpaar vier verschillende eindpunten. Koorden met een gemeenschappelijk randpunt kunnen elkaar niet nog eens binnen de cirkel snijden.

Er is dus een koppeling in beide richtingen: vier randpunten kiezen is hetzelfde als een kruisend koordenpaar kiezen. Omdat we drievoudige kruisingen vermijden, horen bij verschillende kruisende paren ook verschillende kruispunten.

Het aantal inwendige kruispunten is daarom

    \[ I=\binom n4=\frac{n(n-1)(n-2)(n-3)}{24}. \]

De noemer is 24=4\cdot3\cdot2\cdot1: je kunt dezelfde vier gekozen punten in 24 volgordes opsommen, maar hun volgorde van kiezen is niet van belang. Als n<4, kun je geen vier punten kiezen en is \binom n4=0.

Voor zes randpunten: I=\binom64=15.

6. De knopen en de randen tellen

Knopen: randpunten én kruisingen

Er zijn n oorspronkelijke randpunten en I inwendige kruispunten. Dus

    \[ V=n+I. \]

Randen: cirkelbogen én stukken koord

De n randpunten verdelen de cirkelomtrek in n bogen. Die leveren n graafranden.

Nu de rechte stukken. Zonder onderverdeling zouden de C koorden samen C stukken geven. Een kruispunt verdeelt elk van de twee betrokken koorden een keer extra. Er komen dus per kruispunt twee stukken bij.

Twee kruisende koorden, naast hun opsplitsing in vier gekleurde graafranden. Het gemeenschappelijke kruispunt is een extra knoop; op elk koord komt één lijnstuk bij.

Twee koorden worden vier stukken. Eén kruispunt betekent één extra knoop, maar twee extra koordstukken.

Met I kruispunten krijgen we C+2I rechte stukken. Inclusief de cirkelbogen is dus

    \[ E=n+C+2I. \]

Een andere manier om dezelfde telling te zien: een koord met k kruispunten bestaat uit k+1 stukken. Tel je dit over alle koorden op, dan tel je elk kruispunt tweemaal, eenmaal op elk betrokken koord. Ook zo vind je C+2I.

7. Alles valt op zijn plaats

We vullen de twee tellingen in bij Euler:

    \[ \begin{aligned} R&=E-V+1\\ &=\bigl(n+C+2I\bigr)-\bigl(n+I\bigr)+1\\ &=1+C+I. \end{aligned} \]

Met C=\binom n2 en I=\binom n4 krijgen we de gezochte formule:

    \[ \boxed{R(n)=1+\binom n2+\binom n4.} \]

Of volledig uitgeschreven:

    \[ R(n)=1+\frac{n(n-1)}2 +\frac{n(n-1)(n-2)(n-3)}{24}. \]

Voor zes punten is de hele berekening nu te volgen:

    \[ V=6+15=21,\qquad E=6+15+2\cdot15=51. \]

Dus

    \[ \boxed{R(6)=51-21+1=31.} \]

Bij vier punten was het V=4+1=5, E=4+6+2=12, en dus R=12-5+1=8, precies zoals in de graaftekening.

Aantal punten n Koorden \binom n2 Kruispunten bij algemene ligging \binom n4 Maximum R(n) De gok 2^{n-1}
1 0 0 1 1
2 1 0 2 2
3 3 0 4 4
4 6 1 8 8
5 10 5 16 16
6 15 15 31 32
7 21 35 57 64
8 28 70 99 128
9 36 126 163 256
10 45 210 256 512

De waarden komen overeen met rij A000127 in de OEIS. Het geval van één punt kun je apart aflezen: er is nog niets verdeeld en de formule geeft één deel.

8. Waarom zijn samenvallende kruisingen ongunstig?

We moeten nog verantwoorden dat onze formule het maximum geeft.

Stel dat een nieuw koord in k verschillende punten door de al getekende koorden wordt gesneden. Dan bestaat het uit k+1 stukjes. Elk stukje snijdt één bestaand gebied in tweeën: er komen k+1 gebieden bij. Dat zijn verschillende gebieden. Elk gebied is namelijk convex: het lijnstuk tussen twee punten ervan blijft volledig binnen dat gebied. Dat komt doordat de gebieden ontstaan door de cirkelschijf telkens aan één kant van een rechte lijn te houden. Een recht koord kan eenzelfde gebied dus niet verlaten en later opnieuw binnengaan.

Laat een koord bijvoorbeeld twee oude koorden ontmoeten. Bij twee verschillende ontmoetingspunten ontstaan drie stukken en drie nieuwe gebieden. Vallen de ontmoetingen samen, dan zijn er maar twee stukken en twee nieuwe gebieden. Samenvallende kruisingen leveren dus minder op.

Teken je alle koorden één voor één, dan kan elk koord zelf één nieuw gebied bijdragen en kan elk kruisend koordenpaar hoogstens één verdere bijdrage leveren. Er zijn \binom n2 koorden en \binom n4 kruisende paren. Met het oorspronkelijke gebied erbij is de bovengrens

    \[ 1+\binom n2+\binom n4. \]

Zonder drievoudige kruisingen bereiken we die grens, zoals Euler aantoonde. Daarmee is het maximum bewezen.

9. Waarom werkte de verdubbeling dan vijf keer?

Het begin van de rij is niet zomaar willekeurig. Er is zelfs een verklaring voor de vijf treffers.

Een verzameling met n elementen heeft 2^n deelverzamelingen: elk element kies je wel of niet. Voor n\geq1 heeft precies de helft daarvan een even aantal elementen. Je kunt de even en de oneven deelverzamelingen in paren zetten door één vast element telkens toe te voegen of weg te nemen.

Daarom geldt

    \[ 2^{n-1}=\binom n0+\binom n2+\binom n4+\binom n6+\cdots. \]

Onze cirkelformule bevat alleen de eerste drie termen:

    \[ R(n)=\binom n0+\binom n2+\binom n4. \]

Zolang er hoogstens vijf punten zijn, kun je geen zes of meer punten kiezen. De ontbrekende termen zijn dan allemaal nul. Daarom vallen de twee formules samen.

Bij zes punten verschijnt voor het eerst de extra term \binom66=1 in de machten-van-twee-formule, terwijl die niet in de cirkelformule zit:

    \[ 2^5=1+15+15+1=32, \qquad R(6)=1+15+15=31. \]

De ontbrekende één is dus geen zoekgeraakt gebiedje. Het is het eerste zichtbare verschil tussen twee verschillende telproblemen.

Zelf proberen

  1. Hoeveel delen kun je maximaal krijgen met acht randpunten? Bereken eerst afzonderlijk het aantal koorden en het aantal kruisingen.
  2. Waarom mag je bij het gebruik van Euler het buitengebied niet vergeten?
  3. Bij tien punten is het maximum opnieuw een macht van twee: 256. Is de oorspronkelijke verdubbelingsregel daarmee hersteld?

Antwoorden: 1. 1+28+70=99. 2. Euler telt alle vlakken van de graaf in het hele vlak; daarom is F=R+1. 3. Nee: 256=2^8, terwijl de gok voor tien punten 2^9=512 voorspelt. Eén nieuwe overeenkomst met een macht van twee bewijst geen algemene regel.