Het vlak kleuren

Vorige maand (april 2018) is er een stap gezet op weg naar de oplossing van het volgende probleem: “hoeveel kleuren heb je nodig om de punten van het vlak te kleuren en wel zo dat punten op afstand 1 verschillende kleuren krijgen. De titel van het artikel in de Volkskrant is misleidend want het probleem is nog niet opgelost; de titel van het stuk in NRC is correct.

Beide stukken waren niet zo duidelijk als men wellicht hoopte, getuige bijvoorbeeld de commentaren in de facebookgroep ‘Leraar Wiskunde’. De opmerkingen over de voorbeelden in de Volkskrant werden niet altijd begrepen en de pixelmetafoor in NRC leidde tot misverstanden over de aard van het probleem.

Wat bekend was over het probleem tot vorige maand was het volgende. Door middel van een betegeling van het vlak met behulp van regelmatige zeshoeken met diameter 1 kun je een kleuring met zeven kleuren maken. Hierbij moet je wel precies zijn: bij elke zeshoek neem je de randpunten van zes uur tot twaalf uur mee (inclusief zes uur exclusief twaalf uur) en laat je de andere randpunten weg. Elke tegel krijg namelijk een kleur en op deze manier vermijdt je dat randpunten op afstand 1 dezelfde kleur krijgen.

De voorbeelden in het NRC-artikel zijn duidelijk: als je de punten van het vlak met twee kleuren kleurt dan zijn er in een gelijkzijdige driehoek met zijden 1 al twee punten met dezelfde kleur. Daarnaast is er een configuratie van zeven punten te zien waarvoor bij elke kleuring met drie kleuren twee punten met afstand 1 zijn die dezelfde kleur krijgen.

Het nieuwe is een configuratie van 1581 punten, gevonden door Aubrey de Grey waarin hetzelfde geldt, maar nu voor vier kleuren; dus, hoe je die punten ook kleurt met vier kleuren er zullen er altijd twee zijn met afstand 1 en dezelfde kleur. Inmiddels is 1581 teruggebracht tot 633.

De pixelmetafoor uit NRC leidde tot een onderschatting van het probleem; dat kwam door een subtiel verschil tussen pixels en de punten van het vlak: in tegenstelling tot pixels hebben punten in het vlak geen directe buren en geen oppervlakte, ook zijn ze niet vierkant. De echte formulering van het probleem vraagt naar het kleinste natuurlijke getal n met de eigenschap dat er een functie van het vlak naar {1,2,…,n} is met de eigenschap dat als d(x,y)=1 dan f(x)≠f(y). Daar komt geen verf of kwast aan te pas en de vorm of oppervlakte van een punt is ook niet van belang.

Achter de voorbeelden die laten zien dat een bepaald aantal kleuren niet volstaat zit een stelling van De Bruijn en Erdös: als elke eindige deelverzameling van het vlak een goede kleuring met k kleuren toelaat dan laat het vlak ook een goede kleuring toe. Met andere woorden: om te laten zien dat er geen goede kleuring is moet je een eindige verzameling zonder goede kleuring vinden.

Overigens zou dit nog tot twee verschillende oplossingen van het probleem kunnen leiden: de stelling van De Bruijn en Erdös geldt onder aanname van het keuzeaxioma. In dit artikel van Shelah en Soifer is te lezen dat de aard van de gevraagde functie het antwoord kan beïnvloeden. Lang voor het werk van De Grey was bekend dat een Lebesgue-meetbare kleuring ten minste vijf kleuren zou vergen. NB de laatste stelling in het artikel van Shelah en Soifer is nu achterhaald.

Ten slotte: houd de Wikipediapagina over dit probleem in de gaten.

Toevoeging (2018-05-14): het hieronder in een reactie genoemde artikel op Kennislink is ook zeer informatief.

Be Sociable, Share!

• 
•