De bank van Bath
Opgave - IMO 2019 dag 2 vraag 2
De Bank van Bath geeft munten uit met een $H$ op de ene kant en een $T$ op de andere kant.
Harry heeft $n$ van deze munten van links naar rechts op een rij gelegd.
Hij voert herhaaldelijk de volgende handeling uit: als er precies $k \ge 1$ munten zijn die met de $H$ naar boven liggen, dan draait hij de
$k^{\mathrm{de}}$ munt van links om; als alle munten met de $T$ naar boven liggen, dan stopt hij.
Bijvoorbeeld, als $n=3$ en hij start met de beginrij $THT$, dan krijgt hij achtereenvolgens $THT \to HHT \to HTT \to TTT$ en stopt hij na drie handelingen.
Bewijs dat Harry voor elke beginrij na een eindig aantal handelingen stopt.
Voor elke beginrij $C$ definiëren we $L(C)$ als het aantal handelingen totdat Harry stopt. Bijvoorbeeld: $L(THT)=3$ en $L(TTT)=0$.
Bepaal de gemiddelde waarde van $L(C)$ over alle $2^n$ mogelijke beginrijen $C$.
- login om te reageren
Oplossing
Noot: $K$ wordt hier soms ipv $T$ gebruikt.
Lemma: Noteer $C(A)$ voor een rij $A$ van lengte $n$ als de rij die je verkrijgt door elke munt van $A$ om te draaien en voor alle $1\le i<\frac{n}{2}$ de $i$-de en $n-i$-de munt te verwisselen (de $n$-de munt verander je dus niet van plaats). We tonen dat als je van een rij $A$ verschillend van een rij bestaande uit enkel $H$'s of enkel $T$'s overgaat naar een rij $B$, je dan ook van $C(A)$ naar $C(B)$ overgaat. Als $A$ precies $k$ keer een $H$ bevat, dan verkrijgen we $B$ door de $k$-de munt van $A$ om te draaien. $C(B)$ verkrijgen we dan door alle munten van $A$ behalve de $k$-de om te draaien en dan voor alle $1\le i<\frac{n}{2}$ de $i$-de en $n-i$-de munt te verwisselen, of nog eerst voor alle $1\le i<\frac{n}{2}$ de $i$-de en $n-i$-de munt te verwisselen en dan alle munten behalve de $n-k$-de om te draaien. Dit laatste komt overeen met $C(A)$ nemen en dan de $n-k$-de munt omdraaien. Omdat $A$ precies $k$ keer $H$ bevat, bevat $C(A)$ precies $n-k$ keer $H$, dus gaan we wegens voorgaande van $C(A)$ over naar $C(B)$.
Zij $G(n)$ de gerichte graaf waarvan de knopen alle rijen van lengte $n$ zijn en er een zijde van knoop $A$ naar knoop $B$ bestaat als en slechts je met de handeling beschreven in de opgave van rij $A$ naar rij $B$ overgaat. Noem $A_K$ de knoop die $n$ keer $K$ bevat. We bewijzen inductief dat er voor elke knoop $A$ van $G(n)$ precies één pad naar $A_K$ bestaat (eventueel van lengte 0) en dat de gemiddelde lengte van dit pad $\frac{n(n+1)}{4}$ is. Voor de inductiebasis nemen we $n=1$ en dan ziet $G(1)$ eruit als $H\rightarrow K$. Er bestaat een pad van lengte 0 en lengte 1 van respectievelijk $K$ en $H$ naar $A_K$, dus is de gemiddelde lengte van de paden $\frac{0+1}{2}=\frac{n(n+1)}{4}$.
Stel bewezen voor $n=k$. Noem $G_K(k+1)$ en $G_H(k+1)$ de deelgrafen van $G(k+1)$ die bestaan uit respectievelijk alle knopen die eindigen op een $K$ en alle knopen die eindigen op een $H$ en $A_H$ de knoop die $k+1$ keer $H$ bevat. Merk om te beginnen op dat als we aan elke knoop van $G(k)$ een $K$ achteraan toevoegen, de structuur van de graaf niet wijzigt, aangezien de handeling er niet door wordt beïnvloed. Dus heeft $G_K(k+1)$ dezelfde structuur als $G(k)$ en bestaat er wegens de inductiehypothese voor elke knoop van $G_K(k+1)$ een pad naar $A_K$. (1)
De afbeelding $C$ beschreven in het lemma hierboven is een bijectie tussen de rijen van lengte $k+1$ die eindigen op $K$ en de rijen van lengte $k+1$ die eindigen op $H$, aangezien elke rij die eindigt op $K$ op een eenduidige manier op een eenduidige manier wordt afgebeeld op een rij die eindigt op $H$ en omgekeerd. Door het lemma volgt ook dat elke zijde van $G_K(k+1)$ met met beginpunt $A$ en eindpunt $B$ afgebeeld wordt op de zijde van $G_H(k+1)$ met beginpunt $C(A)$ en eindpunt $C(B)$ en omgekeerd, dus heeft $G_K(k+1)$ dezelfde structuur als $G_H(k+1)$ en bestaat er vanuit elke knoop van $G_H(k+1)$ een pad naar $C(A_K)=A_H$. (2)
Doordat je van $A_H$ overgaat naar de rij bestaande uit $k$ keer $H$ gevolgd door een $K$, bestaat er een zijde van $A_H$ naar een knoop van $G_K(k+1)$. Samen met (1) en (2) volgt er dat er vanuit elke knoop van $G(k+1)$ een pad naar $A_K$ bestaat. Omdat er vanuit elke knoop hoogstens 1 zijde vertrekt, is dit pad uniek, dus is het eerste deel van de inductiestap bewezen.
Wegens (1) en (2) hebben $G(k),G_H(k+1)$ en $G_K(k+1)$ dezelfde structuur, dus is wegens de inductiehypothese de gemiddelde lengte van het pad van een knoop van $G_H(k+1)$ en $G_K(k+1)$ naar $A_H$ en $A_K$ respectievelijk gelijk aan $\frac{k(k+1)}{4}$. Voor de knopen van $G_H(k+1)$ (dus de helft van het totale aantal knopen) komt hier de lengte van het pad van $A_H$ naar $A_K$ bij. De lengte van dit pad is gelijk aan $k+1$ aangezien Harry telkens de laatste nog aanwezige $H$ in een $T$ verandert. Dus is de gemiddelde lengte van het pad van een knoop van $G(k+1)$ naar $A_K$ gelijk aan $\frac{k(k+1)}{4}+\frac{k+1}{2}=\frac{(k+1)(k+1+1)}{4}$.
Wegens inductie volgt er dat voor elke knoop van $G(n)$ er precies één pad naar $A_K$ bestaat en dat de gemiddelde lengte van dit pad $\frac{n(n+1)}{4}$ is. Dus stopt Harry voor elke beginrij na een eindig aantal handelingen en is het gemiddelde aantal handelingen voor een beginrij van lengte $n$ gelijk aan $\frac{n(n+1)}{4}$.