23 jul. 2009
1 minuut
Wat is het verschil tussen rijst en couscous? Het antwoord: couscous is als woord veel interessanter, want de eerste vier en de laatste vier letters zijn hetzelfde. Dergelijke repeterende woorden staan centraal in het ‘vermoeden van Dejean’, een probleem uit de combinatoriek. Het gaat over de vraag in hoeverre het mogelijk is om repeterende woorden in een oneindige rij letters te vermijden. Deze theorie heeft zijn toepassingen in onder andere de datacompressie.
Narad Rampersad bewees dat je met een 4-letter-alfabet een oneindig woord kunt construeren zonder kwadraten xx, waarbij x uit ten minste drie letters bestaat. De constructie kan op deze manier grafisch worden weergegeven, waarbij elke kleur een letter voorstelt.
Wiskundige James Currie en informaticus Narad Rampersad, beiden verbonden aan de universiteit van de Canadese stad Winnipeg, hebben het ‘vermoeden van Dejean’ opgelost, een combinatorisch probleem uit 1972. Het probleem gaat over rijtjes letters (of cijfers) waarbij de vraag in hoeverre repeterende rijtjes letters voorkómen kunnen worden, centraal staat. Dit probleem heeft toepassingen in de informatica: het is bruikbaar bij het comprimeren van computerbestanden.
Een groot deel van het wiskundige vraagstuk was al opgelost en nu zijn ook de laatste puzzelstukjes gelegd. In het raadsel staan woorden als ‘papa’, ‘kerker’, het Engelse ‘hotshots’ en het Franse ‘chercher’ centraal. Deze vier woorden hebben een bijzondere eigenschap: het zijn zogeheten kwadraten of tweedemachten: repeterende woorden die we korter kunnen schrijven als ‘(pa)2’, ‘(ker)2’, ‘(hots)2’ en ‘(cher)2’. Overigens maken we ons er in de wiskunde niet druk om als een woord niet in de Van Dale is te vinden: ook niet-bestaande woorden tellen mee. De schrijfwijze van ‘hogeremachtswoorden’ gaat op dezelfde manier als bij kwadraten: xxx (x staat voor een rijtje letters) wordt kort geschreven als x3, xxxx als x4, enzovoorts. We zeggen dat een woord van de vorm xn een n-de macht is. Dus blablabla = (bla)3 is een derdemacht.