De winnaar van de breinbreker van april-mei is Simon Van den Eynde. We belonen dit met een abonnement op het wiskundetijdschrift Pythagoras. We ontvingen ook een correcte inzending van Steven Van Overberghe. Bedankt!
Dit antwoord werd ons ingezonden door Simon Van den Eynde:
We zullen PRIME-woord noteren met behulp van machten. Bijvoorbeeld (PRIME)^n staat voor het PRIME-woord bestaande uit n concatenaties van het woord PRIME. We definiëren alvast twee PRIME-woorden:
- α := P^n R^n I^n M^n E^n
- ω := E^n M^n I^n R^n P^n
Lemma 1. Er zijn minimaal 10n^2 swaps nodig om α om te zetten naar ω.
Bewijs. In α staan alle P ’s voor de andere letters, terwijl deze in ω erna staan. Aangezien swaps de enige manier zijn om de volgorde te veranderen, moet elke P ten minste eenmaal met elke andere letter geswapt worden. Analoog vinden we dat elke A ∈ {P, R, I, M, E} met elke letter in {B_A | B ∈ {P, R, I, M, E} ∧ B ≠ A} geswapt moet worden om α om te zetten naar ω. Aangezien er van elke letter A^n exemplaren zijn en er 4n letters B_A zijn, vergt het minstens 4n^2 swaps om alle A’s te swappen met alle B A ’s. Natuurlijk swapt een swap telkens twee letters van plaats, dus om alle 5n letters van α om te zetten naar ω zijn er minstens (4n·n·5)/2 = 10n^2 swaps nodig.
Stelling 1. Voor elk PRIME-woord X bestaat er een PRIME-woord Y zodat er ten minste 5n^2 swaps nodig zijn om X in Y om te zetten.
Bewijs. Stel uit het ongerijmde dat er een PRIME-woord X bestaat zodat er voor elk PRIME-woord Y een swapsequentie bestaat met strikt minder dan 5n^2 swaps die X omzet in Y . Aangezien swappen een symmetrische relatie is, bestaat er dan ook een swapsequentie van elk P RIM E-woord Y naar X met strikt minder dan 5n^2 swaps. In het bijzonder vinden we een swapsequentie sws_1 van α naar X en een swapsequentie sws_2 van X naar ω zodat zowel sws_1 als sws_2 strikt minder dan 5n 2 swaps bevatten. Concateneren we sws_1 met sws_2 dan vinden we een sequentie die α omzet naar ω in strikt minder dan 10n^2 swaps, een contradictie met Lemma 1.