Je leest:

17 × 17 probleem opgelost

17 × 17 probleem opgelost

Auteur: | 14 februari 2012

Het vierkant hieronder lijkt op het eerste gezicht een willekeurige kleuring van 17 × 17 vakjes. Maar achter deze schijnbare willekeur gaat wiskunde schuil. Het vierkant is namelijk de oplossing van het zogeheten ‘17 × 17 probleem’.

In 2009 plaatsten Lance Fortnow en Bill Gasarch op hun blog een mathematische puzzel: het 17 × 17 probleem. Voor een oplossing loofden zij 17 × 17 = 289 dollar uit.

Uitgangspunt van de puzzel is een vierkant bestaande uit 17 × 17 vakjes. Je mag vier verschillende kleuren gebruiken. De bedoeling is om elk van de 289 vakjes een kleur te geven, en wel zodanig dat er geen monochromatische rechthoek ontstaat. Een monochromatische rechthoek is een rechthoek waarvan de vier hoekvakjes dezelfde kleur hebben. Alleen rechthoeken waarvan de vier zijden op de roosterlijnen liggen en waarvan de lengte en de breedte groter dan 1 zijn, tellen mee.

Onderstaande kleuring toont een oplossing. Welke rechthoek je ook kiest, nooit hebben de vier hoekvakjes allemaal dezelfde kleur. Neem bijvoorbeeld de rechthoek waarvan de hoekvakjes de coördinaten (B, 3), (F, 3), (F, 11) en (B, 11) hebben: deze hebben respectievelijk de kleuren blauw, blauw, rood, geel.

Alex van den Brandhof

Hoe eenvoudig het raadsel ook klinkt, het duurde meer dan twee jaar totdat iemand met een oplossing kwam. De credits zijn voor Bernd Steinbach en Christian Posthoff. Bovendien vonden zij dat een 18 × 18 vierkant met vier kleuren gekleurd kan worden onder dezelfde voorwaarden.

Zelf aan de slag

Lance Fortnow en Bill Gasarch zijn nog geïnteresseerd in de vraag of een 12 × 21 rechthoek gekleurd kan worden met vier kleuren, zonder dat er een monochromatische rechthoek ontstaat. Als je een correcte invulling vindt, laat het mij, Lance Fortnow en William Gasarch weten!

Update 18 februari 2012:

het 12 × 21 probleem is inmiddels ook opgelost, zie deze reactie van Bernd Steinbach op de blog van Fortnow en Gasarch.

Complexiteitstheorie

De puzzel is niet alleen een recreatieve bezigheid. Het is een puzzel uit een dieperliggend probleem over het kleuren van grids zonder monochromatische rechthoeken. De resultaten zijn van belang binnen de complexiteitstheorie, een tak van de wiskunde en theoretische informatica die als doel heeft computationele problemen te classificeren in een aantal categorieën die de inherente moeilijkheidsgraad van deze problemen aangeven. Het P-versus-NP-probleem is uit dit deelgebied van de wiskunde afkomstig. Dit probleem staat op de lijst van millenniumproblemen, waarmee een miljoen dollar verdiend kan worden.

Zie ook:

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 14 februari 2012

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.