Winnaar breinbreker april-mei 2021

De winnaar van de breinbreker van februari-maat is Simon Van den Eynde. Hoera! We belonen dit met een abonnement op het wiskundetijdschrift Pythagoras. We ontvingen ook een correcte inzending van Steven Van Overberghe. Bedankt!

 

oplossing:  

Kies een n vast.

 

    Elke twee PRIME-woorden van lengte 5n kunnen door swaps in elkaar omgezet worden (gebruik bijvoorbeeld de analogie met bucket-sort).

    Als d(X,Y) het minimale aantal swaps voorstelt om X in Y om te zetten, dan vormt d een metriek op de verzameling van alle PRIME-woorden met lengte 5n.

    Het woord A := P^n · R^n · I^n · M^n · E^n ligt op afstand 10n^2 van B := E^n · M^n · I^n · R^n · P^n.

    Uit de driehoeksongelijkheid volgt nu dat elk n-PRIME-woord X op afstand minstens 5n^2 ligt van ofwel A of B.

 

Voor bewering 3: 10n^2 is voldoende, want zet eerst alle P's vooraan (4n^2 stappen), dan alle R'en na de P's (3n^2 stappen) enzovoort. In totaal geeft dat (4+3+2+1)n^2 stappen.

 

Anderzijds, 10n^2 is ook nodig. Zeg dat twee verschillende letters in een PRIME-woord pɹǝǝʇɹǝʌuïǝƃ zijn als ze niet staan zoals in de volgorde van PRIME zelf. (Deze definitie houdt enkel steek voor dit specifieke probleem, maar dat geeft niet.) Dan is woord A het enige woord met 0 inversies. Ook is het duidelijk dat elke swap ten hoogste één inversie kan wegnemen.  Aangezien B 10n^2 inversies heeft, volgt dus de bewering.