Posts in category kleuren

Twee recente artikelen op Kennislink hebben iets gemeen. Dat gemeenschappelijke is een belangrijk stuk gereedschap uit de Wiskunde dat bekend staat als het Compactheidsbeginsel.

In 2016 werd een kleuringsprobleem voor de natuurlijke getallen opgelost: is het mogelijk de natuurlijke getallen in tweeën te delen op zo’n manier dat beide delen geen enkel Pythagoreïsch drietal bevatten? Het antwoord is: “nee”. Zoals op Kennislink te lezen is is er iets meer ontdekt: bij elke verdeling van {1,2,3,…7825} in twee delen moet een van de delen een Pythagoreïsch drietal bevatten en er is een verdeling van {1,2,3,…,7824} waarbij geen van de beide delen een bevat.
Voor de goede orde: een Pythagoreïsch drietal is een drietal natuurlijke getallen (a,b,c) dat voldoet aan a²+b²=c². Ook wordt het probleem vaak in termen van kleuringen geformuleerd: de verdeling wordt weergegeven door elk natuurlijk getal rood of blauw te kleuren.

Begin van deze maand werd vooruitgang geboekt bij een kleuringsprobleem in het platte vlak: in hoeveel verzamelingen moet je de punten in het vlak minimaal verdelen opdat geen enkel deel twee punten bevat die afstand 1 hebben. Er was lang bekend dat dat minimale aantal ten minste 4 en ten hoogste 7 is; nu is bekend dat het ten minste 5 moet zijn. Okk hier is al aan een eindige verzameling punten te zien dat bij elke verdeling in vier stukken er altijd een stuk is dat twee punten met afstand 1 bevat.

Waarom is dat? Het zou toch bij het eerste probleem zo kunnen zijn dat bij verschillende kleuringen de drietallen één kleur krijgen steeds hoger in de natuurlijke getallen moeten zitten. Maar kennelijk is het zo dat, ongeacht de kleuring er al een éénkleurig drietal is in {1,2,3,…,7825}.

Het geheim is een stelling van De Bruijn en Erdös; deze zegt dat bij elk kleurings probleem het volgende geldt: als elke eindige verzameling een `goede’ kleuring heeft dan is er een `goede’ kleuring voor de hele verzameling. Dat kun je ook als volgt contrapositief formuleren: als elke kleuring van de hele verzameling `slecht’ is dan is er een vaste eindige verzameling waarvoor elke kleuring `slecht’ is. In April 2014 is over deze stelling een artikel in Pythagoras verschenen.

Het voordeel van dit Compactheidsbeginsel is dat men voor positieve resultaten alleen naar eindige verzamelingen hoeft te kijken; dat kan de bewijzen aanzienlijk vereenvoudigen. Het nadeel is dat het niet constructief is: het geeft geen enkele informatie over de grootte van de vaste eindige verzameling waarvoor elke kleuring `slecht’ is. Dat laatste is te zien aan de resultaten waarover op Kennislink bericht werd; de zoektochten naar de eindige verzamelingen en de verificaties dat ze werkten kostten veel tijd en moeite.