Find the Murderer
My former student, Xiaoyu He, invented this elegant puzzle and shared it with me.
Share:Puzzle. We’ve got a murder mystery on our hands. There are four suspects, and it’s pretty clear that one of them is the actual murderer. But here’s the twist: there are also four witnesses who know who the killer is. Now, three of these witnesses are the honest type, always telling the truth, but the fourth one always lies.
You get to ask each of these witnesses a single yes-or-no question, and your question must be, “Is the murderer among this group of suspects?” You can choose any group of suspects you want. The challenge is to figure out who the murderer is.
Can you take it up a notch and determine the murderer if you have to list all your questions before getting any of the answers?
Konstantin:
Yes, I can.
First three questions about {1, 2} set, and the last questions about {1,3}.
4 October 2023, 4:40 pmZarunias:
Somehow by quickly thinking over this problem, I missed this obvious (?) solution, so I solved this problem in some strange way: First I came to the conclusion that this problem is equivalent to following problem: Mark 4 of the 16 vertices of a 4-dimensional cube in such a way that no 2 marked vertices have a distance of exactly 2 edges (the marked vertices represent the answers of the 4 witnesses if nobody lies – if there are two vertices with distance 2 you wouldn’t get an unique possible murderer if the set of 4 answers lies inbetween).
5 October 2023, 7:22 pmBy drawing this it’s easy to see that there is a solution: (0000),(0001),(1110) and (1111). And from this you come to the already presented solution.
With this method I additionally can proof that (apart from permutations) this is the only solution.
Ali Mohammadinia:
Yes.
13 October 2023, 2:01 pmAsk From 1 & 2 about {3, 4},
Ask From 3 & 4 about {1,2}.
A-non-Austrian:
For Ali, what if the 3rd witness lies and the murderer was the first suspect? The first 2 witnesses agree that the murderer isn’t in 3 or 4, but then you can’t tell between who is the murderer between 1 and 2.
19 October 2023, 12:24 amSanjay Godse:
The four questions can be
23 October 2023, 12:54 am{1,2}
{1,3}
{3,4}
{3,4}
Alkis Piskas:
A condition is missing from the problem: How many times each witness can be asked that single question. If the condition is “only once”, then this is indeed a very interesting puzzle. I can’t find a solution for it. I need to ask at least one witness twice.
BTW, it seems some people found a solution but no one of has proved it. (At the time of my writing this.)
30 October 2023, 3:57 amCyberK:
@Alkis
It can be solved with the interpretation “only once”. I guess it’s in the spirit of the blog that some people will rather give a hint than a complete solution.
Proving that something is a solution is easy, if a little tedious – there are 4×4 combinations of lier&murderer and 16 possible Y/N answers for the selected 4 subsets. If every L&M combination maps to a unique Y/N 4-tuple, then it is a solution.
Technically it doesn’t even need to be unique (we don’t need to identify the lier), just that there are no 4-tuples belonging to different murderer cases. (I’m not sure if this case is even possible though).
I arrived at essentially the same solution as Konstantin (a slight permutation), there’s a certain logic to it beyond just checking all 16 L&M cases. See if you can figure out why that is a solution.
Ali’s solution is not right as explained, I can’t say I can follow Zarunias’ logic, but given that Sanjay’s answer also looks to be a solution and it’s not a permutation of Konstantin’s solution, his claim of solution uniqueness seems suspicious.
This could also be made into a nice programming problem for HS competitions – find out all solutions. I was thinking of doing it if I find some time for it.
2 November 2023, 11:10 amZarunias:
Yes, Sanjay’s solution is not strictly a permutation of Konstantin’s solution but in a wider senseit is: As a question {3,4} is equal to a question {1,2} (regarding the information you get out of it) I didn’t differentiate between those.
2 November 2023, 9:17 pm