Recall our previous logic puzzle (which was the so-called Hardest Logic Puzzle Ever in disguise), about finding the identities of 3 dogs – one that always lies, one that always truths, and one that’s random – with 3 questions. With the twist that they only answer with “arf” and “ruf” and you don’t know which means “yes” and which means “no”.
It turns out there’s a way to solve that with only 2 questions, sort of. Rather than ask you to think of how to do that, I’ll explain how it can even be possible and then the puzzle can be to actually come up with the questions.
But let’s further simplify it by dropping the lying (letting lying dogs truth?) since we’ve figured out how to turn liars and even random liars into impeccable truth-tellers. And we know the trick to turn arfs and rufs into logical yeses and nos, so forget that too.
So suppose there are 3 classic truth-telling, English-speaking dogs: Argos, Buck, and Clifford.
You now have to figure out who’s who with just 2 questions.
You might’ve said that’s provably impossible since there are 6 possible permutations of the 3 dogs and only 2 bits of information in 2 yes/no answers. (Also I guess we’re blind and so can’t see, for example, that Clifford is huge and red.)
Here’s the trick. We can allow something we didn’t allow before: exploding heads! There are questions like “will you answer no to this question?” which simply can’t be answered truthfully. It’s a perfectly logical proposition about the universe with a true yes/no answer, just that the dog can’t give that answer without creating a paradox. (If the dog says “no” then the true answer was “yes” and if the dog says “yes” then the true answer was “no”.) If you ask such a question the dog’s head explodes. Figuratively. Let’s not be gruesome here.
Ok, so now that there are 3 possible answers to to every question – yes, no, and head explodes – it should be theoretically possible to learn the dog identities with 2 questions. Can you?
I will (with ~95% probability) post the solution in a week (definitely not less)! http://dreev.commits.to/post_dog_puzzle_followup_solution