\
\
voorpagina
prijsvragen
puzzels
wis-spellen
veelvlakken
drogredeneringen
vermoedens
topologie
rekenwerk
'Vier kleuren is voldoende', zegt de computer
Mersenne-priemgetallen
Rekenwerk bij het KNMI
Rekenmeisjes en rekentuig
Gedistribueerde berekeningen
Bewijzen nalopen met de computer
Vedische wiskunde
links

Abonnementen en adreswijzigingen: 0522 855175 • EnglishContactAbonnementen
WISKUNDETIJDSCHRIFT VOOR JONGEREN
\
'Vier kleuren is voldoende', zegt de computer door Marco Swaen, Jan Guichelaar

 


1: Het vierkleurenprobleem
2: Wat is een kaart?
3: De telformule
4: De methode van het reduceren
5: Het 'bewijs' van Kempe
6: Ontladen
7: De hulp van de computer

In de eerste helft van de twintigste eeuw gingen de onderzoeken verder op het spoor van een onvermijdelijke set van reduceerbare configuraties. De Duitser Heinrich Heesch (1906-1995) speelde in dit onderzoek een centrale rol. Van hem stamt de techniek van het 'ontladen' waarmee nieuwe onvermijdelijke sets opgespoord kunnen worden, zoals de onvermijdelijke set {tweehoek, driehoek, vierhoek, twee vijfhoeken aan elkaar, een vijf- en zeshoek aan elkaar}, zie figuur 6.

Figuur 6 Onvermijdelijke set {tweehoek, driehoek, vierhoek, twee vijfhoeken aan elkaar, een vijf- en zeshoek aan elkaar}

We laten zien hoe je met ontladen kunt bewijzen dat elke kaart inderdaad ten minste één van deze configuraties moet bevatten.
Ken aan elk land de 'lading' 6 - k (k is het aantal grenzen) toe. Vijfhoeken hebben dus lading 1, zeshoeken lading 0, zevenhoeken -1, achthoeken -2, enzovoorts.
Stel nu (tegen beter weten in) dat geen van de configuraties uit figuur 6 in de kaart voorkomt. Bereken de totale lading van de hele kaart. Omdat er geen twee-, drie- of vierhoeken in voorkomen, geldt: c2 = c3 = c4 = 0. De totale lading van de kaart is dan: 1 × c5 + (-1) × c7 + (-2) × c8 + (-3) × c9- .... Volgens de telformule levert dit: c5 - c7 - 2c8 - 3c9 - ... = 12; de totale lading is dus 12.
Verdeel nu (ontladen) de lading 1 van elke vijfhoek netjes (5 keer 1/5) over zijn 5 buren. Merk op dat rond elke vijfhoek alleen zevenhoeken of hoger zitten (onze aanname) met ladingen -1, -2 enzovoorts. De lading van elke vijfhoek wordt dus 0, die van elke zeshoek blijft 0 en die van elke zevenhoek of hoger worden -4/5, -9/5, enzovoorts. De totale lading van de landkaart is dan dus negatief. Maar de totale lading is 12 en positief. We stuiten op een tegenspraak, en concluderen dat er geen kaart kan bestaan waarin niet ten minste één van de vijf configuraties voorkomt.



prev | 1 | 2 | 3 | 4 | 5 | 6 | 7 | next
[printversie]
Uit Pythagoras nummer juni 2004

pythagoras op papier

 

laatste nummervorig nummerarchiefover pythagoras
abonnementenpostersoude jaargangenkennismakingsnummerVan viervlak naar ster
 
rekenwerk

 

In jaargang 2003-2004 is het thema van Pythagoras "het rekenwerk" met artikelen over de enorme veranderingen die de afgelopen vijftig jaar hebben plaatsgevonden op rekengebied. Werden vijftig jaar geleden nog tabellen berekend met de hand en met eenvoudige rekenmachines, nu zijn we bijna zover dat we het nalopen van bewijzen uitbesteden aan de computer.
   
Gerelateerde artikelen

 

Het kleuren van kaarten
Kaartenmakers weten allang dat je aan vier kleuren genoeg hebt om de landen van een kaart zo te kleuren dat buurlanden nooit dezelfde kleur krijgen. Wiskundigen echter slaagden er lange tijd niet in een bewijs te leveren voor dit ervaringsfeit, dat dan ook bekend stond als het vierkleurenprobleem. De bewijzen, die inmiddels wel gevonden zijn, zijn nog steeds dermate ingewikkeld dat ze zonder computer niet geleverd noch gecontroleerd kunnen worden. Vreemd genoeg blijkt het kleurenprobleem voor landkaarten op ingewikkeldere oppervlakken een heel stuk gemakkelijker.