Set is een onverwacht diep kaartspel

Een Nederlandse wiskundige zet een forse stap vooruit in de analyse van Set, het kaartspel dat vooral in de beginjaren van deze eeuw in Nederland erg populair was. Het gaat om Dion Gijswijt, een wiskundige van de TU Delft die is gespecialiseerd in zogeheten combinatorische optimalisatie.

Het spel Set bevat 81 kaarten waarop patronen zijn getekend. Die patronen hebben vier eigenschappen: vorm, kleur, vulling en aantal. Elk van die eigenschappen komt in drie soorten voor: drie vormen (rechthoek, ovaal en golf), drie kleuren (rood, groen en paars), drie vullingen (vol, leeg en gearceerd) en drie aantallen (1, 2 en 3). Alle combinaties komen voor, dus er zijn 34 = 81 kaarten.

Een ‘set’ is een groepje van drie kaarten waarvoor geldt dat elke eigenschap op de drie kaarten óf hetzelfde is, óf compleet verschillend. De illustratie toont twaalf kaarten met maar liefst zes sets.

De kans dat een serie van twaalf kaarten géén set bevat, is 1/34. Die kans neemt natuurlijk af naarmate het aantal kaarten toeneemt. Het grootste aantal kaarten dat nog ‘setvrij’ kan zijn, is 20. Vanaf 21 kaarten ben je verzekerd van een set.

Je kunt het spel complexer maken door kaarten met méér dan vier eigenschappen te maken. ‘Grootte’, ‘dikte van de rand’ – in theorie kun je zoveel eigenschappen toevoegen als je maar wilt. Met n eigenschappen zijn er 3n verschillende kaarten. Zelfs voor kleine waarden van n is het knap lastig om het maximale aantal kaarten te bepalen dat nog setvrij kan zijn. Voor n = 5 is dit aantal 45, voor n = 6 is het 112. Voor grotere waarden van n is dit een onopgelost probleem.

De Nederlander Gijswijt heeft nu aangetoond dat het maximale aantal kaarten dat setvrij kan zijn, relatief gezien exponentieel afneemt naarmate n groter wordt: van de 3n kaarten in totaal kan een setvrije serie niet meer dan (ongeveer) 2,756n kaarten hebben. In een spel met 100 eigenschappen gaat het dan om 0,02 procent van het totale aantal kaarten. Met 200 eigenschappen is dit percentage nog maar 0,0000043 procent. Volgens Gijswijt is deze exponentiële afname een onverwacht resultaat. Overigens kwam Jordan Ellenberg (University of Wisconsin) tegelijkertijd, onafhankelijk van Gijswijt, met dezelfde bevinding.

Alleen maar spielerei? „Nee”, zegt Gijswijt. „Dit setprobleem hangt samen met tal van open problemen in de wiskunde.” Een spectaculair voorbeeld is het zogeheten ‘zonnebloemvermoeden’ van Erdös en Szemerédi: dat is nu ook in één klap opgelost. De oplossing van een ander vermoeden, van Erdös en Rado, ligt nu in het verschiet. Bekende wiskundigen, zoals Fieldsmedaillewinnaars Timothy Gowers en Terence Tao, blogden over het werk van Gijswijt en Ellenberg. Zo belangrijk is het.

De zes sets in de figuur zijn: ABK, BFG, BHL, CGH, DKL en EIL.