Liars and truth-tellers

David113

Posers and Puzzles

26 Aug '11 13:47

andrew93
.
Joined
06 Feb '10
Moves
6916
12 Sep '11 10:191 edit
@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.
iamatiger
Joined
26 Apr '03
Moves
26771
12 Sep '11 18:21
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.
iamatiger
Joined
26 Apr '03
Moves
26771
12 Sep '11 20:072 edits
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?
JS357
Joined
29 Dec '08
Moves
6788
12 Sep '11 20:33
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?
iamatiger
Joined
26 Apr '03
Moves
26771
12 Sep '11 21:011 edit
Reveal Hidden Content
Initialise N_liars = num liars, Difference = N_truthers - N_liars

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

Reveal Hidden Content
a->b->c->d->e->f->g->h

Reveal Hidden Content
Start with the first person (a)

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

Reveal Hidden Content
1) Ask the current person whether the next person in the list lies

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

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

Reveal Hidden Content
3.1) Decrement N_liars

Reveal Hidden Content
3.2) Set the current person to the person before him

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

Reveal Hidden Content
If Exit is hit at 0 then:

Reveal Hidden Content
The person at position N_liars+1 (1st person = 1) is a truther
iamatiger
Joined
26 Apr '03
Moves
26771
12 Sep '11 21:182 edits
Reveal Hidden Content
(also exit if n liars=0 when all remaining people must be truthers)

Reveal Hidden Content
Eg with 4 truthers, 2 liars:

Reveal Hidden Content
Assume liars always say the next person is a truther

Reveal Hidden Content
if in order L->L->T->T->T->T

Reveal Hidden Content
Nobody says the next person is a liar

Reveal Hidden Content
so we exit at the bracketed person:

Reveal Hidden Content
L->L->T->T->(T)->T

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

Reveal Hidden Content
must be a truther:

Reveal Hidden Content
L->L->[T]->T->T->T

Reveal Hidden Content
if in order L->T->T->T->T->F

Reveal Hidden Content
Nobody says the next person is a liar

Reveal Hidden Content
so we exit at the bracketed person:

Reveal Hidden Content
L->T->T->T->(T)->F

Reveal Hidden Content
and determine that the person N-liars+1

Reveal Hidden Content
from the start must be a truther:

Reveal Hidden Content
L->T->[T]->T->T->F

Reveal Hidden Content
if in order T->T->T->T->F->F

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

Reveal Hidden Content
so we remove them

Reveal Hidden Content
T->T->(T)->F

Reveal Hidden Content
Now we are on the bracketed guy who is the correct

Reveal Hidden Content
threshold from the

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

Reveal Hidden Content
T->[T]->T->F

Reveal Hidden Content
if in order T->T->T->F->F->T

Reveal Hidden Content
The second T says the next guy is a liar,

Reveal Hidden Content
so we remove them and are on the bracketed guy:

Reveal Hidden Content
T->(T)->F->T with N liars = 1

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

Reveal Hidden Content
(T)->T and now N liars is 0

Reveal Hidden Content
so we exit declaring all remaining guys to be truthers.
iamatiger
Joined
26 Apr '03
Moves
26771
12 Sep '11 21:351 edit
With 9 liars, 11 truthers the distibution of Num questions needed is:

N_questions, Occurrences
9 1
10 11
11 66
12 286
13 1001
14 3003
15 8008
16 19448
17 43758
18 92378

With 10 liars, 12 truthers the distribution is:
10 1
11 12
12 78
13 364
14 1365
15 4368
16 12376
17 31824
18 75582
19 167960
20 352716
iamatiger
Joined
26 Apr '03
Moves
26771
12 Sep '11 22:054 edits
Reveal Hidden Content
The principle is, if we arrange everyone in a ring

Reveal Hidden Content
and there are a mixture of truthers + liars

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

Reveal Hidden Content
we can locate that pair and remove them

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

Reveal Hidden Content
with nobody saying a liar is to their left

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

Reveal Hidden Content
I like that with 1000 truthers and 2 liars, I only need 4 questions
iamatiger
Joined
26 Apr '03
Moves
26771
13 Sep '11 04:474 edits
Now I've managed to reduce it by 1 to 17 for 9L 11T with the following histogram:
9 2036
10 8104
11 17570
12 27170
13 33000
14 32604
15 26026
16 15730
17 5720

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
JS357
Joined
29 Dec '08
Moves
6788
13 Sep '11 05:16
Originally posted by iamatiger
Now I've managed to reduce it by 1 to 17 for 9L 11T with the following histogram:
9 2036
10 8104
11 17570
12 27170
13 33000
14 32604
15 26026
16 15730
17 5720

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.
andrew93
.
Joined
06 Feb '10
Moves
6916
13 Sep '11 08:38
Nice solution.
Palynka
Upward Spiral
Halfway
Joined
02 Aug '04
Moves
8702
04 Oct '11 15:151 edit
Excelent work iamatiger!
Palynka
Upward Spiral
Halfway
Joined
02 Aug '04
Moves
8702
04 Oct '11 15:17
That said...are you andrew93? andrew93's first post sounds remarkably like a continuation of the conversation by you. 😕
tomtom232
Joined
15 Jun '06
Moves
16334
04 Oct '11 16:432 edits
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.
tomtom232
Joined
15 Jun '06
Moves
16334
04 Oct '11 17:413 edits
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.