Two Gates and Two Angels - with a Twist

There’s a famous riddle that goes like this:

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. Beside 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.

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?

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

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

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?

The solution can be found some space below.

Solution:

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.

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

“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?”

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.

Now here’s some explanation: think of an answer passing through an angel as being XNORed 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:

(Here’s the original Inkscape SVG image).

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 Commutative and Distributive, 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”.

I originally published this riddle on on rec.puzzles on Usenet. 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.