Naar de content

De kortste weg naar het miljoen

De wiskunde achter ‘alle 5 uit 10 goed’

Pixabay.com, jojooff via CC0 Creative Commons

In de spelshow De Weg Naar Het Miljoen moest een kandidaat telkens uit tien items de vijf goede kiezen. Na elke poging kreeg de kandidaat alleen te horen hoeveel er goed zijn. Dat kleine beetje informatie kan je een heel eind op weg helpen, maar dat hadden de kandidaten blijkbaar niet door.

In menig opzicht is De Weg Naar Het Miljoen een commerciële spelshow volgens beproefd recept: grote zaal vol publiek, flitsend decor, gelikte presentatie door een BN’er en vette geldprijzen. Maar in dit geval is de manier waarop een kandidaat de prijzen in de wacht kan slepen ook wiskundig interessant.

De kandidaat krijgt telkens een lijst van tien items te zien, waarvan er vijf goed en vijf fout zijn. Bijvoorbeeld: tien steden, waarvan vijf een Europese hoofdstad zijn, en vijf niet. De kandidaat heeft vijf pogingen. Bij elke poging wijst hij of zij vijf items aan, en krijgt dan te horen hoeveel er goed zijn – maar niet welke goed zijn.
Als de kandidaat binnen vijf pogingen vijf goed scoort, wint deze een fors geldbedrag en mag verder.

Blind gokken

Laten we eerst maar eens kijken of blind gokken enige kans maakt: er zijn
(10×9×8×7×6/(1×2×3×4×5) ) = 252 echt verschillende mogelijkheden om vijf items uit een lijstje van tien te kiezen. De kans om op de eerste poging meteen alles goed te hebben, is daarom 1/252. De kans om binnen vijf pogingen alle vijf goed te gokken – waarbij je er natuurlijk voor zorgt dat je niet twee keer dezelfde gok doet – is 5/252, ofwel bijna twee procent.

Maar met gokken maak je geen gebruik van de informatie die je na elke poging krijgt. In de shows leken de kandidaten, voor zover ze al een strategie hadden, een voor de hand liggend principe aan te houden: als je na een poging te horen krijgt dat je er bijvoorbeeld vier goed hebt, verander je bij de volgende poging alleen het item waarvan je het minst zeker bent.

Laten we eens aannemen dat je vier items echt zeker weet. Dus al bij de eerste poging scoor je vier goed, terwijl je dan ook weet welk van de vijf items fout is. Als je dan de resterende items een voor een gaat proberen kan het nog fout gaan, want dat zijn er vijf, terwijl je maar vier pogingen over hebt.

Als je er van tevoren al vier zeker weet, is er een veel effectievere methode, die in maximaal vier pogingen gegarandeerd vijf goed scoort, en dus een geldprijs oplevert. (zie onderstaand kader)

Methode als je vier items zeker weet

Hoofdletters zijn de items die zeker goed zijn, kleine letters zijn items waarvan je het nog niet zeker weet, cursieve letters zijn foute items.
In het begin zijn er tien items, waarvan je er vier zeker weet, en de rest is onzeker:

A B C D e f g h i j

Bij je eerste poging moet je juist niet alle vier de zekere items aanklikken, maar slechts twee:

poging 1] A B e f g (niet aangeklikt: h i j C D)

Er zijn maar twee mogelijke uitkomsten: twee goed of drie goed (vier of vijf kan niet, want je hebt twee goede items bewust niet aangeklikt)

1a] twee goed: e,f en g zijn fout

1b] drie goed: h,i en j zijn fout

Op je tweede poging klik je wel je vier zekere items aan, en een van de drie die nog onzeker zijn (voor het vervolg nemen we aan dat h,i en j nog onzeker zijn):

poging 2] A B C D h (niet aangeklikt: i j e f g )

opnieuw zijn er maar twee uitkomsten mogelijk:

2a] vijf goed: klaar op 2e poging

2b] vier goed: h is fout

poging 3] A B C D i (niet aangeklikt: j e f g h)

weer twee mogelijke uitkomsten:

3a] vijf goed, klaar op 3e poging

3b] vier goed: i is fout.

De enige overgebleven mogelijkheid is nu, dat A B C D en J goed zijn, dus die kun je bij de vierde poging invullen.

Munten wegen

Het ‘vijf uit tien’-probleem, en zijn generalisatie (hoeveel pogingen zijn minimaal nodig om ‘n uit m’ op te lossen) lijkt typisch zo’n probleem dat door wiskundigen al tot op het bot is geanalyseerd, maar dat valt enigszins tegen. Dion Gijswijt, wiskundige aan de TU Delft met als specialisatie combinatorische optimalisatie, laat per e-mail weten: “Het lijkt nog het meest op het zogeheten adaptive d-coin weighing problem.”

De opgave is hier om van n munten, waarvan gegeven is dat er d vals zijn (dat wil zeggen: een afwijkend gewicht hebben), exact te bepalen welke vals zijn. Om hier achter te komen heb je een weegschaal met veer (dus geen balansweegschaal) waar je telkens een zelf gekozen aantal munten op mag leggen.

Het gewicht dat de weegschaal aangeeft, komt overeen met de feedback in de spelshow hoeveel aangeklikte items goed zijn (want je weet hoeveel een echte, en hoeveel een valse munt weegt). In 2009 publiceerde de Israëliër Nader Bshouty een efficiënt algoritme dat dit probleem oplost. Hoeveel pogingen Bshouty’s algoritme nodig heeft voor het ’5 uit 10’-probleem is nog niet zo makkelijk te zeggen, omdat hij alleen een benaderingsformule geeft voor grote aantallen munten. Die formule suggereert dat zijn algoritme niet meer dan zes of zeven pogingen nodig heeft.

Maar er zit een addertje onder het gras: in het weegprobleem mag je zelf bepalen hoeveel munten je op de weegschaal legt, terwijl je in de spelshow altijd vijf items moet aanklikken. Dit is uiteraard een nadeel. Anderzijds is het weer een voordeel, dat je weet dat er precies vijf munten vals zijn. Welke gevolgen dit heeft voor het benodigde aantal pogingen zou een apart onderzoek vergen.

Twee goed, twee fout

Gijswijt stuurde ook een zelf bedachte methode om in vijf pogingen vijf goed te scoren als je slechts twee items zeker weet, maar ook van twee items zeker weet dat ze fout zijn. Deze methode is qua complexiteit vergelijkbaar met die in het kader, dus ook dat is nog wel uit het hoofd te leren.

Als je van drie items zeker weet dat ze goed zijn, is er in ieder geval een methode die in verreweg de meeste gevallen in hoogstens vijf pogingen succes oplevert. Alleen als je maximaal pech hebt bij de eerste vier pogingen, moet je op de vijfde poging nog tussen twee alternatieven gokken.

Deze methode is gecompliceerder dan voor ‘vier goed’ en ‘twee goed-twee fout’, dus het is nauwelijks realistisch dat iemand tijdens die spelshow, met alle stress die daarbij komt kijken, dat hele stappenplan goed kan uitvoeren.

Bij Master Mind moet de tegenspeler erachter komen, welke gekleurde pionnen achter een schermpje staan (de bovenste regel). Na elke poging bestaat de feedback uit het aantal pionnen met de goede kleur (wit), en het aantal dat bovendien op de goede plaats staat (zwart).

Jeff Stuckman, Guo-Qiang Zhang

Nog een verwant probleem, dat ook Gijswijt noemt, is het welbekende spelletje Master Mind. Daarbij worden vier gekleurde pionnen neergezet achter een schermpje. De tegenspeler zet de eerste keer op de gok vier pionnen neer en krijgt feedback over hoeveel pionnen de juiste kleur hebben, en hoeveel er bovendien op de juiste plek staan.

Maximaal vijf pogingen nodig?

Voor Master Mind bestaat een algoritme, waarmee een computer altijd in maximaal vijf pogingen kan ontdekken welke pionnen er achter het schermpje staan. Dit algoritme is in wiskundige zin weliswaar niet efficiënt, maar omdat het totaal aantal mogelijkheden beperkt is (64 = 1296), is het toch heel snel. Als je Master Mind zou uitbreiden naar 50 of 100 gekleurde pionnen, zou het algoritme veel meer pogingen nodig hebben, en er een eeuwigheid over doen om telkens de beste poging te vinden.

Het algoritme voor het adaptive d-coin weighing problem is wel efficiënt, maar het is een open vraag of er ook zo’n efficiënt algoritme bestaat als je telkens vijf (of een ander vast aantal) munten moet wegen.

Concluderend: voor een paar problemen die sterk lijken op ‘alle 5 uit 10 goed’ bestaan algoritmes die in vijf pogingen altijd een oplossing vinden. Maar die algoritmes zijn zo omslachtig, dat alleen een computer ermee overweg kan. Of het in principe mogelijk is, om ‘alle 5 uit 10’ in vijf pogingen op te lossen als je geen enkel item zeker weet, is nog niet goed onderzocht, maar dit is zeer onwaarschijnlijk.

Echter, als je een paar items zeker weet, of zeker weet dat ze fout zijn, kun je als deelnemer met handige zoekmethodes je kansen flink vergroten. Als je van vier items zeker weet of ze goed of fout zijn, weet je zelfs zeker dat je binnen vijf pogingen prijs hebt.

Bron
ReactiesReageer