Het moeilijkste raadsel aller tijden
Het moeilijkste raadsel aller tijden (Engels: The hardest logic puzzle ever) is de naam gegeven door George Boolos aan een raadsel uit de krant La Repubblica. Het raadsel verscheen in 1992 en werd bedacht door Raymond Smullyan. Het gaat als volgt:
"Drie goden A, B en C heten (in onbepaalde volgorde) Waar, Onwaar en Willekeur. Waar spreekt altijd de waarheid, Onwaar liegt altijd en Willekeur antwoordt willekeurig de waarheid of de leugen. De opdracht bestaat eruit om door drie ja-neevragen te stellen exact de identiteiten van A, B en C te bepalen. Je mag kiezen aan welke god je elke vraag stelt en je mag meerdere vragen aan dezelfde god stellen. Een bijkomend probleem is dat de goden wel Nederlands verstaan, maar zelf niet kunnen spreken. Ze antwoorden met 'dah' en 'nah', maar vooraf is niet bekend welke 'ja' en welke 'nee' betekent."
Herkomst
bewerkenToen Boolos het raadsel publiceerde, refereerde hij naar Raymond Smullyan als uitvinder van het raadsel, hoewel John McCarthy werd gerefereerd als de persoon die het concept toevoegde van het taalprobleem. Het raadsel is een uitbreiding van het bekende 'ridder-schildknaap' probleem. Dit raadsel is eenvoudiger en ook bekender, vooral nadat het in de film Labyrinth voorkwam. Toen was het van de volgende vorm:
- "Er zijn twee deuren. Eén ervan leidt naar het kasteel en de andere naar een gewisse dood. Achter elke deur is een bewaker, de ene spreekt altijd de waarheid, de andere liegt altijd. Het raadsel is nu om door slechts één vraag te stellen aan een van de bewakers te weten te komen welke weg naar het kasteel leidt."
Oplossingen
bewerkenIn het artikel zelf verklapte Boolos ook de oplossing van het raadsel. Cruciaal in de oplossing is het identificeren van Willekeur. We beschouwen daarom de volgende vraag:
- Als ik u zou vragen of één plus één twee is, zou u dan 'dah' antwoorden?
- Als we deze vraag stellen aan Waar of Onwaar, dan krijgen we als antwoord altijd 'dah'. (dit is eenvoudig zelf na te gaan door alle mogelijkheden uit te proberen).
(Er vanuitgaande dat dah : Ja is. & Nah : Nee is) (bv.:Als ik u zou vragen of één plus één twee is, zou u dan 'ja' antwoorden?) (Als we deze vraag stellen aan Waar of Onwaar, dan krijgen we als antwoord altijd 'ja') (onwaar zal liegen ook tijdens dit antwoord) (terwijl als dah NEE is & Nah = ja , valt de rest van de oplossing uit elkaar) (want Waarheid zal zeggen "Dah=NEE" LET OP de vraag is : zou je NEE zeggen waarop het eerlijke antwoord is NEE.) (terwijl Onwaar op de vraag liegt en zegt "Dah=NEE" terwijl Onwaar er wel nee op zou antwoorden) (KORT zou je liegen? Altijd = NEE(of je nu de waarheid spreekt of niet)
Analoog zal de vraag
- Als ik u zou vragen of één plus één drie is, zou u dan 'dah' antwoorden?
- altijd 'nah' als antwoord opleveren als de god aan wie het gevraagd is Onwaar of Waar is.
Als we dit gebruiken, is een mogelijke oplossing:
- Vraag aan god B: "Als ik god B zou vragen 'Is A Willekeur?', zou hij dan 'dah' antwoorden?". Als B 'dah' antwoordt, dan is ofwel B zelf Willekeur, ofwel is A Willekeur. In beide gevallen is C dus niet Willekeur. Als B 'nah' antwoordt, dan is ofwel B Willekeur, ofwel C, en dus is A zeker niet Willekeur.
- Vraag nu aan de god die zeker niet Willekeur is het volgende: "Als ik u zou vragen: 'Bent u Waar?', zou u dan 'dah' antwoorden?" Als het antwoord 'dah' is, is deze god Waar. Als het antwoord 'nah' is, dan is deze god Onwaar.
- Vraag aan dezelfde god "Als ik u zou vragen 'Is B Willekeur', zou u dan 'dah' antwoorden?" Als het antwoord 'dah' is, is B willekeur. Anders is de god waartegen je nog niet hebt gesproken Willekeur. Nu weet je dus de identiteit van Willekeur en van Onwaar of Waar, maar dus ook de identiteit van de laatste (door eliminatie!).
Lange tijd dacht men dat dit de enige oplossing was, maar later vond men een alternatieve methode. Deze veronderstelt wel een uitgebreide definitie van het raadsel, waarbij het hoofd van een god ontploft wanneer elk mogelijk antwoord op een vraag inconsistent is. In dat geval kan men de identiteit zelfs achterhalen met twee vragen.