The three trolls riddle

Here is a riddle, I encountered recently when browsing newly acquired discrete mathematics textbook. It’s really simple, when you remind yourself basics about mathematical logic, but I must admit that I was confused ath the beginning.

So here’s the riddle:

You are wandering through a magical forest and suddenly you encounter three magical trolls guarding the bridge, which you must pass, in order to continue your travel. Every troll may either say the truth or either lie. To pass the bridge you must properly identify which troll is which. But they will help, so:

  1. troll says: If I am lying, then exactly two other trolls are saying the truth
  2. troll says: Troll 1. is lying
  3. troll says: Either we are all lying or at least one of us is telling the truth

As I said, this might be confusing at the beginning, but when you review your knowledge about logics, it’s a piece of cake. At first you have to properly identify logic functions used by every troll. So the first one is using implication, second one negation and the last one is using disjunction. If troll is lying, then logical value of his statement must be true, otherwise if it’s lying, then it must be false. As simple as that.

If you still haven’t figured out the solution, then here it is:

Troll no. 3 will say the truth when one of the statements will be true. So when only one of them is false, the final value must be true. If statement ‘we are all lying’ would be true, then this troll may not be speaking the truth, because he would be telling truth about that he is lying. This is a paradox, so the first statement must be false, not every troll is lying. But what about second statement? Let’s just assume, that this is true.

Troll no. 2 says, that first troll is lying. If it is true, then it means troll no. 3 is telling the truth. But let’s check the troll no. 1. He can lie only when first statement will be true, but second one will be false. So he will lie only when he will be a lier and at least one of his comrades will be lying as well. Such outcome won’t be possible, because if troll 1 is lying and all other trolls are lying as well, then troll 3 must say the truth, which is impossible. If only troll 3 is saying the truth, then troll 2 must be lying, so troll 1 must say the truth, which also isn’t possible. The only possible solution is that, troll no. 1 is saying the truth, which gives us truth at the end, because falsehood may imply truth. Troll no. 2 is lying about troll 1, so his outcome is false and troll 3. is telling the truth, because he and troll 1 are telling the truth, so there is at leas one troll telling the truth.

The book containing the riddle is “Discrete Mathematics: An Open Introduction” by Oscal Levin.