Followup to the Stupidly Hard Dog Logic Puzzle

Buzzles
1

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! :exploding_head: 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)!
[commitment log: dreev.commits.to/post_dog_puzzle_followup_solution]

1 Like
2

Seems easy enough:

You ask the first dog: “Is at least one of the following true: Either
A) Your name is Argos; or
B) Your name is Buck and your answer to this question is ‘no’.”

Let’s call this question that we’re asking the first dog “question Q”, for the sake of clarity. This is so that we can replace the words “this question” in the last sub-clause with “question Q”.

Now, if the dog’s name is Argos, then case A will be true, and case B will be false, and so he will truthfully answer “Yes” to question Q, because at least one of the cases of the disjunction is true.

If the dog’s name is Clifford, then both case A and B will be false, so he will truthfully answer “No”.

If the dog’s name is Buck, then case A is clearly false, and so the truth-value of the disjunction is equal to the truth-value of just case B. So he needs to answer as if we just asked him B flat out.

Now, B is a conjunction, and the first part of it is certainly true (his name is Buck), so again we find that the answer he must give is equivalent to if we just asked him the second part: “Is your answer to question Q ‘no’?”.

It’s impossible for him to answer “yes”, because in that case the truth-value of Q would be “(false) OR (true AND false)”, and so the truthful answer is “no”.

It’s also impossible for him to answer “no”, because in that case the truth-value of Q would be “(false) OR (true AND true)”, and so the truthful answer is “yes”.

So, if his name is Buck, his head explodes.

Each of the three possibilities for the first dog’s name leads to a different answer from that dog, so after asking that question you know the first dog’s name. You can then move on to the second dog and ask it the simple yes/no question “Is your name X”, where X is one of the two remaining names.

Now you know the names of all three dogs.
Q.E.D.

1 Like
3

Impressive, @zzq! And beautifully exposited!

Here’s my similar write-up of my solution, in which I try to keep it as general as possible. The nice thing about this version is that it generalizes to finding out, with n questions, the answer to anything with up to 3^n possible answers. In this case there are 3!=6 possible identities of the 3 dogs. So we could also, for example, find the identities of 4 dogs (4!=24 possibilities) with 3 questions (3^3=27).

The goal is to construct a new kind of macro where we can map the possible answers – yes, no, :exploding_head: – into the answer to a multiple choice question with 3 choices.

Here’s how! “Of the mutually exclusive possibilities P, Q, and R, is at least one of the following true: (a) P is true, or (b) Q is false and the answer to this question is no?”

Consider the cases:

  • P is true, Q and R are false: Part (a) of the or-statement is true so the whole thing is true and the answer is yes.

  • Q is true, P and R are false: Part (a) of the or-statement is false and the first part of the and-statement in (b) is false so the whole thing is false and the answer is no.

  • R is true, P and Q are false: Part (a) is false and the first part of (b) is true so the whole thing reduces to ‘is the answer to this question no’ which makes the dog’s head explode.

As long as exactly one of P, Q, and R are true, that covers all the possibilities! We can now do ternary search through the possible dog identities:

ABC
ACB
---
BAC
BCA
---
CAB
CBA

First ask which third of those possible orderings – top, middle, bottom – has the correct one. That narrows it down to 2 possibilities so a totally normal 2nd question finishes you off. If there were more possibilities, just repeat the whole procedure with the possibilities you narrowed it down to. QED