Het moeilijkste raadsel aller tijden

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Waar, Vals, en Willekeur

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 X, Y, en Z 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 X, Y en Z 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 'neen' betekent."

Herkomst[bewerken]

Toen 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[bewerken]

In 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).

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 waaraan het gevraagd is Onwaar of Waar is.

Als we dit gebruiken, is een mogelijke oplossing:

  1. Vraag aan god Y: "Als ik jou zou vragen 'Is X Willekeur?', zou je dan 'dah' antwoorden?". Als Y 'dah' antwoordt, dan is ofwel Y zelf Willekeur, ofwel is X Willekeur. In beide gevallen is Z dus niet Willekeur. Als Y 'nah' antwoordt, dan is ofwel Y Willekeur, ofwel Z, en dus is X zeker niet Willekeur.
  2. 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.
  3. Vraag aan dezelfde god "Als ik u zou vragen 'Is Y Willekeur', zou u dan 'dah' antwoorden?" Als het antwoord 'dah' is, is Y 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, die gebruik maakt van ingewikkeldere vraagstelling. In dat geval kan men de identiteit zelfs achterhalen met twee vragen.

Zie ook[bewerken]

Externe links[bewerken]