Cooperative Dedicated Liars
My new logic puzzle happens in the usual place: an island with truth-tellers and liars. Truth-tellers always tell the truth, while liars always lie. The liars on this island are dedicated to their lies: they do not want other people to figure out that they are liars and want to confuse people with their responses as much as possible. They also are cooperative: they coordinate their answers. The islanders all know each other and who is who.
Puzzle. A stranger arrives on this island with a plan. Each time the stranger hangs out with a group of people, he will ask each person the same question:
How many truth-tellers are in this group?
The liars on this island discover the stranger’s plan, and, being cooperative and dedicated, they do not want the stranger to figure out the true answer to his question. They also do not want the stranger to know anyone’s identity. What should they say?
For starters, any dedicated liar should always provide a theoretically possible answer. The liar shouldn’t say, “three quarters” or “infinitely many”, as these are obvious lies. In addition, the answer “zero” is too revealing: a truth-teller would never say this. Thus, the liar would answer with a positive integer that doesn’t exceed the total number of people in the group.
Suppose, for example, the stranger meets three people. Then there could be 0, 1, 2, or 3 truth-tellers in the group. As we discussed before, everyone replies 1, 2, or 3.
If there are t truth-tellers in the group, then the answer t is repeated exactly t times. That means the following sets of three answers reveal that all three islanders are liars: {1,1,1}, {1,1,2}, {1,1,3}, {2,2,2}, and {2,3,3}. With the following sets of answers, the stranger can figure out who is the only truth-teller: {1,2,3} and {1,3,3}. The set {2,2,3} allows the stranger to find both truth-tellers. And the following sets of answers do not allow the stranger to figure out who is who: {1,2,2} and {3,3,3}. So those sets of answers are the ones the liars will choose.
To sum up, the best strategy is for all the liars in the group to answer x, where x is the number of liars. Meanwhile, all the truth-tellers would say: 3 − x. That way, the stranger cannot differentiate between the truth-tellers and the liars.
The strategy above works with a group of any size as long as the number of liars is not equal to the number of truth-tellers.
Bonus Puzzle. Is there a way to confuse the stranger when the liars make are half of the group?
Share:
Bradley Kuszmaul:
Couldn’t {2,2,2} also mean there are 2 truthers? The liar wants to confuse, so they say 2.
The stranger cannot tell the difference between this case,and all three being liars.
25 May 2023, 4:25 pmtanyakh:
Bradley, in the model above, the liars always lie. However, this is a great idea for another model.
25 May 2023, 4:51 pmIsaac Grosof:
For any answer consisting of positive integers, it’s possible that all the answerers are liars, right? So an answer like {1,2,3} doesn’t prove that the person who said 1 told the truth, only that if someone told the truth, it was that person.
Also, I believe the liars can achieve complete ambiguity whenever the group size is not 2 or 4.
25 May 2023, 11:42 pmAli Mohammadinia:
if t truth teller + t liar -> one liar say “1” , other liar says “t-1”
if 2 truth teller + 2 liar -> stranger will know anyone’s identity.
26 May 2023, 2:01 amCristóbal Camarero:
With 2 truth tellers plus 2 liars, one of the liars could answer 1 and the other 0. The stranger clearly knows 0’s identity, but in principle he does not know if there is 1 or 2 truth tellers. However, if the stranger have already discovered the method employed by the liars, then he knows that with a single truth teller in the group, the liars would have answered 3. I wonder if there is some method which is robust even after being discovered.
26 May 2023, 12:57 pmAndreas:
All the x liars turn to the stranger, look them in the eyes and say “my friend, there are x+1 truth tellers: our group of x and you.”
27 May 2023, 4:41 amFelipe M Pait:
Let’s leave politics out of this blog 😉
Sorry, couldn’t resist the joke.
28 May 2023, 8:43 amTwo people speaking the truth (maybe):
[…] Maybe it was me, maybe it was the weather, but I just couldn’t stop looking for a good mystery. Fortunately, mathematician Tanya Khovanova created one and described it to her Blog. […]
9 June 2023, 6:27 amDos personas diciendo la verdad (tal vez) - Teknomers Noticias:
[…] Tal vez fui yo, tal vez fue el clima, pero no podía dejar de buscar un buen acertijo. Afortunadamente, a la matemática Tanya Khovanova se le ocurrió uno y lo describió en su Blog. […]
10 June 2023, 10:53 am