Op Boxing Day1 belooft de manager van een 10-koppige band om een dikke eindejaarspremie uit te keren als de muzikanten slagen in de volgende opdracht.

De manager heeft de 10 verschillende instrumenten van de muzikanten in 10 afgesloten dozen gestopt, die hij in een geluidsdichte kamer heeft geplaatst. Hij heeft de dozen ook gelabeld met de 10 verschillende instrumenten, maar de inhouden van de dozen komen niet noodzakelijk overeen met hun labels. De muzikanten moeten om de beurt de kamer binnengaan om hun eigen instrument te zoeken. Daarbij mogen ze maximaal 5 dozen openen. Als ze hun eigen instrument gevonden hebben dan moeten ze de geopende dozen terug afsluiten en de kamer langs een andere deur verlaten. Ze mogen op geen enkele manier met elkaar communiceren. De muzikanten slagen enkel in de opdracht als ze allemaal hun eigen instrument gevonden hebben.

dozen
Tien dozen bevatten tien verschillende instrumenten. De dozen zijn ook gelabeld met de verschillende instrumenten, maar de labels corresponderen niet noodzakelijk met de inhoud van de dozen.

Als elke muzikant willekeurig 5 dozen opent dan heeft hij 50% kans om zijn eigen instrument te vinden. De kans dat alle muzikanten op deze manier hun eigen instrument vinden is \[\left(\frac{1}{2}\right)^{10} = \frac{1}{1024}\] Dat is dus minder dan 0.1%.

De band heeft echter een strategie bedacht waarmee ze 35% kans hebben om de opdracht te doen slagen. Elke muzikant gaat de kamer binnen en opent de doos die gelabeld is met zijn instrument. Als de doos zijn eigen instrument bevat, dan is hij geslaagd in zijn deel van de opdracht. Anders kijkt hij welk instrument er in de doos zit en opent daarna de doos die gelabeld is met dat instrument.

dozen
De gitarist gaat de kamer binnen en opent de doos die gelabeld is met de gitaar. In die doos vindt hij een conga waardoor hij vervolgens de doos die gelabeld is met de conga zal openen.

Hij blijft dit herhalen totdat hij ofwel 5 dozen geopend heeft zonder zijn eigen instrument te vinden (waardoor de opdracht mislukt) of totdat hij zijn eigen instrument gevonden heeft (waardoor hij slaagt in zijn deel van de opdracht).

dozen
De gitarist opent de doos die gelabeld is met de trompet en daarin vindt hij zijn gitaar. Daarmee is hij geslaagd in zijn deel van de opdracht.

Deze strategie werkt omdat ze elke muzikant laat zoeken in een gelinkte reeks dozen die uiteindelijk zal uitkomen bij de doos die het instrument van de muzikant bevat. Deze doos linkt terug naar de doos waar de muzikant zijn zoektocht gestart is, waardoor de gelinkte reeks dozen een lus vormt. Een dergelijke lus wordt in de grafentheorie2 een cykel genoemd.

Deze strategie werkt veel beter dan het willekeurig uitkiezen van dozen. Voor een even aantal dozen $$m = 2n$$ kan aangetoond worden dat de kans dat de langste cykel kleiner of gelijk is aan $$n$$ kan berekend worden als \[ 1 - \left( \frac{1}{n+1} + \frac{1}{n+2} + \frac{1}{n+3} + \cdots + \frac{1}{2n} \right)\] Voor $$m = 10$$ wordt deze kans ongeveer 35%. Voor grote $$m$$ nadert deze kans naar 30%. Het is dus zeker niet gegarandeerd dat de muzikanten in hun opdracht zullen slagen, maar met een klein beetje geluk kunnen ze toch hun eindejaarspremie opstrijken.

Opgave

Er zijn $$m$$ verschillende items die elk worden beschreven door een unieke string die geen komma's bevat. Deze items werden in $$m$$ dozen gestopt. De dozen werden ook gelabeld met de beschrijvingen van de $$m$$ items, maar de labels van de dozen komt niet noodzakelijk overeen met hun inhouden.

De labels en de inhouden van de dozen worden beschreven in een tekstbestand. Elke regel van het tekstbestand beschrijft een doos aan de hand van twee beschrijvingen van items, die van elkaar gescheiden worden door een komma (,). De eerste beschrijving correspondeert met het label van de doos en de tweede met de inhoud van de doos. Zo'n tekstbestand kan er dan bijvoorbeeld als volgt uitzien:

guitar,conga
saxophone,banjo
conga,maracas
drum set,saxophone
trumpet,guitar
bass guitar,trombone
synthesizer,trumpet
banjo,drum set
trombone,bass guitar
maracas,synthesizer

Onderstaande figuur toont een grafische voorstelling van de labels en de inhouden van de tien dozen, zoals beschreven in dit tekstbestand.

dozen
Grafische voorstelling van de labels en de inhouden van de tien dozen, zoals vastgelegd in het tekstbestand.

Gevraagd wordt:

Voorbeeld

Bij onderstaande voorbeeldsessie gaan we ervan uit dat de tekstbestanden dozen01.txt3, dozen02.txt4, dozen03.txt5 en dozen04.txt6 zich in de huidige directory bevinden.

>>> dozen = lees_dozen('dozen01.txt7')
>>> dozen
{'guitar': 'conga', 'saxophone': 'banjo', 'conga': 'maracas', 'drum set': 'saxophone', 'trumpet': 'guitar', 'bass guitar': 'trombone', 'synthesizer': 'trumpet', 'banjo': 'drum set', 'trombone': 'bass guitar', 'maracas': 'synthesizer'}

>>> cykel('guitar', dozen)
('guitar', 'conga', 'maracas', 'synthesizer', 'trumpet')
>>> cykel('saxophone', dozen)
('saxophone', 'banjo', 'drum set')
>>> cykel('bass guitar', dozen)
('bass guitar', 'trombone')
>>> cykel('clarinet', dozen)
Traceback (most recent call last):
AssertionError: ongeldig item

>>> langste_cykel(dozen)
5

>>> lees_dozen('dozen02.txt8')  # 2x zelfde label
Traceback (most recent call last):
AssertionError: ongeldige dozen
>>> lees_dozen('dozen03.txt9')  # 2x zelfde inhoud
Traceback (most recent call last):
AssertionError: ongeldige dozen
>>> lees_dozen('dozen04.txt10')  # labels verschillen van inhouden
Traceback (most recent call last):
AssertionError: ongeldige dozen

Epiloog

Bronnen