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.
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!
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:
- Rectangle Free Coloring of Grids (artikel van Stephen Fenner, William Gasarch en Charles Glover; pdf)
- Rectangle Free Coloring of Grids (slides van een praatje door hetzelfde drietal; pdf)