Submitted by Jens H. on
De beste inzending voor de breinbreker februari-maart was van Jasmine Maes. Als prijs krijgt zij een jaarabonnement op Pythagoras en Wiskunde & Onderwijs opgestuurd. Proficiat en veel plezier met de abonnementen!
We kregen ook nog juiste inzendingen van Ben De Bondt, Yannick Neyt en Pieter Stroobant. Bedankt voor jullie inzending!
Oplossing
We kunnen de positie van de bal voorstellen door een getal in $[0,1[$, waarbij $0$ de linkerrand van het veld is en $1$ de rechtrrand. ($\frac{1}{2}$ is dan de middellijn.)
Stel dat de bal zich een bepaald moment op positie $x \in [0,\frac{1}{2}[$ (dus in de linkerhelft) bevindt. Dan bevindt hij zich één worp later op positie $2x$. als de bal zich in de rechterhelft bevindt, dan zit hij na de volgende worp op $2x-1$.
Gegeven een beginpositie $x$, kunnen we dus de bijbehorende rij opstellen door telkens het volgende te herhalen:
- Als $x \in [0,\frac{1}{2}[$, schrijf dan L en vervang $x$ door $2x$.
- Als $x \in [\frac{1}{2},1[$, schrijf dan R en vervang $x$ door $2x-1$.
Dit procedé is exact hetzelfde als het volgend algoritme om van een gegeven getal $x \in [0,1[$ de binaire voorstelling te bepalen: schrijf ''$0.$'' en herhaal telkens het volgende:
- Als $x \in [0,\frac{1}{2}[$, schrijf dan 0 en vervang $x$ door $2x$.
- Als $x \in [\frac{1}{2},1[$, schrijf dan 1 en vervang $x$ door $2x-1$.
Dit geeft ons dus volgende methode om een voor een gegeven rij van R'en en L'en een goede beginpositie te vinden: vervang elke L door een $0$ en elke R door een $1$, schrijf er ''$0.$'' voor. Je bekomt een binair getal $x$ (bijvoorbeeld vertrekkend van de rij ''RLRLRL...'' krijgen we het binair getal $0.101010...$). Laten we de bal nu vertekken vanaf $x$, dan krijgen we de gezochte rij.
Dit procedé kan enkel mislopen bij rijen die eindigen op oneindig veel L'en of R'en: dan krijgen we namelijk getallen waarvan de binaire schrijfwijze niet uniek is. Om het met een voorbeeld uit te leggen: de rijen ''LRRRR...'' en ''RLLLL...'' leveren allebei $x=0.1=0.01111...$ als beginpositie. Als we bovenstaand algoritme bekijken, zien we echter dat we met deze $x$ de rij ''RLLLL...'' bekomen, en niet de rij ''LRRRR...''. Aldus kunnen we inzien dat de rijen die eindigen op oneindig veel L'en wel kunnen, maar die op oneindig veel R'en niet.