Go back
Liars and truth-tellers

Liars and truth-tellers

Posers and Puzzles

a
Standard memberandrew93

.

Joined
06 Feb 10
Moves
6916
Clock
12 Sep 11
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.

iamatiger
Standard memberiamatiger

Joined
26 Apr 03
Moves
26771
Clock
12 Sep 11
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.

iamatiger
Standard memberiamatiger

Joined
26 Apr 03
Moves
26771
Clock
12 Sep 11
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?

JS357
SubscriberJS357

Joined
29 Dec 08
Moves
6788
Clock
12 Sep 11
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?

iamatiger
Standard memberiamatiger

Joined
26 Apr 03
Moves
26771
Clock
12 Sep 11
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

iamatiger
Standard memberiamatiger

Joined
26 Apr 03
Moves
26771
Clock
12 Sep 11
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.

iamatiger
Standard memberiamatiger

Joined
26 Apr 03
Moves
26771
Clock
12 Sep 11
1 edit
Vote Up
Vote Down

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
Standard memberiamatiger

Joined
26 Apr 03
Moves
26771
Clock
12 Sep 11
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

iamatiger
Standard memberiamatiger

Joined
26 Apr 03
Moves
26771
Clock
13 Sep 11
4 edits
Vote Up
Vote Down

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
SubscriberJS357

Joined
29 Dec 08
Moves
6788
Clock
13 Sep 11
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:
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.

a
Standard memberandrew93

.

Joined
06 Feb 10
Moves
6916
Clock
13 Sep 11
Vote Up
Vote Down

Nice solution.

P
Standard memberPalynka
Upward Spiral

Halfway

Joined
02 Aug 04
Moves
8702
Clock
04 Oct 11
1 edit
Vote Up
Vote Down

Excelent work iamatiger!

P
Standard memberPalynka
Upward Spiral

Halfway

Joined
02 Aug 04
Moves
8702
Clock
04 Oct 11
Vote Up
Vote Down

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

t
Standard membertomtom232

Joined
15 Jun 06
Moves
16334
Clock
04 Oct 11
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.

t
Standard membertomtom232

Joined
15 Jun 06
Moves
16334
Clock
04 Oct 11
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.