Wiskundemeisjes

Fine-Wilf woorden

Belofte maakt schuld en daarom nu een stuk over Fine-Wilf woorden. Woorden zijn eigenlijk het onderzoeksonderwerp van mijn kamergenoot Sierk Rosema, dus moeilijke vragen zal ik aan hem doorsturen. Omdat dit een echt wiskundige stukje is, begin ik met een paar definities.

Een woord w is een rijtje letters (uit een of ander alfabet, dat kan bijvoorbeeld het gewone alfabet zijn of het binaire 'alfabet' {0,1}). We schrijven zo'n woord als w = w₁w₂...w_n, waarbij w_i de i-de letter van het woord is en n de lengte van het woord.

Een woord heeft periode p als w_i+p = w_i voor elke i die tussen 1 en n-p ligt. Het zevenletterige woord

abbabba

heeft bijvoorbeeld periode 3. Dit woord heeft ook periode 6, want er geldt w₁ = w₇ en voor de volgende letters valt er niets te controleren.

Fine-Wilf woorden
Stel nu dat je een woord zoekt dat bepaalde periodes wél en andere juist níet heeft. Hoe lang kan zo'n woord dan maximaal zijn? Fine en Wilf (daar zijn ze!) keken in 1965 naar woorden met twee periodes p₁ en p₂, die de grootste gemeenschappelijke deler van p₁ en p₂ NIET als periode hebben. We noteren deze grootste gemene deler voortaan als ggd(p₁,p₂). Fine en Wilf bewezen dat zo'n woord maximaal lengte p₁ + p₂ - ggd(p₁,p₂) - 1 kan hebben. Het is niet zo moeilijk om dit maximale woord te vinden.
Een eenvoudig voorbeeld
Neem als periodes 2 en 3. Volgens de stelling van Fine en Wilf kan een woord met deze periodes 2 en 3 en zonder periode 1 (dat is ggd(2,3)) maximaal 3 letters lang zijn. Periode 1 betekent dat een woord uit allemaal dezelfde letters bestaat, dat mag dus niet voor onze oplossing. We gaan het langst mogelijk woord stap voor stap opbouwen. We beginnen met de eerste letter, laten we die a noemen:

a.

We weten dat het woord periode 2 en 3 moet hebben, dus op plaats 3 en 4 komen nu ook a's te staan, de tweede plaats is nog vrij te kiezen, die noemen we even x:

axaa.

Op de tweede plek kunnen we ook een a zetten, maar dat betekent dat het hele woord uit a's zal bestaan (omdat daarna elke tweede plek vanaf zowel de 1ste als 2de letter een moet zijn). We mogen daar dus geen a zetten. Maar als we er een andere letter zetten, b bijvoorbeeld, dan krijgen we:

abaa.

Maar dit woord heeft niet periode 2, want op de 2de en 4de plaats staan verschillende letters. Kortom: we kunnen geen niet-constant woord van vier of meer letters maken dat periodes 2 en 3 heeft. We noemen het drieletterige woord

aba

ook wel het Fine-Wilf woord voor periodes 2 en 3.
Nog een voorbeeld

Iets minder flauw is het voorbeeld voor periodes 6 en 8. Volgens de stelling van Fine-Wilf kan dit woord maximaal 8 + 6 -2 -1 = 11 letters hebben. We beginnen weer met een letter a en krijgen dan:

a23456a8a.

Deze keer noteer ik de nog onbekende letters met cijfers in plaats van x-en, zodat jullie niet op je scherm hoeven te tellen of het klopt. Er staat nu op plaats 9 een a, dus moet er op plek 3 ook een a komen, omdat het woord periode 6 heeft:

a2a456a8a.

Maar als er op plek 3 een a staat, dan moet er op plek 11 ook een a staan, want het woord heeft periode 8:

a2a456a8a0a.

En jahoor, ook op plek 5 moet een a komen:

a2a4a6a8a0a.

Als we nu op plaats 2 een willekeurige letter zetten, dan komt volgens dezelfde stappen als hierboven die letter ook op plaatsen 8, 10, 4, 12 en 6. Dat betekent dat het woord constant wordt als we een a kiezen en periode 2 krijgt als we een b kiezen:

abababababab.

Maar 2 is de grootste gemene deler van 6 en 8 en we zochten juist een woord dat die niet als periode had! Dit betekent dat we een letter teveel gebruikt hebben. Als we het woord tot 11 letters beperken en op de tweede plaats een b zetten, dan krijgen we volgens bovenstaande stappen

ababaxababa.

De zesde plaats is nu nog vrij te kiezen, omdat we niet dezelfde letter meer hoeven te kiezen als op de 12de plaats. Daar zetten we vrolijk een c en we hebben het Fine-Wilf woord voor periodes 6 en 8 gevonden:

ababacababa.

Deze resultaten zijn trouwens ook gegeneraliseerd voor meer dan twee periodes. De liefhebber kan ook eens nadenken over een generalisatie in meer dimensies, dat is pas echt spannend.
(Ionica)