Liars and truth-tellers

Originally posted by iamatiger
First, 50 questions leaves us with (25,24) TL.
There is a max of 100 initial questions rather than 50, if a pair is TT, FF, or FT (F asked first) then that pair takes 2 questions to categorise, 1 per person.

Then you have 48 people, but you don't know what they are, so you need another 48 questions, then 24 then 12, then 6 I think?

That wo ...[text shortened]... ions, I'm not sure why it is 4 less than my method, need to think and perhaps simulate them???

Right! I need to revise my numbers. I need to double most of them, right? I was using only one question to eliminate a pair... Let me see... (R is taking representatives from each pair)

Start
51 49
Q-100
50 48
R
25 24
Q-48
24 22
R
12 11
Q-22
12 10
R
6 5
Q-10
6 4
R
3 2
Q-4
3 1
Done!
Total Q- 184

Hopefully I've got it right... I think this is just a variation which should be equivalent to your collecting in groups strategy (the representatives just make it easier to think about it, I guess) so we should be getting the same number if that's exactly what you did... Perhaps is where I can get rid of the unpaired L. I have to say I need to look at it tomorrow with a fresh mind to understand it.

I've implemented my algorithm in perl and tested it out with all combos of 7 truthers and 5 liars, the max was 18, which is 2(n-3) as predicted

the kind of combination which gets to the max is:
TTTTLTLLLTTL
Num liars is 5, so our threshold is 6
here we ask the second guy about the first, and then the first guy about the second (2 questions) then stick them in the questioned group:

(TT) (TTLTLLLTTL)

now we ask a quy in the questioned group about the first guy in the other group (4 questions) and incorporate that guy.
(TTT) (TLTLLLTTL)

we incorporate the next truther and we are now on 6 questions
(TTTT) (LTLLLTTL)

As the free set is the larger we ask the liar first, so we need two more questions to eliminate a pair (8 questions), threshold decreases to 5.

(TTT) (TLLLTTL)

We now have truther asking truther, which takes us to 10 questions
(TTTT) (LLLTTL)
another truther would complete the search, but now we get a liar, as his set is larger we ask him first, so we are on 12 questions, threshold 4
(TTT) (LLTTL)
and another liar, 14 questions, threshold 3
(TT) (LTTL)
ANOTHER liar, 16 questions, threshold 2
(T) (TTL)
and finally another truther, which takes us to 18 questions but now meets our threshold. note that another liar would have finished too, as there would only have been two left.
(TT)<-accepted (TL)

I suppose your algorithm would be slightly quicker worst case on 7T 5L Palynka? I wonder why??? am I missing something?

Originally posted by iamatiger
I've implemented my algorithm in perl and tested it out with all combos of 7 truthers and 5 liars, the max was 18, which is 2(n-3) as predicted

the kind of combination which gets to the max is:
TTTTLTLLLTTL
Num liars is 5, so our threshold is 6
here we ask the second guy about the first, and then the first guy about the second (2 questions) then stic ...[text shortened]... would be slightly quicker worst case on 7T 5L Palynka? I wonder why??? am I missing something?

Mine
7 5
Q-14
6 4
R
3 2
Q-4
And we're done with 18, which is what you get... So I guess the advantage may be when in the 51,49 case I get an odd number of T and an even number ofL at (25,24). There I manage to get rid of 2 L and a T. When it's the other way around (12,11), I get rid of only one L. But your algorithm is not what I thought, would you say it's equivalent to your group gathering idea? I'm not seeing how, if true...

The algorithm is as described in my earlier post. I realised that after I had the group gathering idea, that if I processed the people one at a time rather than all at once, I only needed two groups. The only tweak, is that where it says "select a random man" I select the first man in the group. This is because random selection can always be unlucky and hit the worst case, and making the selection deterministic greatly reduces the possibilities to search through to locate the worst cases. I can post my perl up here if you like, but it is hard to format code nicely on these groups, for example indentation is very difficult.

I am wondering whether your strategy might get in trouble with some combinations, for instance with 51 T, 49 L, what if 3 pairs are rejected on the first pass? These could be TF FF FF, or TF TF TF

therefore after the initial stage you don't know whether you have 50T, 44 L or 48T, 46L

if the next pairing is exact, and you throw away half, then you either have 25T, 22L or 24T 23L, and so after a second pairing off I think you can't tell whether the odd man is a L or a T? I can't see a very good way to cater for this except to give ambiguous odd men a "bye" to the next round. But may that mean you sometimes need more questions than you thought?

Just run it with 11T, 9L (167960 combinations!)

worst were 4290 "worst case" combinations like
TTLTLTLTLTLTLTLTLLTT
TTLTLTLTLTLTLTLTLTLT
TTTTTTTTTLLLLLLLLLTT
which all took 34 tries as predicted: 2(n-3) = 34

Unfortunately it would probably take many years to do an exhaustive run on 51/49, looking at the three above it seems 49Ts, followed by 49 Ls, followed by 2 Ts would be a worst case, and that combo does indeed take 194 as predicted: 2(100-3) = 194

Originally posted by iamatiger
The algorithm is as described in my earlier post. I realised that after I had the group gathering idea, that if I processed the people one at a time rather than all at once, I only needed two groups. The only tweak, is that where it says "select a random man" I select the first man in the group. This is because random selection can always be unlucky and h to the next round. But may that mean you sometimes need more questions than you thought?

Definitely possible. On the plus side, more initial pairings means less people to ask, but on the minus side I may need to give "byes", which means more questions. I need to think about it... I'll be off for a few days, though.

Originally posted by iamatiger
Just run it with 11T, 9L (167960 combinations!)

worst were 4290 "worst case" combinations like
TTLTLTLTLTLTLTLTLLTT
TTLTLTLTLTLTLTLTLTLT
TTTTTTTTTLLLLLLLLLTT
which all took 34 tries as predicted: 2(n-3) = 34

Unfortunately it would probably take many years to do an exhaustive run on 51/49, looking at the three above it seems 49Ts, followed by 49 L ...[text shortened]... y 2 Ts would be a worst case, and that combo does indeed take 194 as predicted: 2(100-3) = 194

What if you have 2 questioned groups (one on each side)? Seems less efficient, but the WCS configuration seems so skewed, that forcing L towards the middle may help.

Originally posted by Palynka
What if you have 2 questioned groups (one on each side)? Seems less efficient, but the WCS configuration seems so skewed, that forcing L towards the middle may help.

Lets looks at that idea with
TTLTLTLTLTLTLTLTLLTT

4 questions:
(TT)LTLTLTLTLTLTLTLL(TT)
8 questions:
(T)TLTLTLTLTLTLTL(T)
12 questions:
(TT)LTLTLTLTLTL(T)
16 questions
(T)TLTLTLTL(T)
18 questions
(TT)LTLTL(T)
24 questions
(T)TL(T)
28 questions
(TT)()
finished

which is indeed less than 34, but there might still be a worst case for it:
try:
TTLTLTLTLLTLTLTLTTTL
4 questions:
(TT)LTLTLTLLTLTLTLT(T)
8 questions:
(T)TLTLTLLTLTLTL(TT)
12 questions:
(TT)LTLTLLTLTLT(T)
16 questions:
(T)TLTLLTLTL(TT)
20 questions
(TT)LTLLTLT(T)
24 questions
(T)TLLTL(TT)
28 questions:
(TT)LLT(T)
(cant exit yet, 2 liars could be in left hand group )
32 questions:
(T)L(TT)
hmm, looks like we can finish here, as the right hand group is half the total so must both be T

Ok! that took two questions less! it will be tricky to implement but I will need to to make sure that there is not a cunning "worser" case I have missed.

Originally posted by iamatiger
Lets looks at that idea with
TTLTLTLTLTLTLTLTLLTT

4 questions:
(TT)LTLTLTLTLTLTLTLL(TT)
8 questions:
(T)TLTLTLTLTLTLTL(T)
12 questions:
(TT)LTLTLTLTLTL(T)
16 questions
(T)TLTLTLTL(T)
18 questions
(TT)LTLTL(T)
24 questions
(T)TL(T)
28 questions
(TT)()
finished

which is indeed less than 34, but there might still be a worst case for it: ...[text shortened]... ement but I will need to to make sure that there is not a cunning "worser" case I have missed.

I just want to say this is great watching great brains do what only they can do.

In my simulations I found the following sorts of queues throw up the highest question counts, depending on whether it was a single/multi group and using varying methods for extracting unprocessed people from the queue:
TTTTTTTTTTTLLLLLLLLL
and also arrangements such as:
TTLTLTLTLTLTLTLTLTLT

Using the double queue per your post, and starting with this:
TTTTTTTTTTTLLLLLLLLL
after 32 questions we have:
(TTTTTTTTT)TT(LLLLLLLLL)

By deduction we know the 2 people in the middle must be T (given both processed groups must be full of the same types and we have exhausted all of the Ls in one of the groups) but we haven't yet met the condition per the algorithm that one of the groups is at least half the size of the remaining population. So we could stop at 32 if we didn't have to meet that condition. But given the condition g>=n/2, then under the WCS we have to ask 2 more questions.

I ran some simulations last night using n/2 groups and applying the round robin and other methods of subsequent pairings - this method had some very high worst case scenarios in excess of the 194 I saw in my single group / single queue WCS simulation for 100 people. If 2 groups is better than 1 (by deduction), I'm not sure that it follows that more groups (to the point of n/2) is better given we relied on deduction combined with the algorithm (rather than just the algorithm), to get a lower question count.

In my opinion you don't need to examine every possible combination to test a method. After devising a method, I process a queue that doesn't match the rules for elimination for as long as possible and requires the greatest number of questions to eliminate TL pairings. So the WCS for the double queue method requires the two processed groups to be as full as possible for as long as possible - this is achieved using the queue posted above.

Originally posted by Palynka
Mine
7 5
[b]Q-14
6 4
R
3 2
Q-4
And we're done with 18, which is what you get... So I guess the advantage may be when in the 51,49 case I get an odd number of T and an even number ofL at (25,24). There I manage to get rid of 2 L and a T. When it's the other way around (12,11), I get rid of only one L. But your algorithm is not what I thought, would you say it's equivalent to your group gathering idea? I'm not seeing how, if true...[/b]

I think I'm following your post to a point. If I haven't described it correctly please let me know.

{We have a population of}
7T 5L
{We pair them up and under WCS we must ask}
Q12
{and under WCS we eliminate 1 pair leaving}
6T 4L
{the next part I don't understand. Given we don't have the people organised in two groups (one of T and the other of L), and we now pick a sample}
R5
{and ask}
4Q
{with 1 bye - is that right?}
and under WCS we could have selected 5T or 5L in R, eliminating zero.

If we could group them such that we knew with certainty we can select 5R made up of 3T and 2L then we wouldn't need to ask any more questions.....unless I have misunderstood your post?

Originally posted by Palynka
What if you have 2 questioned groups (one on each side)? Seems less efficient, but the WCS configuration seems so skewed, that forcing L towards the middle may help.

Tried the "one each side" algorithm you suggested, with 11T 9L, the worst case stubbornly remains 34, although now only 415 combos hit that rather than 4290:

The problematic ones are things like:
TTTTTTLLTTTTTLLLLLLL

which goes:
(4 questions..)
(TT)TTTTLLTTTTTLLLLL(LL)
(8 questions..)
(TTT)TTTLLTTTTTLLLL(LLL)
(12 questions..)
(TTTT)TTLLTTTTTLLL(LLLL)
(16 questions..)
(TTTTT)TLLTTTTTLL(LLLLL)
(20 questions..)
(TTTTTT)LLTTTTTL(LLLLLL)
(24 questions..)
(TTTTT)LTTTTT(LLLLLLL) threshold 9
(28 questions..)
(TTTT)TTTT(LLLLLL) threshold 7
(32 questions..)
(TTTTT)TT(LLLLL) threshold 6
I don't think we can exit there, as we can't tell whether the combination is as the above or: (LLLLL)TT(TTTTT); or (TTTTT)LL(TTTTT) ; or (TTTTT)TL(TTTTT), which I think could be reached from other start combinations with the same discard sequence.
so:
(34 questions..)
(TTTTTT)T(LLLLL) threshold 6 Now we know the LHS must all be truthers and we can exit.

Originally posted by iamatiger
Tried the "one each side" algorithm you suggested, with 11T 9L, the worst case stubbornly remains 34, although now only 415 combos hit that rather than 4290:

The problematic ones are things like:
TTTTTTLLTTTTTLLLLLLL

which goes:
(4 questions..)
(TT)TTTTLLTTTTTLLLLL(LL)
(8 questions..)
(TTT)TTTLLTTTTTLLLL(LLL)
(12 questions..)
(TTTT)TTLLTTTTTLL ...[text shortened]... s..)
(TTTTTT)T(LLLLL) threshold 6 Now we know the LHS must all be truthers and we can exit.

By the way I PM'd David113 who originated this thread, suggesting he look at the results. No response. He happens to be a non-sub who has not yet made a chess move on the site.

Originally posted by iamatiger
Tried the "one each side" algorithm you suggested, with 11T 9L, the worst case stubbornly remains 34, although now only 415 combos hit that rather than 4290:

The problematic ones are things like:
TTTTTTLLTTTTTLLLLLLL

which goes:
(4 questions..)
(TT)TTTTLLTTTTTLLLLL(LL)
(8 questions..)
(TTT)TTTLLTTTTTLLLL(LLL)
(12 questions..)
(TTTT)TTLLTTTTTLL s..)
(TTTTTT)T(LLLLL) threshold 6 Now we know the LHS must all be truthers and we can exit.

I am wondering if your data allows an analysis and estimation of the distribution of questions needed for a given pairing strategy. For example, if the maximum under the WCS were the same for two strategies, would the median values of the two strategies run on a large number of randomly chosen (or exhaustive study of) scenarios be of interest?

Originally posted by JS357
I am wondering if your data allows an analysis and estimation of the distribution of questions needed for a given pairing strategy. For example, if the maximum under the WCS were the same for two strategies, would the median values of the two strategies run on a large number of randomly chosen (or exhaustive study of) scenarios be of interest?

Maybe of interest (the exact distribution of num questions would also be of interest!) but neither are directly relevant to this question, which asks for the minimum worst case number, i.e. the maximum.

Palynka! Can you perhaps come up with the Minimum N people (where N liars = N truthers - 2) where you believe getting rid of an odd one should give your method an advantage? If we can find one with N ~ 20 or so we may be able to do an exhaustive evaluation of your strategy vs mine to see if your is *really* better for all combinations.

It looks to me as if 11, 9 is similar to 51,49, do we both get 34 for that....?