Go back
Liars and truth-tellers

Liars and truth-tellers

Posers and Puzzles

1 edit
Vote Up
Vote Down

@iamatiger : I predicted the 34 in an earlier post for the WCS under a double group method, and I also recommended a deductive method for reducing the question count - did you not see that? I genuinely don't think you need to exhaustively test all combinations.

I also think there may be an issue with Palynka's method - see my post above.

Vote Up
Vote Down

Aha!!!!
I believe I have it!

Worst case questions (51T 49L) == 98 (= N-2)

And I can take just 18 questions to solve the 11T 9L case that took 34 before.
I'm in the process of implementing the algorithm I have thought of to make sure it works.

2 edits
Vote Up
Vote Down

Yep! Tested it out
11T, 9L worst case 18 questions, successfully located a truther with all combos.

13 T, 11L (2,496144 combinations!) worst case 22 questions, and again located a truther each on each pass.

So Questions = N_people - N_Truthers + N_Liars = 2 * N_liars (it works with even only one more truther than liars, and doesn't change if only truthers are added)

Do people want to see my method? Or try to work it out themselves?

Vote Up
Vote Down

Originally posted by iamatiger
Yep! Tested it out
11T, 9L worst case 18 questions, successfully located a truther with all combos.

13 T, 11L (2,496144 combinations!) worst case 22 questions, and again located a truther each on each pass.

So Questions = N_people - N_Truthers + N_Liars (it works with even only one more truther than liars)

Do people want to see my method? Or try to work it out themselves?
This forum is always about posting solutions. It would be hard to post it hidden but I for one want to see it. Anybody who doesn't want to see it can stop as soon as they see it is your method being announced.

Could you exhaustively walk through a very minimal example with N_T-N_L=2? Such as N_P=4, or 6?

1 edit
Vote Up
Vote Down

Initialise N_liars = num liars, Difference = N_truthers - N_liars

make a linked list of the people, e.g with people a,b,c..h the list is:

a->b->c->d->e->f->g->h

Start with the first person (a)

0) Finish if the current person is Difference-1 from list end

1) Ask the current person whether the next person in the list lies

2) If he says "No", then move on to the next person and goto 0)

3) If he says "Yes" snip him and the next person out of the list

3.1) Decrement N_liars

3.2) Set the current person to the person before him

3.3) Or to the first person in the list if there is nobody before him

If Exit is hit at 0 then:

The person at position N_liars+1 (1st person = 1) is a truther

2 edits
Vote Up
Vote Down

(also exit if n liars=0 when all remaining people must be truthers)


Eg with 4 truthers, 2 liars:

Assume liars always say the next person is a truther


if in order L->L->T->T->T->T

Nobody says the next person is a liar

so we exit at the bracketed person:

L->L->T->T->(T)->T

and determine that the person N-liars+1 from the start

must be a truther:

L->L->[T]->T->T->T


if in order L->T->T->T->T->F

Nobody says the next person is a liar

so we exit at the bracketed person:

L->T->T->T->(T)->F

and determine that the person N-liars+1

from the start must be a truther:

L->T->[T]->T->T->F


if in order T->T->T->T->F->F

when we get to the fourth T he says the next guy is a liar

so we remove them

T->T->(T)->F

Now we are on the bracketed guy who is the correct

threshold from the

end and we determine that the guy in square brackets is a truther

T->[T]->T->F


if in order T->T->T->F->F->T

The second T says the next guy is a liar,

so we remove them and are on the bracketed guy:

T->(T)->F->T with N liars = 1

He says the *next* guy is a liar too, so we remove them,

(T)->T and now N liars is 0

so we exit declaring all remaining guys to be truthers.

1 edit
Vote Up
Vote Down

With 9 liars, 11 truthers the distibution of Num questions needed is:

N_questions, Occurrences
91
1011
1166
12286
131001
143003
158008
1619448
1743758
1892378


With 10 liars, 12 truthers the distribution is:
101
1112
1278
13364
141365
154368
1612376
1731824
1875582
19167960
20352716

4 edits
Vote Up
Vote Down

The principle is, if we arrange everyone in a ring

and there are a mixture of truthers + liars

then, at least 1 truther must have a liar to his left

we can locate that pair and remove them

and. if we get close enough to going all the way round

with nobody saying a liar is to their left

then we can predict what the next person is going to say without asking them!

I like that with 1000 truthers and 2 liars, I only need 4 questions

4 edits
Vote Up
Vote Down

Now I've managed to reduce it by 1 to 17 for 9L 11T with the following histogram:
92036
108104
1117570
1227170
1333000
1432604
1526026
1615730
175720

Max questions is now Liars*2- 1
The tweak was to the finishing case, exit as soon as the length of the current chain of people asked was greater than the number of liars left, with the answer being the person you would ask a question next.

A worst case for 9L 11T goes like this:

Where the one in brackets is the guy we are just about to query, T is the length of the chain, L is the number of liars left and Q is the number of questions we have asked.

(T)TTTTTTTTLLLLLLLLTTL T 1 L 9 Q 0
T(T)TTTTTTTLLLLLLLLTTL T 2 L 9 Q 1
TT(T)TTTTTTLLLLLLLLTTL T 3 L 9 Q 2
TTT(T)TTTTTLLLLLLLLTTL T 4 L 9 Q 3
TTTT(T)TTTTLLLLLLLLTTL T 5 L 9 Q 4
TTTTT(T)TTTLLLLLLLLTTL T 6 L 9 Q 5
TTTTTT(T)TTLLLLLLLLTTL T 7 L 9 Q 6
TTTTTTT(T)TLLLLLLLLTTL T 8 L 9 Q 7
TTTTTTTT(T)LLLLLLLLTTL T 9 L 9 Q 8
TTTTTTT(T)LLLLLLLTTL T 8 L 8 Q 9
TTTTTT(T)LLLLLLTTL T 7 L 7 Q 10
TTTTT(T)LLLLLTTL T 6 L 6 Q 11
TTTT(T)LLLLTTL T 5 L 5 Q 12
TTT(T)LLLTTL T 4 L 4 Q 13
TT(T)LLTTL T 3 L 3 Q 14
T(T)LTTL T 2 L 2 Q 15
(T)TTL T 1 L 1 Q 16
T(T)TL T 2 L 1 Q 17

Sow now we would get an answer of 49*2 - 1 = 97 for the question as posed

Vote Up
Vote Down

Originally posted by iamatiger
Now I've managed to reduce it by 1 to 17 for 9L 11T with the following histogram:
92036
108104
1117570
1227170
1333000
1432604
1526026
1615730
175720

Max questions is now Liars*2- 1
The tweak was to the finishing case, exit as soon as the length of the current chain of people asked was greater than the number of liars left, with the a ...[text shortened]... (T)TL T 2 L 1 Q 17

Sow now we would get an answer of 49*2 - 1 = 97 for the question as posed
That is a very clear presentation of how the worst case works out. Thanks. What an interesting outcome.

Vote Up
Vote Down

Nice solution.

1 edit
Vote Up
Vote Down

Excelent work iamatiger!

Vote Up
Vote Down

That said...are you andrew93? andrew93's first post sounds remarkably like a continuation of the conversation by you. 😕

2 edits
Vote Up
Vote Down

Does a liar always tell the truth if he just told a lie and vice versa? if so you could ask each person about somebody twice and the first person with a consistent answer would be a truther... this would take maximum of 98 questions because after 98 you would eliminate all the liars and the rest would all be truthers.

3 edits
Vote Up
Vote Down

Here is a nice spin on the problem.

Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking two yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, in some order. You do not know which word means which.

-It could be that some god gets asked more than one question (and hence that - the other gods are not asked any question at all).
-What the second question is, and to which god it is put, may depend on the answer to the first question.
-Whether Random say ja or da should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he say ja; if tails, da.
Random will answer da or ja when asked any yes-no question.

Cookies help us deliver our Services. By using our Services or clicking I agree, you agree to our use of cookies. Learn More.