shlomi-fish-homepage / t2 / MathVentures / two-angels-and-two-gates.html.wml

#include '../template.wml'

<latemp_subject "Two Gates and Two Angels - with a Twist" />

<p>
There's a famous riddle that goes like this:
</p>

<blockquote>

<p>
You are standing in front of two gates (a left one and a right one) - one 
leads to paradise and the other leads to hell. You don't know which gate
leads where. Besides the gates, there are two angels: one of them always tells 
the truth and the other always lies, but you also don't know which one
is which.
</p>

<p>
You have one question to ask one of the angels, in order to find out which gate
you should follow. What would that question be?
</p>

</blockquote>

<p>
Now, I came up with a harder variation of this riddle, which you should
consider only after you found the solution to the original:
</p>

<blockquote>

<p>
You are standing in front of two gates (a left one and a right one) - one 
leads to paradise and the other leads to hell. Besides the gates, there are
two angels, each one of them can either tell the truth all the time, or
constantly lie. Every angel knows where each door leads to, and the other
angel's orientation, but you don't, nor can assume anything.
(They can both be liars or both truth-tellers, or one of each).
</p>

<p>
You can ask one of the angels a single question, in order to find out which
gate you should follow. What would that question be?
</p>

</blockquote>

<p>
The solution can be found some space below.
</p>

<longblank />

<h2>Solution:</h2>

<p>
The solution to the first puzzle is to ask one of the angels "If I asked
the other angel, if the left gate leads to paradise, would he answer yes?".
One can see, that in this case, one will always get a false answer, according
to which one can determine which is the right gate.
</p>

<p>
Now for the tougher variation. The answer to this is to
ask one of the angels:
</p>

<blockquote>

<p>
"If I asked the other angel what you would answer, if I asked you what 
he would answer if I asked him if the left gate leads to paradise - what would 
he answer?"
</p>

</blockquote>

<p>
The answer will evaluate to a true one, so if it's "yes" - go to the left gate,
and if it's "no" - go to the right. 
</p>

<p>
Now here's some explanation: think of an answer passing through an angel
as being <a href="http://en.wikipedia.org/wiki/Exclusive_nor">XNORed</a>
with "T" if the angel is a truth-teller or "F" if he's a liar. So the
logical evaluation of the question I constructed looks like so:
</p>

<img src="two-angels.png" alt="Two Angels Logic Diagram" />

<p>
(Here's the <a href="two-angels.svg.gz">original Inkscape SVG image</a>).
</p>

<p>
As you can see, the angel values "L" (Left) and "R" right are XNORed exactly 
twice in the way to the solution. Since XNOR is <a 
href="http://en.wikipedia.org/wiki/Commutative">Commutative</a> and 
<a href="http://en.wikipedia.org/wiki/Distributivity">Distributive</a>, we
get "Truth XNOR (L XNOR L) XNOR (R XNOR R)". Since for every boolean 
"X XNOR X" is true, we get "Truth XNOR T XNOR T" which is the "Truth".
</p>

<p>
I originally published this riddle on
<a href="http://groups.google.com/group/rec.puzzles/msg/4e05d7f0912f3944">on
rec.puzzles on Usenet</a>. Someone emailed me back and suggested that
I could simply ask an angel "If I asked you which gate leads to paradise -
what would you say?" and he'd give the right answer. However, this leads
to interesting philosophical problems.
</p>

<hr />

<h3><a href="./">Back to the Math-Ventures web page</a></h3>
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.