Peter Winkler uit Dartmouth College bedacht deze merkwaardige puzzel. Je wilt lid worden van het Verbond der Werpers van Muntstukken. De jaarlijkse bijdrage die je daarvoor moet betalen, wordt op passende wijze door het toeval bepaald. Je noemt een reeks van vijf kop-of-munt uitkomsten. Daarna wordt herhaaldelijk met een muntstuk geworpen totdat jouw reeks van vijf opeenvolgende uitkomsten voorkomt. Je bijdrage is het totaal aantal worpen dat daarvoor nodig was, in euro.

Laten we kop voorstellen door de letter H (naar het Engels heads) en munt door de letter T (naar het Engelse tails). Als je bijvoorbeeld de reeks HHHHH kiest en er zijn 36 worpen nodig vooraleer er vijf keer na elkaar kop gegooid wordt, dan bedraagt je jaarlijkse bijdrage €36. Nu je dit weet, welke reeks zou je dan kiezen?

Op het eerste gezicht lijkt het dat je keuze er niet echt toe doet — elke vaste reeks heeft toch $$\left(\frac{1}{2}\right)^5 = \frac{1}{32}$$ kans? Maar "niet zo snel", schrijft Winkler, "want overlappende reeksen zorgt voor extra complexiteit". Het is waar dat in een oneindige reeks van willekeurige worpen, de gemiddelde afstand tussen het ene voorkomen en het volgende voorkomen van een vaste reeks uitkomsten $$\frac{1}{32}$$ is. Maar als je bijvoorbeeld HHHHH kiest, dan vergroot één voorkomen van deze reeks uitkomsten de kans dat je direct daarna nog een voorkomen van de reeks tegenkomt — als je bij de volgende worp munt gooit dan begin je daarna helemaal opnieuw van voor af aan, maar als het kop is dan doet de reeks zich al meteen opnieuw voor. Winkler schrijft:

Als $$X$$ het gemiddeld aantal worpen is dat nodig is om bij het begin de reeks HHHHH te werpen, dan is het gemiddelde van $$1 + X$$ en $$1$$ gelijk aan $$32$$. Als je dit oplost naar $$X$$ dan krijg je de verrassende hoge waarde van $$X = 62$$ worpen.

Om je verwachte jaarlijkse bijdrage te laten zakken naar €32, moet je een reeks kiezen waarvoor dit "voorsprong"-effect zich niet voordoet. Er bestaan 10 zo'n reeksen, en daar is HHHTT er één van.

Opgave

Bij een experiment gebruiken we een muntstuk om één of meer reeksen van kop-of-munt uitkomsten te bepalen. Een reeks bestaat uit één of meer uitkomsten, waarbij we de uitkomst "kop" voorstellen door de hoofdletter H en de uitkomst "munt" door de hoofdletter T. Bij de beschrijving van het experiment schrijven we de letters voor de uitkomsten van opeenvolgende worpen in een reeks gewoon achter elkaar, en worden opeenvolgende reeksen telkens van elkaar gescheiden door een spatie.

Elke regel van het tekstbestand dues.txt¹ bestaat uit een patroon $$p \in \mathcal{P}$$, gevolgd door een verticale streep (|) en een woord $$w \in \mathcal{W}$$. De verzameling $$\mathcal{P}$$ bestaat uit alle mogelijke beschrijvingen van experimenten. De verzameling $$\mathcal{W}$$ bevat alle woorden die enkel uit kleine letters bestaan. Gevraagd wordt:

1. Bepaal zo kort mogelijke reguliere expressies voor de volgende deelverzamelingen van $$\mathcal{P}$$:

   • $$\mathcal{P}_1 = \{\,p \in \mathcal{P}\,|\,p\ $$heeft een reeks die uit minstens zes worpen bestaat en waarvan alle worpen dezelfde uitkomst hebben$$\,\}$$

     voorbeeld:	TTTHHT THTTH HTHTHTHT THTTTH HTHHTHTH HHHHHH HHHH HT HTHT TH TH|logins $$\in \mathcal{P}_1$$
     	HHTTTTTT T HHHHH HHHT HTTHHT HT TTTH T H THTHTH TT HTT TT HT TTHT|rubbish $$\not \in \mathcal{P}_1$$

   • $$\mathcal{P}_2 = \{\,p \in \mathcal{P}\,|\,$$in experiment $$p$$ werd in totaal exact 60 keer met een muntstuk geworpen$$\,\}$$

     voorbeeld:	TTHTTH TTHHHTH THHTHHHT TT HHTHHTH HTTTTTH HHTHH TT HTHTHTTT HHHTTHTH|enter $$\in \mathcal{P}_2$$
     	THHTTH TTHHH TH HTH HTH TTHTHHH HTH TH HHT T TTHT T T HTHHHH HTTHTH|mercurial $$\not \in \mathcal{P}_2$$

   • $$\mathcal{P}_3 = \{\,p \in \mathcal{P}\,|\,$$alle reeksen van $$p$$ alterneren tussen kop en munt$$\ ^{(*)}\,\}$$

     (*) het doet er niet toe wat de eerste worp van een reeks is, maar opeenvolgende worpen moeten afwisselend kop of munt zijn
     

     voorbeeld:	THTHTHT HTHTHT HTHTHTH H THT HTHTHTHT THTHTHTH HTH THTH THTHTH|flubs $$\in \mathcal{P}_3$$
     	HTHTH TTTTTHH HTTHTH TTHHTT TTHHHH HTTHHHHH HTT TT THTHTH HTHTHHH|brakemen $$\not \in \mathcal{P}_3$$

   • $$\mathcal{P}_4 = \{\,p \in \mathcal{P}\,|\,$$experiment $$p$$ heeft twee dezelfde reeksen van minstens vijf worpen$$\,\}$$

     voorbeeld:	TTTTHTH HTHHHHHH HTHHT HHTH THHTT H THTHT TTT THTHHHTT HTHHT TTTTHTTH|boomerang $$\in \mathcal{P}_4$$
     	HTHHHH HTT THTH THH HHHT THH HH HTHTHTTT HTHT HHTHTTH HTH HHTHHTH HTH|pupil $$\not \in \mathcal{P}_4$$

   Geef telkens een Unix commando waarin de reguliere expressie gebruikt wordt door een commando uit de grep familie om enkel de regels van het tekstbestand naar stdout te schrijven waarvan het patroon $$p$$ behoort tot $$\mathcal{P}_i\ (i = 1, 2, 3, 4)$$.

2. Bepaal als volgt de woorden $$w_1\ w_2\ w_3\ w_4$$ van een geheime boodschap:

   • het woord $$w_1$$ staat op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_1 \cap \mathcal{P}_2$$

   • het woord $$w_2$$ staat op de unieke regel waarvan $$p$$ behoort tot $$ \mathcal{P}_2 \cap \mathcal{P}_3$$

   • het woord $$w_3$$ staat op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_3  \cap \mathcal{P}_4$$

   • het woord $$w_4$$ staat op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_4 \cap \mathcal{P}_1$$

   Geef telkens een Unix commando waarin de reguliere expressies voor de verzamelingen $$\mathcal{P}_i\ (i = 1, 2, 3, 4)$$ gebruikt worden door commando's uit de grep familie om het woord $$w_j\ (j = 1, 2, 3, 4)$$ op te zoeken in het tekstbestand en uit te schrijven naar stdout. Hierbij is het niet toegelaten om het woord $$w_j$$ letterlijk uit te schrijven (bv. echo $$w_j$$).

Bronnen

• Winkler P (2013). Puzzled: Coin flipping. Communications of the ACM 56(11), 120. ¹⁶