De kortste weg naar het miljoen

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)

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.

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 (6⁴ = 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.