[bushindo]

This is an extension of my last which was flawed but still had some value to the board thanks to contribution from araver.

Suppose that you encounter 7 people, each of whom is either a truth teller (always tells the truth), a liar (always tell lies), or a random answerer (always answer randomly with 'Yes' or 'No'). You know that in this group of 7, there are 3 random answerers, 2 truth teller, and 2 liars, but you don't know which person is which. The puzzle is to identify the 3 random answerers with the following information:

1) You can only ask yes/no questions to 1 person at a time

2) You can ask the same question of different people, or address different questions to the same person.

3) You can not ask any question which is impossible for a truth teller/liar to answer with a yes/no (ie. asking a truth teller what a random answerer would say to a particular question, asking paradoxes, etc. )

4) Everytime you ask a question, your question count increases by 1

5) Each person in the group of 7 knows what type of people the remaining 6 are.

Determine a strategy that is guaranteed to find the 3 random answerers in 10 questions or less.

Edited November 23, 2010 by bushindo

[k-man]

Maybe I'm not understanding something, but how can you have any certainty after any number of questions when you're dealing with random answerers? If their answers are completely random then there is a possibility that for x number of questions they will answer exactly the same as a truth teller (or a liar) would, which makes it impossible to distinguish them.

T - Truth teller

L - Liar

R - Random

You can ask every person a question like "Are there 3 random answerers among you?", which will let you separate 7 people into 2 groups. One group will have 2 Ts and some Rs that happened to answer "Yes". The other group will have 2 Ls and some Rs that happened to answer "No". If you get lucky and all 3 random answerers answer this question the same way then you will get 2:5 distribution and can determine the 3 Rs by asking people in the group of 2 (whether Ts or Ls). But if you don't get lucky and get 3:4 distribution then I don't see how any strategy can be used to distinguish Ts from Rs or Ls from Rs in any limited number of questions.

But maybe it's just been a long day and I'm not thinking clearly...

[araver]

Determine a strategy that is guaranteed to find the 3 random answerers in 10 questions or less.

Actually, I have a very strong hunch that

it can be done in 8 questions (or less, depending on the answers). Worst case would be 3+1+1+3=8 questions

But I'm very far from actually writing such a successful strategy (at least the first part of it), so for now I guess I'm just bragging

Maybe I'm not understanding something, but how can you have any certainty after any number of questions when you're dealing with random answerers? If their answers are completely random then there is a possibility that for x number of questions they will answer exactly the same as a truth teller (or a liar) would, which makes it impossible to distinguish them.

You are correct, random answerers are a pain . However it's not completely unavoidable

You might want to try for yourself, then come back to this challenge.

[bushindo]

Actually, I have a very strong hunch that

it can be done in 8 questions (or less, depending on the answers). Worst case would be 3+1+1+3=8 questions

But I'm very far from actually writing such a successful strategy (at least the first part of it), so for now I guess I'm just bragging

I eagerly look forward to this strategy =)

[araver]

I eagerly look forward to this strategy =)

As I'm experiencing a series of electrical black-outs right now (about one every 30 min), I lost a part of what I had written, so it's going to take a while And since it's late night here, I'm probably going to finish this tomorrow.

However, here's a sneak peak of what I'm trying to accomplish:

Step 0 - Assume all liars are truth-tellers using known techniques to construct questions.

Step 1 - Get 4 of them in a line. Adaptive-strategy of 3-questions either gets you a truth-teller for sure (go to step 3, skipping step 2) or establish the fact that the other 3 not interrogated contain more truth-tellers than random answerers (either (2,0,1) or (3,0,0)-instances) in latter case go to step 2.

Step 2 (if needed) - Get the remaining 3 not interrogated in step 2. From 1 question you can get the location of one truth-teller among them.

Step 3 - Zero-in on the rest of the random answerers.

If step 2 was done, in the worst case only truth-tellers were there (which you cannot know for sure unless you actually spend a question), so 3 more questions are needed to determine the 3 random answerers from the first 4 in step 1.

If step 2 was skipped, then in at most 5 question you need to determine the random answerers. Normally 5 questions are needed (Is X random?) since you know one person and need-not ask the last one. Knowing the answers from step 1 may help save one of these 5 questions, but since the other branch is longer, I'll leave it like this.

Step 0 is trivial. I've written step 2 and step 3 (partially, as it depends on step 1).

Step 1 is tricky and prone to errors. I could be over-optimistic about only 3 questions needed.

Recap:

Step 0 - nothing

Step 1 - 3Q

Step 2 - 1Q

Step 3 - 1+3Q (if step 2) and 5Q (if step 2 is skipped)

Running total: 8Q

Edited November 24, 2010 by araver

[Akriti]

Sorry I didn't attempt the first two. So I have a question

Is there a rule to govern the answering of random answerer ? Like 1 time he speaks truth while 2 time he lies? or something like that?

[k-man]

Sorry I didn't attempt the first two. So I have a question

Is there a rule to govern the answering of random answerer ? Like 1 time he speaks truth while 2 time he lies? or something like that?

No rules. Random answerer is purely random. You cannot predict his answers, so they are useless. The purpose of the strategy is to avoid random answerers and zero-in on the truth tellers or liars to get definitive answers.

[araver]

As I'm experiencing a series of electrical black-outs right now (about one every 30 min), I lost a part of what I had written, so it's going to take a while And since it's late night here, I'm probably going to finish this tomorrow.

However, here's a sneak peak of what I'm trying to accomplish:

Step 0 - Assume all liars are truth-tellers using known techniques to construct questions.

Step 1 - Get 4 of them in a line. Adaptive-strategy of 3-questions either gets you a truth-teller for sure (go to step 3, skipping step 2) or establish the fact that the other 3 not interrogated contain more truth-tellers than random answerers (either (2,0,1) or (3,0,0)-instances) in latter case go to step 2.

Step 2 (if needed) - Get the remaining 3 not interrogated in step 2. From 1 question you can get the location of one truth-teller among them.

Step 3 - Zero-in on the rest of the random answerers.

If step 2 was done, in the worst case only truth-tellers were there (which you cannot know for sure unless you actually spend a question), so 3 more questions are needed to determine the 3 random answerers from the first 4 in step 1.

If step 2 was skipped, then in at most 5 question you need to determine the random answerers. Normally 5 questions are needed (Is X random?) since you know one person and need-not ask the last one. Knowing the answers from step 1 may help save one of these 5 questions, but since the other branch is longer, I'll leave it like this.

Step 0 is trivial. I've written step 2 and step 3 (partially, as it depends on step 1).

Step 1 is tricky and prone to errors. I could be over-optimistic about only 3 questions needed.

Recap:

Step 0 - nothing

Step 1 - 3Q

Step 2 - 1Q

Step 3 - 1+3Q (if step 2) and 5Q (if step 2 is skipped)

Running total: 8Q

bushindo, scratch my previous strategy, I was barking up the wrong tree

I found a flaw in all my attempted strategies and only after a while it hit me why Step 1 can never work.

Reason is simple:

If you get 4 of them in a line, there are 15 cases of which 14 are pairs of mirror cases ()), and the last TTTT has no mirror.

E.g. RTRT and TRTR (6 and 9 in the following list)

1	RRRT

2	RRTR

3	RTRR

4	TRRR

5	RRTT

6	RTRT

7	RTTR

8	TRRT

9	TRTR

10	TTRR

11	RTTT

12	TRTT

13	TTRT

14	TTTR

15	TTTT

I wanted to either get a truth-teller for sure or establish the fact that the other 3 not interrogated contain more truth-tellers than random answerers. That means either have only cases 11-15 on a branch or have a mix of cases where one position is surely a truth-teller.

However, for each pair of mirror cases, no matter how many enclosed questions you can think of, there's always a branch where that pair of mirror cases exists (since mirror cases really cannot be completely separated). E.g. there's absolutely no way you can distinguish between case 1 and case 14 on all branches.

So, there's no possible way to get a truth-teller for sure from this 4. And no way to separate the cases 11-15 from the rest.

Pity though, I liked my divide-et-impera strategy, hate to see it drown

So I'll be going the long road too, and it seems like it might take me 10 questions, too.

Edited November 24, 2010 by araver

[phaze]

Do the liars and truth tellers know what the random answer will answer for a given question?

Or in another way of asking it. Is the random answer for a particular question predetermined such that if I go to a truth teller and ask him what the random answerer will answer to a particular question and then go to the random answerer and ask him that question they will always be the same answer?

Asked to truth teller "If I next ask him (the random answerer) if he is a liar what will be his answer ?"

Truth teller: True

Asked to specified random answerer "Are you a liar?"

Random answerer: True

The answer will still be random to us it just means that the liar, truth teller and random answerer have access to the same random number table.

[bushindo]

Do the liars and truth tellers know what the random answer will answer for a given question?

Or in another way of asking it. Is the random answer for a particular question predetermined such that if I go to a truth teller and ask him what the random answerer will answer to a particular question and then go to the random answerer and ask him that question they will always be the same answer?

Asked to truth teller "If I next ask him (the random answerer) if he is a liar what will be his answer ?"

Truth teller: True

Asked to specified random answerer "Are you a liar?"

Random answerer: True

The answer will still be random to us it just means that the liar, truth teller and random answerer have access to the same random number table.

Let's say that the liars and the truth tellers do not know what the random answerers would respond to any given question. I think the question is more challenging that way.

[araver]

Sorry I didn't attempt the first two. So I have a question

Is there a rule to govern the answering of random answerer ? Like 1 time he speaks truth while 2 time he lies? or something like that?

Do the liars and truth tellers know what the random answer will answer for a given question?

Or in another way of asking it. Is the random answer for a particular question predetermined such that if I go to a truth teller and ask him what the random answerer will answer to a particular question and then go to the random answerer and ask him that question they will always be the same answer?

Asked to truth teller "If I next ask him (the random answerer) if he is a liar what will be his answer ?"

Truth teller: True

Asked to specified random answerer "Are you a liar?"

Random answerer: True

The answer will still be random to us it just means that the liar, truth teller and random answerer have access to the same random number table.

I believe there are several classical definitions for random answerers in these types of puzzles.

RandomFlipFlop: He doesn't look at the question. First time he flips a coin then simply says alternatively either Yes or No.

RandomWeak: Before answering a question he tosses a coin. If it is heads he lies, if it is tails he tells the truth.

RandomStrong: He doesn't look at the question, simply flips a coin and says either Yes or No.

I believe bushindo's random's are RandomStrong (from the wording of the puzzle) since this is the most challenging situation of the three

So randoms are not predictable by others and their answers don't depend on their previous answers.

EDIT: Just seen that bushindo already posted a reply.

Edited November 24, 2010 by araver

[phaze]

Let's say that the liars and the truth tellers do not know what the random answerers would respond to any given question. I think the question is more challenging that way.

Then going by rule number 3 we cant ask anyone what answer anyone else can give unless we a sure that we are either asking about a truth-teller / liar or asking the question to a random answerer?

[bushindo]

Then going by rule number 3 we cant ask anyone what answer anyone else can give unless we a sure that we are either asking about a truth-teller / liar or asking the question to a random answerer?

Yes, we can't ask anyone what answer someone else will give to a particular question, unless we are sure that we are either asking about a truth-teller / liar or asking the question to a random answerer.

[araver]

Then going by rule number 3 we cant ask anyone what answer anyone else can give unless we a sure that we are either asking about a truth-teller / liar or asking the question to a random answerer?

Yup ... or else his head might explode

Seriously, yes, you cannot ask that kind of questions (according to most opinions out there) since they force a third type of answer: either "I do not know" or "I can't answer" or head-exploding (I like this one most of all).

It's similar to a Turing machine or a program that has at least one branch that does not terminate (loops).

On the right input, it will give you a Yes/No answer (sooner or later)

On the wrong input, you might be waiting for an eternity without knowing for sure if it's going to respond eventually. You could ask it whether Fermat's Last Theorem is true (which would take a while, but eventually the machine would say Yes) or if P=NP (and still wait for the response as I'm doing now ).

Safe bet is to try only question that can be answered in all cases.

[araver]

My first strategy

In 9 questions.

Step 0 - Assume all liars are truth-tellers using known techniques to construct questions.

-------------------------------------------------------------------------------------------

First of all, the distinction between liars and truthtellers is irrelevant. A well-known technique (when dealing with truthtellers/liars alone) if you want to see if a statement P is true or not is to ask another question instead:

Q:"If I would ask you if P is true would you answer Yes?".

If P is true: a liar answers No to P therefore answering Yes to Q. a truthteller answers Yes to both P and Q.

If P is false: a liar answers Yes to P therefore answering No to Q. a truthteller answers No to both P and Q.

So P is true if and only if you get an Yes answer to Q.

Now assuming all questions are asked like this, we have transformed the problem to a similar problem with 3 randoms and 4 truthtellers. Moving on.

Step 1 - Static 6 questions

---------------------------

Assume all 7 are standing in a line.

I will ask each of the first 6 in line the same question: "Is the person next in the line (to your left/my right) to you a random?". Note that from Step 0, my actual question is "If I would ask you if the person next in the line to you is a random would you answer Yes?" to elicit the same response from truth-tellers and liars.

Note that this question reffers to only 2 people's position and has the following "truth table":

   Yes  No

RR  1   1

RT  1   1

TR  1   0

TT  0   1

where 1 means response is possible and 0 means response is impossible.

A truth-teller followed by a random cannot answer No and a truth-teller followed by a truth-teller cannot answer Yes.

These types of questions targeted at position X can be used to reduce the number of possibilities:

- branch Yes is true for all arrangements with randoms on position X and all arrangements with truth-tellers on X and randoms on X+1

- branch No is true for all arrangements with randoms on position X and all arrangements with truth-tellers on X and truth-tellers on X+1

There are 6 (static/non-adaptive) questions, so 2^6=64 possible combinations of answers.

The following table shows the possible arrangements for each combination and creates a "mask" of known positions: e.g. if only arrangements TRTTTRR and RTTTTRR are possible for a combination of answers then the last 5 positions are sure - written --TTTTRR (where - stands for an unknown).

1) NNNNNN- 1 possibilities: RRRTTTT. 7 sure positions: RRRTTTT.

2) NNNNNY- 1 possibilities: RRTTTTR. 7 sure positions: RRTTTTR.

3) NNNNYN- 2 possibilities: RTTTTRR, RRTTTRT. 5 sure positions: R-TTTR-.

4) NNNNYY- 2 possibilities: RTTTTRR, RRTTTRT. 5 sure positions: R-TTTR-.

5) NNNYNN- 3 possibilities: TTTTRRR, RTTTRRT, RRTTRTT. 3 sure positions: --TTR--.

6) NNNYNY- 3 possibilities: TTTTRRR, RTTTRTR, RTTTRRT. 4 sure positions: -TTTR--.

7) NNNYYN- 3 possibilities: TTTTRRR, RTTTRRT, RRTTRTT. 3 sure positions: --TTR--.

8) NNNYYY- 3 possibilities: TTTTRRR, RTTTRTR, RTTTRRT. 4 sure positions: -TTTR--.

9) NNYNNN- 4 possibilities: TTTRRRT, RTTRRTT, RRTRTTT, RRRTTTT. 1 sure position: ------T.

10) NNYNNY- 3 possibilities: TTTRRTR, RTTRTTR, TTTRRRT. 3 sure positions: -TTR---.

11) NNYNYN- 4 possibilities: TTTRTRR, TTTRRRT, RTTRTRT, RTTRRTT. 3 sure positions: -TTR---.

12) NNYNYY- 4 possibilities: TTTRTRR, TTTRRTR, TTTRRRT, RTTRTRT. 3 sure positions: -TTR---.

13) NNYYNN- 3 possibilities: TTTRRRT, RTTRRTT, RRTRTTT. 3 sure positions: --TR--T.

14) NNYYNY- 3 possibilities: TTTRRTR, RTTRTTR, TTTRRRT. 3 sure positions: -TTR---.

15) NNYYYN- 4 possibilities: TTTRTRR, TTTRRRT, RTTRTRT, RTTRRTT. 3 sure positions: -TTR---.

16) NNYYYY- 4 possibilities: TTTRTRR, TTTRRTR, TTTRRRT, RTTRTRT. 3 sure positions: -TTR---.

17) NYNNNN- 3 possibilities: TTRRRTT, RTRRTTT, RRRTTTT. 3 sure positions: --R--TT.

18) NYNNNY- 3 possibilities: TTRRTTR, RTRTTTR, RRTTTTR. 3 sure positions: ----TTR.

19) NYNNYN- 5 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT, TTRRRTT. 0 sure position: -------.

20) NYNNYY- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT. 2 sure positions: ----TR-.

21) NYNYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RRTTRTT, RTRRTTT. 1 sure position: ------T.

22) NYNYNY- 3 possibilities: TTRTRTR, TTRRTTR, TTRTRRT. 3 sure positions: TTR----.

23) NYNYYN- 5 possibilities: TTRTRRT, TTRRTRT, TTRRRTT, RTRTRTT, RRTTRTT. 1 sure position: ------T.

24) NYNYYY- 3 possibilities: TTRTRTR, TTRTRRT, TTRRTRT. 3 sure positions: TTR----.

25) NYYNNN- 4 possibilities: TTRRRTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

26) NYYNNY- 2 possibilities: TTRRTTR, RTRTTTR. 5 sure positions: -TR-TTR.

27) NYYNYN- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, TTRRRTT. 2 sure positions: -TR----.

28) NYYNYY- 3 possibilities: TTRTTRR, TTRRTRT, RTRTTRT. 4 sure positions: -TR-TR-.

29) NYYYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RTRRTTT, RRTRTTT. 1 sure position: ------T.

30) NYYYNY- 3 possibilities: TTRTRTR, TTRRTTR, TTRTRRT. 3 sure positions: TTR----.

31) NYYYYN- 4 possibilities: TTRTRRT, TTRRTRT, TTRRRTT, RTRTRTT. 3 sure positions: -TR---T.

32) NYYYYY- 3 possibilities: TTRTRTR, TTRTRRT, TTRRTRT. 3 sure positions: TTR----.

33) YNNNNN- 2 possibilities: TRRRTTT, RRRTTTT. 5 sure positions: -RR-TTT.

34) YNNNNY- 2 possibilities: TRRTTTR, RRTTTTR. 5 sure positions: -R-TTTR.

35) YNNNYN- 4 possibilities: TRTTTRR, RTTTTRR, TRRTTRT, RRTTTRT. 3 sure positions: ---TTR-.

36) YNNNYY- 4 possibilities: TRTTTRR, RTTTTRR, TRRTTRT, RRTTTRT. 3 sure positions: ---TTR-.

37) YNNYNN- 5 possibilities: TRTTRRT, RTTTRRT, TRRTRTT, RRTTRTT, TRRRTTT. 1 sure position: ------T.

38) YNNYNY- 4 possibilities: TRTTRTR, RTTTRTR, TRTTRRT, RTTTRRT. 3 sure positions: --TTR--.

39) YNNYYN- 4 possibilities: TRTTRRT, RTTTRRT, TRRTRTT, RRTTRTT. 3 sure positions: ---TR-T.

40) YNNYYY- 4 possibilities: TRTTRTR, RTTTRTR, TRTTRRT, RTTTRRT. 3 sure positions: --TTR--.

41) YNYNNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

42) YNYNNY- 3 possibilities: TRTRTTR, RTTRTTR, TRRTTTR. 3 sure positions: ----TTR.

43) YNYNYN- 5 possibilities: TRTRTRT, RTTRTRT, TRRTTRT, TRTRRTT, RTTRRTT. 1 sure position: ------T.

44) YNYNYY- 3 possibilities: TRTRTRT, RTTRTRT, TRRTTRT. 3 sure positions: ----TRT.

45) YNYYNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRTRTT, TRRRTTT, RRTRTTT. 2 sure positions: -----TT.

46) YNYYNY- 2 possibilities: TRTRTTR, RTTRTTR. 5 sure positions: --TRTTR.

47) YNYYYN- 5 possibilities: TRTRTRT, RTTRTRT, TRTRRTT, RTTRRTT, TRRTRTT. 1 sure position: ------T.

48) YNYYYY- 2 possibilities: TRTRTRT, RTTRTRT. 5 sure positions: --TRTRT.

49) YYNNNN- 3 possibilities: TRRRTTT, RTRRTTT, RRRTTTT. 4 sure positions: --R-TTT.

50) YYNNNY- 3 possibilities: TRRTTTR, RTRTTTR, RRTTTTR. 4 sure positions: ---TTTR.

51) YYNNYN- 4 possibilities: TRTTTRR, TRRTTRT, RTRTTRT, RRTTTRT. 3 sure positions: ---TTR-.

52) YYNNYY- 4 possibilities: TRTTTRR, TRRTTRT, RTRTTRT, RRTTTRT. 3 sure positions: ---TTR-.

53) YYNYNN- 6 possibilities: TRTTRRT, TRRTRTT, RTRTRTT, RRTTRTT, TRRRTTT, RTRRTTT. 1 sure position: ------T.

54) YYNYNY- 2 possibilities: TRTTRTR, TRTTRRT. 5 sure positions: TRTTR--.

55) YYNYYN- 4 possibilities: TRTTRRT, TRRTRTT, RTRTRTT, RRTTRTT. 3 sure positions: ---TR-T.

56) YYNYYY- 2 possibilities: TRTTRTR, TRTTRRT. 5 sure positions: TRTTR--.

57) YYYNNN- 5 possibilities: TRTRRTT, TRRRTTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

58) YYYNNY- 3 possibilities: TRTRTTR, TRRTTTR, RTRTTTR. 3 sure positions: ----TTR.

59) YYYNYN- 4 possibilities: TRTRTRT, TRRTTRT, RTRTTRT, TRTRRTT. 1 sure position: ------T.

60) YYYNYY- 3 possibilities: TRTRTRT, TRRTTRT, RTRTTRT. 3 sure positions: ----TRT.

61) YYYYNN- 6 possibilities: TRTRRTT, TRRTRTT, RTRTRTT, TRRRTTT, RTRRTTT, RRTRTTT. 2 sure positions: -----TT.

62) YYYYNY- 1 possibilities: TRTRTTR. 7 sure positions: TRTRTTR.

63) YYYYYN- 4 possibilities: TRTRTRT, TRTRRTT, TRRTRTT, RTRTRTT. 1 sure position: ------T.

64) YYYYYY- 1 possibilities: TRTRTRT. 7 sure positions: TRTRTRT.

Step 2 - Final adaptive questions (at most 3)

--------------------------------------------

All but one case in the table have at least 1 sure position and at least 1 truth-teller among these positions.

Target that one known truthteller (let's call him Oracle) with the rest of the questions.

First, let's eliminate most of the cases.

If there are 3 or more sure positions, then at most 4 unknowns remain. Therefore 3 questions targeted at the Oracle about 3 unknown positions give a total of 6 sure positions and the last can be deduced by whatever type (R or T) is missing from the (3R, 4T) distribution.

If there are 2 sure positions, then it's one of the following 7 cases:

20) NYNNYY- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT. 2 sure positions: ----TR-.

25) NYYNNN- 4 possibilities: TTRRRTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

27) NYYNYN- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, TTRRRTT. 2 sure positions: -TR----.

41) YNYNNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

45) YNYYNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRTRTT, TRRRTTT, RRTRTTT. 2 sure positions: -----TT.

57) YYYNNN- 5 possibilities: TRTRRTT, TRRRTTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

61) YYYYNN- 6 possibilities: TRTRRTT, TRRTRTT, RTRTRTT, TRRRTTT, RTRRTTT, RRTRTTT. 2 sure positions: -----TT.

For each case, 3 well-targeted questions clear the rest of the arrangement.

20) NYNNYY- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT. 2 sure positions: ----TR-.

Ask oracle if first is R (2 cases).

If first is R, ask if 2 is T (one case each answer).

ElseIf first is T, ask if 4 is R (one case each answer).

25) NYYNNN- 4 possibilities: TTRRRTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

Ask oracle if first is T (1 case).

ElseIf first is R, ask if 2 is T (one case). If 2 is R ask if 3 is T (one case each answer).

27) NYYNYN- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, TTRRRTT. 2 sure positions: -TR----.

Ask oracle if first is R (1 case).

ElseIf first is T, ask if 6 is T (one case). If 6 is R ask if 4 is T (one case each answer).

41) YNYNNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

Ask oracle if first is T (2 cases).

If first is R, ask if 3 is T (one case each answer).

ElseIf first is R, ask if 2 is T (one case). If 2 is T ask if 4 is T (one case each answer).

45) YNYYNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRTRTT, TRRRTTT, RRTRTTT. 2 sure positions: -----TT.

Ask oracle if first is R (2 cases).

If first is R, ask if 2 is T (one case each answer).

ElseIf first is T, ask if 3 is T (one case). If 3 is R ask if 4 is T (one case each answer).

57) YYYNNN- 5 possibilities: TRTRRTT, TRRRTTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

Ask oracle if first is T (2 cases).

If first is T, ask if 3 is T (one case each answer).

ElseIf first is R, ask if 2 is T (one case). If 2 is R ask if 3 is T (one case each answer).

61) YYYYNN- 6 possibilities: TRTRRTT, TRRTRTT, RTRTRTT, TRRRTTT, RTRRTTT, RRTRTTT. 2 sure positions: -----TT.

Ask oracle if first is R (3 cases). If 1 is R, ask if 2 is R (one case). If 2 is T ask if 4 is T (one case each answer).

ElseIf first is T, ask if 3 is T (one case). If 3 is R ask if 4 is T (one case each answer).

If there is only 1 sure position, then it's one of the following 10 cases:

9) NNYNNN- 4 possibilities: TTTRRRT, RTTRRTT, RRTRTTT, RRRTTTT. 1 sure position: ------T.

21) NYNYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RRTTRTT, RTRRTTT. 1 sure position: ------T.

23) NYNYYN- 5 possibilities: TTRTRRT, TTRRTRT, TTRRRTT, RTRTRTT, RRTTRTT. 1 sure position: ------T.

29) NYYYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RTRRTTT, RRTRTTT. 1 sure position: ------T.

37) YNNYNN- 5 possibilities: TRTTRRT, RTTTRRT, TRRTRTT, RRTTRTT, TRRRTTT. 1 sure position: ------T.

43) YNYNYN- 5 possibilities: TRTRTRT, RTTRTRT, TRRTTRT, TRTRRTT, RTTRRTT. 1 sure position: ------T.

47) YNYYYN- 5 possibilities: TRTRTRT, RTTRTRT, TRTRRTT, RTTRRTT, TRRTRTT. 1 sure position: ------T.

53) YYNYNN- 6 possibilities: TRTTRRT, TRRTRTT, RTRTRTT, RRTTRTT, TRRRTTT, RTRRTTT. 1 sure position: ------T.

59) YYYNYN- 4 possibilities: TRTRTRT, TRRTTRT, RTRTTRT, TRTRRTT. 1 sure position: ------T.

63) YYYYYN- 4 possibilities: TRTRTRT, TRTRRTT, TRRTRTT, RTRTRTT. 1 sure position: ------T.

For each case, 3 well-targeted questions clear the rest of the arrangement.

9) NNYNNN- 4 possibilities: TTTRRRT, RTTRRTT, RRTRTTT, RRRTTTT. 1 sure position: ------T.

Ask oracle if first is T (one case).

If first is R, ask if second is T (one case).

If first is R and second is R, ask if third is T (one case each answer).

21) NYNYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RRTTRTT, RTRRTTT. 1 sure position: ------T.

Ask oracle if first is T (2 cases).

If first is T, ask if fourth is T (different in these 2 cases).

ElseIf first is R, ask if second is R (one case). If the second is T ask if fourth is T (one case each answer).

23) NYNYYN- 5 possibilities: TTRTRRT, TTRRTRT, TTRRRTT, RTRTRTT, RRTTRTT. 1 sure position: ------T.

Ask oracle if first is R (2 cases).

If first is R, ask if second is T (different in these 2 cases).

ElseIf first is T, ask if fourth is T (one case). If the fourth is R ask if fifth is T (one case each answer).

29) NYYYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RTRRTTT, RRTRTTT. 1 sure position: ------T.

Ask oracle if first is T (2 cases).

If first is T, ask if 4 is T (one case each answer).

ElseIf first is R, ask if 2 is R (one case). If 2 is T ask if 4 is T (one case each answer).

37) YNNYNN- 5 possibilities: TRTTRRT, RTTTRRT, TRRTRTT, RRTTRTT, TRRRTTT. 1 sure position: ------T.

Ask oracle if first is R (2 cases).

If first is R, ask if 2 is T (one case each answer).

ElseIf first is T, ask if 3 is T (one case). If 3 is R ask if 4 is T (one case each answer).

43) YNYNYN- 5 possibilities: TRTRTRT, RTTRTRT, TRRTTRT, TRTRRTT, RTTRRTT. 1 sure position: ------T.

Ask oracle if first is R (2 cases).

If first is R, ask if 6 is T (one case each answer).

ElseIf first is T, ask if 3 is R (one case). If 3 is T ask if 6 is T (one case each answer).

47) YNYYYN- 5 possibilities: TRTRTRT, RTTRTRT, TRTRRTT, RTTRRTT, TRRTRTT. 1 sure position: ------T.

Ask oracle if first is R (2 cases).

If first is R, ask if 6 is T (one case each answer).

ElseIf first is T, ask if 3 is R (one case). If 3 is T ask if 6 is T (one case each answer).

53) YYNYNN- 6 possibilities: TRTTRRT, TRRTRTT, RTRTRTT, RRTTRTT, TRRRTTT, RTRRTTT. 1 sure position: ------T.

Ask oracle if first is R (3 cases). If 1 is R, ask if 2 is R (one case). If 2 is T ask if 4 is T (one case each answer).

ElseIf first is T, ask if 3 is T (one case). If 3 is R ask if 4 is T (one case each answer).

59) YYYNYN- 4 possibilities: TRTRTRT, TRRTTRT, RTRTTRT, TRTRRTT. 1 sure position: ------T.

Ask oracle if first is R (1 case).

ElseIf first is T, ask if 3 is R (one case). If 3 is T ask if 6 is T (one case each answer).

63) YYYYYN- 4 possibilities: TRTRTRT, TRTRRTT, TRRTRTT, RTRTRTT. 1 sure position: ------T.

Ask oracle if first is R (1 case).

ElseIf first is T, ask if 3 is R (one case). If 3 is T ask if 6 is T (one case each answer).

At last, the infamous branch with 0 sure positions.

19) NYNNYN- 5 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT, TTRRRTT. 0 sure position: -------.

3 more questions and we're done:

Ask the last (7th) in the line if the first one is random.

If Yes - TTRTTRR, RTRTTRT, RRTTTRT. Now the mask is ---TTR-. Ask an Oracle if the last is R (one case). If not, ask if second is R (one case for each answer).

If No - TTRTTRR, TTRRTRT, TTRRRTT. Now the mask is TTR----. Ask an Oracle if the last is R (one case). If not, ask if the sixth is R (one case for each answer).

[bushindo]

My first strategy

In 9 questions.

Step 0 - Assume all liars are truth-tellers using known techniques to construct questions.

-------------------------------------------------------------------------------------------

First of all, the distinction between liars and truthtellers is irrelevant. A well-known technique (when dealing with truthtellers/liars alone) if you want to see if a statement P is true or not is to ask another question instead:

Q:"If I would ask you if P is true would you answer Yes?".

If P is true: a liar answers No to P therefore answering Yes to Q. a truthteller answers Yes to both P and Q.

If P is false: a liar answers Yes to P therefore answering No to Q. a truthteller answers No to both P and Q.

So P is true if and only if you get an Yes answer to Q.

Now assuming all questions are asked like this, we have transformed the problem to a similar problem with 3 randoms and 4 truthtellers. Moving on.

Step 1 - Static 6 questions

---------------------------

Assume all 7 are standing in a line.

I will ask each of the first 6 in line the same question: "Is the person next in the line (to your left/my right) to you a random?". Note that from Step 0, my actual question is "If I would ask you if the person next in the line to you is a random would you answer Yes?" to elicit the same response from truth-tellers and liars.

Note that this question reffers to only 2 people's position and has the following "truth table":

   Yes  No

RR  1   1

RT  1   1

TR  1   0

TT  0   1

where 1 means response is possible and 0 means response is impossible.

A truth-teller followed by a random cannot answer No and a truth-teller followed by a truth-teller cannot answer Yes.

These types of questions targeted at position X can be used to reduce the number of possibilities:

- branch Yes is true for all arrangements with randoms on position X and all arrangements with truth-tellers on X and randoms on X+1

- branch No is true for all arrangements with randoms on position X and all arrangements with truth-tellers on X and truth-tellers on X+1

There are 6 (static/non-adaptive) questions, so 2^6=64 possible combinations of answers.

The following table shows the possible arrangements for each combination and creates a "mask" of known positions: e.g. if only arrangements TRTTTRR and RTTTTRR are possible for a combination of answers then the last 5 positions are sure - written --TTTTRR (where - stands for an unknown).

1) NNNNNN- 1 possibilities: RRRTTTT. 7 sure positions: RRRTTTT.

2) NNNNNY- 1 possibilities: RRTTTTR. 7 sure positions: RRTTTTR.

3) NNNNYN- 2 possibilities: RTTTTRR, RRTTTRT. 5 sure positions: R-TTTR-.

4) NNNNYY- 2 possibilities: RTTTTRR, RRTTTRT. 5 sure positions: R-TTTR-.

5) NNNYNN- 3 possibilities: TTTTRRR, RTTTRRT, RRTTRTT. 3 sure positions: --TTR--.

6) NNNYNY- 3 possibilities: TTTTRRR, RTTTRTR, RTTTRRT. 4 sure positions: -TTTR--.

7) NNNYYN- 3 possibilities: TTTTRRR, RTTTRRT, RRTTRTT. 3 sure positions: --TTR--.

8) NNNYYY- 3 possibilities: TTTTRRR, RTTTRTR, RTTTRRT. 4 sure positions: -TTTR--.

9) NNYNNN- 4 possibilities: TTTRRRT, RTTRRTT, RRTRTTT, RRRTTTT. 1 sure position: ------T.

10) NNYNNY- 3 possibilities: TTTRRTR, RTTRTTR, TTTRRRT. 3 sure positions: -TTR---.

11) NNYNYN- 4 possibilities: TTTRTRR, TTTRRRT, RTTRTRT, RTTRRTT. 3 sure positions: -TTR---.

12) NNYNYY- 4 possibilities: TTTRTRR, TTTRRTR, TTTRRRT, RTTRTRT. 3 sure positions: -TTR---.

13) NNYYNN- 3 possibilities: TTTRRRT, RTTRRTT, RRTRTTT. 3 sure positions: --TR--T.

14) NNYYNY- 3 possibilities: TTTRRTR, RTTRTTR, TTTRRRT. 3 sure positions: -TTR---.

15) NNYYYN- 4 possibilities: TTTRTRR, TTTRRRT, RTTRTRT, RTTRRTT. 3 sure positions: -TTR---.

16) NNYYYY- 4 possibilities: TTTRTRR, TTTRRTR, TTTRRRT, RTTRTRT. 3 sure positions: -TTR---.

17) NYNNNN- 3 possibilities: TTRRRTT, RTRRTTT, RRRTTTT. 3 sure positions: --R--TT.

18) NYNNNY- 3 possibilities: TTRRTTR, RTRTTTR, RRTTTTR. 3 sure positions: ----TTR.

19) NYNNYN- 5 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT, TTRRRTT. 0 sure position: -------.

20) NYNNYY- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT. 2 sure positions: ----TR-.

21) NYNYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RRTTRTT, RTRRTTT. 1 sure position: ------T.

22) NYNYNY- 3 possibilities: TTRTRTR, TTRRTTR, TTRTRRT. 3 sure positions: TTR----.

23) NYNYYN- 5 possibilities: TTRTRRT, TTRRTRT, TTRRRTT, RTRTRTT, RRTTRTT. 1 sure position: ------T.

24) NYNYYY- 3 possibilities: TTRTRTR, TTRTRRT, TTRRTRT. 3 sure positions: TTR----.

25) NYYNNN- 4 possibilities: TTRRRTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

26) NYYNNY- 2 possibilities: TTRRTTR, RTRTTTR. 5 sure positions: -TR-TTR.

27) NYYNYN- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, TTRRRTT. 2 sure positions: -TR----.

28) NYYNYY- 3 possibilities: TTRTTRR, TTRRTRT, RTRTTRT. 4 sure positions: -TR-TR-.

29) NYYYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RTRRTTT, RRTRTTT. 1 sure position: ------T.

30) NYYYNY- 3 possibilities: TTRTRTR, TTRRTTR, TTRTRRT. 3 sure positions: TTR----.

31) NYYYYN- 4 possibilities: TTRTRRT, TTRRTRT, TTRRRTT, RTRTRTT. 3 sure positions: -TR---T.

32) NYYYYY- 3 possibilities: TTRTRTR, TTRTRRT, TTRRTRT. 3 sure positions: TTR----.

33) YNNNNN- 2 possibilities: TRRRTTT, RRRTTTT. 5 sure positions: -RR-TTT.

34) YNNNNY- 2 possibilities: TRRTTTR, RRTTTTR. 5 sure positions: -R-TTTR.

35) YNNNYN- 4 possibilities: TRTTTRR, RTTTTRR, TRRTTRT, RRTTTRT. 3 sure positions: ---TTR-.

36) YNNNYY- 4 possibilities: TRTTTRR, RTTTTRR, TRRTTRT, RRTTTRT. 3 sure positions: ---TTR-.

37) YNNYNN- 5 possibilities: TRTTRRT, RTTTRRT, TRRTRTT, RRTTRTT, TRRRTTT. 1 sure position: ------T.

38) YNNYNY- 4 possibilities: TRTTRTR, RTTTRTR, TRTTRRT, RTTTRRT. 3 sure positions: --TTR--.

39) YNNYYN- 4 possibilities: TRTTRRT, RTTTRRT, TRRTRTT, RRTTRTT. 3 sure positions: ---TR-T.

40) YNNYYY- 4 possibilities: TRTTRTR, RTTTRTR, TRTTRRT, RTTTRRT. 3 sure positions: --TTR--.

41) YNYNNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

42) YNYNNY- 3 possibilities: TRTRTTR, RTTRTTR, TRRTTTR. 3 sure positions: ----TTR.

43) YNYNYN- 5 possibilities: TRTRTRT, RTTRTRT, TRRTTRT, TRTRRTT, RTTRRTT. 1 sure position: ------T.

44) YNYNYY- 3 possibilities: TRTRTRT, RTTRTRT, TRRTTRT. 3 sure positions: ----TRT.

45) YNYYNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRTRTT, TRRRTTT, RRTRTTT. 2 sure positions: -----TT.

46) YNYYNY- 2 possibilities: TRTRTTR, RTTRTTR. 5 sure positions: --TRTTR.

47) YNYYYN- 5 possibilities: TRTRTRT, RTTRTRT, TRTRRTT, RTTRRTT, TRRTRTT. 1 sure position: ------T.

48) YNYYYY- 2 possibilities: TRTRTRT, RTTRTRT. 5 sure positions: --TRTRT.

49) YYNNNN- 3 possibilities: TRRRTTT, RTRRTTT, RRRTTTT. 4 sure positions: --R-TTT.

50) YYNNNY- 3 possibilities: TRRTTTR, RTRTTTR, RRTTTTR. 4 sure positions: ---TTTR.

51) YYNNYN- 4 possibilities: TRTTTRR, TRRTTRT, RTRTTRT, RRTTTRT. 3 sure positions: ---TTR-.

52) YYNNYY- 4 possibilities: TRTTTRR, TRRTTRT, RTRTTRT, RRTTTRT. 3 sure positions: ---TTR-.

53) YYNYNN- 6 possibilities: TRTTRRT, TRRTRTT, RTRTRTT, RRTTRTT, TRRRTTT, RTRRTTT. 1 sure position: ------T.

54) YYNYNY- 2 possibilities: TRTTRTR, TRTTRRT. 5 sure positions: TRTTR--.

55) YYNYYN- 4 possibilities: TRTTRRT, TRRTRTT, RTRTRTT, RRTTRTT. 3 sure positions: ---TR-T.

56) YYNYYY- 2 possibilities: TRTTRTR, TRTTRRT. 5 sure positions: TRTTR--.

57) YYYNNN- 5 possibilities: TRTRRTT, TRRRTTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

58) YYYNNY- 3 possibilities: TRTRTTR, TRRTTTR, RTRTTTR. 3 sure positions: ----TTR.

59) YYYNYN- 4 possibilities: TRTRTRT, TRRTTRT, RTRTTRT, TRTRRTT. 1 sure position: ------T.

60) YYYNYY- 3 possibilities: TRTRTRT, TRRTTRT, RTRTTRT. 3 sure positions: ----TRT.

61) YYYYNN- 6 possibilities: TRTRRTT, TRRTRTT, RTRTRTT, TRRRTTT, RTRRTTT, RRTRTTT. 2 sure positions: -----TT.

62) YYYYNY- 1 possibilities: TRTRTTR. 7 sure positions: TRTRTTR.

63) YYYYYN- 4 possibilities: TRTRTRT, TRTRRTT, TRRTRTT, RTRTRTT. 1 sure position: ------T.

64) YYYYYY- 1 possibilities: TRTRTRT. 7 sure positions: TRTRTRT.

Step 2 - Final adaptive questions (at most 3)

--------------------------------------------

All but one case in the table have at least 1 sure position and at least 1 truth-teller among these positions.

Target that one known truthteller (let's call him Oracle) with the rest of the questions.

First, let's eliminate most of the cases.

If there are 3 or more sure positions, then at most 4 unknowns remain. Therefore 3 questions targeted at the Oracle about 3 unknown positions give a total of 6 sure positions and the last can be deduced by whatever type (R or T) is missing from the (3R, 4T) distribution.

If there are 2 sure positions, then it's one of the following 7 cases:

20) NYNNYY- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT. 2 sure positions: ----TR-.

25) NYYNNN- 4 possibilities: TTRRRTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

27) NYYNYN- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, TTRRRTT. 2 sure positions: -TR----.

41) YNYNNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

45) YNYYNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRTRTT, TRRRTTT, RRTRTTT. 2 sure positions: -----TT.

57) YYYNNN- 5 possibilities: TRTRRTT, TRRRTTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

61) YYYYNN- 6 possibilities: TRTRRTT, TRRTRTT, RTRTRTT, TRRRTTT, RTRRTTT, RRTRTTT. 2 sure positions: -----TT.

For each case, 3 well-targeted questions clear the rest of the arrangement.

20) NYNNYY- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT. 2 sure positions: ----TR-.

Ask oracle if first is R (2 cases).

If first is R, ask if 2 is T (one case each answer).

ElseIf first is T, ask if 4 is R (one case each answer).

25) NYYNNN- 4 possibilities: TTRRRTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

Ask oracle if first is T (1 case).

ElseIf first is R, ask if 2 is T (one case). If 2 is R ask if 3 is T (one case each answer).

27) NYYNYN- 4 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, TTRRRTT. 2 sure positions: -TR----.

Ask oracle if first is R (1 case).

ElseIf first is T, ask if 6 is T (one case). If 6 is R ask if 4 is T (one case each answer).

41) YNYNNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

Ask oracle if first is T (2 cases).

If first is R, ask if 3 is T (one case each answer).

ElseIf first is R, ask if 2 is T (one case). If 2 is T ask if 4 is T (one case each answer).

45) YNYYNN- 5 possibilities: TRTRRTT, RTTRRTT, TRRTRTT, TRRRTTT, RRTRTTT. 2 sure positions: -----TT.

Ask oracle if first is R (2 cases).

If first is R, ask if 2 is T (one case each answer).

ElseIf first is T, ask if 3 is T (one case). If 3 is R ask if 4 is T (one case each answer).

57) YYYNNN- 5 possibilities: TRTRRTT, TRRRTTT, RTRRTTT, RRTRTTT, RRRTTTT. 2 sure positions: -----TT.

Ask oracle if first is T (2 cases).

If first is T, ask if 3 is T (one case each answer).

ElseIf first is R, ask if 2 is T (one case). If 2 is R ask if 3 is T (one case each answer).

61) YYYYNN- 6 possibilities: TRTRRTT, TRRTRTT, RTRTRTT, TRRRTTT, RTRRTTT, RRTRTTT. 2 sure positions: -----TT.

Ask oracle if first is R (3 cases). If 1 is R, ask if 2 is R (one case). If 2 is T ask if 4 is T (one case each answer).

ElseIf first is T, ask if 3 is T (one case). If 3 is R ask if 4 is T (one case each answer).

If there is only 1 sure position, then it's one of the following 10 cases:

9) NNYNNN- 4 possibilities: TTTRRRT, RTTRRTT, RRTRTTT, RRRTTTT. 1 sure position: ------T.

21) NYNYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RRTTRTT, RTRRTTT. 1 sure position: ------T.

23) NYNYYN- 5 possibilities: TTRTRRT, TTRRTRT, TTRRRTT, RTRTRTT, RRTTRTT. 1 sure position: ------T.

29) NYYYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RTRRTTT, RRTRTTT. 1 sure position: ------T.

37) YNNYNN- 5 possibilities: TRTTRRT, RTTTRRT, TRRTRTT, RRTTRTT, TRRRTTT. 1 sure position: ------T.

43) YNYNYN- 5 possibilities: TRTRTRT, RTTRTRT, TRRTTRT, TRTRRTT, RTTRRTT. 1 sure position: ------T.

47) YNYYYN- 5 possibilities: TRTRTRT, RTTRTRT, TRTRRTT, RTTRRTT, TRRTRTT. 1 sure position: ------T.

53) YYNYNN- 6 possibilities: TRTTRRT, TRRTRTT, RTRTRTT, RRTTRTT, TRRRTTT, RTRRTTT. 1 sure position: ------T.

59) YYYNYN- 4 possibilities: TRTRTRT, TRRTTRT, RTRTTRT, TRTRRTT. 1 sure position: ------T.

63) YYYYYN- 4 possibilities: TRTRTRT, TRTRRTT, TRRTRTT, RTRTRTT. 1 sure position: ------T.

For each case, 3 well-targeted questions clear the rest of the arrangement.

9) NNYNNN- 4 possibilities: TTTRRRT, RTTRRTT, RRTRTTT, RRRTTTT. 1 sure position: ------T.

Ask oracle if first is T (one case).

If first is R, ask if second is T (one case).

If first is R and second is R, ask if third is T (one case each answer).

21) NYNYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RRTTRTT, RTRRTTT. 1 sure position: ------T.

Ask oracle if first is T (2 cases).

If first is T, ask if fourth is T (different in these 2 cases).

ElseIf first is R, ask if second is R (one case). If the second is T ask if fourth is T (one case each answer).

23) NYNYYN- 5 possibilities: TTRTRRT, TTRRTRT, TTRRRTT, RTRTRTT, RRTTRTT. 1 sure position: ------T.

Ask oracle if first is R (2 cases).

If first is R, ask if second is T (different in these 2 cases).

ElseIf first is T, ask if fourth is T (one case). If the fourth is R ask if fifth is T (one case each answer).

29) NYYYNN- 5 possibilities: TTRTRRT, TTRRRTT, RTRTRTT, RTRRTTT, RRTRTTT. 1 sure position: ------T.

Ask oracle if first is T (2 cases).

If first is T, ask if 4 is T (one case each answer).

ElseIf first is R, ask if 2 is R (one case). If 2 is T ask if 4 is T (one case each answer).

37) YNNYNN- 5 possibilities: TRTTRRT, RTTTRRT, TRRTRTT, RRTTRTT, TRRRTTT. 1 sure position: ------T.

Ask oracle if first is R (2 cases).

If first is R, ask if 2 is T (one case each answer).

ElseIf first is T, ask if 3 is T (one case). If 3 is R ask if 4 is T (one case each answer).

43) YNYNYN- 5 possibilities: TRTRTRT, RTTRTRT, TRRTTRT, TRTRRTT, RTTRRTT. 1 sure position: ------T.

Ask oracle if first is R (2 cases).

If first is R, ask if 6 is T (one case each answer).

ElseIf first is T, ask if 3 is R (one case). If 3 is T ask if 6 is T (one case each answer).

47) YNYYYN- 5 possibilities: TRTRTRT, RTTRTRT, TRTRRTT, RTTRRTT, TRRTRTT. 1 sure position: ------T.

Ask oracle if first is R (2 cases).

If first is R, ask if 6 is T (one case each answer).

ElseIf first is T, ask if 3 is R (one case). If 3 is T ask if 6 is T (one case each answer).

53) YYNYNN- 6 possibilities: TRTTRRT, TRRTRTT, RTRTRTT, RRTTRTT, TRRRTTT, RTRRTTT. 1 sure position: ------T.

Ask oracle if first is R (3 cases). If 1 is R, ask if 2 is R (one case). If 2 is T ask if 4 is T (one case each answer).

ElseIf first is T, ask if 3 is T (one case). If 3 is R ask if 4 is T (one case each answer).

59) YYYNYN- 4 possibilities: TRTRTRT, TRRTTRT, RTRTTRT, TRTRRTT. 1 sure position: ------T.

Ask oracle if first is R (1 case).

ElseIf first is T, ask if 3 is R (one case). If 3 is T ask if 6 is T (one case each answer).

63) YYYYYN- 4 possibilities: TRTRTRT, TRTRRTT, TRRTRTT, RTRTRTT. 1 sure position: ------T.

Ask oracle if first is R (1 case).

ElseIf first is T, ask if 3 is R (one case). If 3 is T ask if 6 is T (one case each answer).

At last, the infamous branch with 0 sure positions.

19) NYNNYN- 5 possibilities: TTRTTRR, TTRRTRT, RTRTTRT, RRTTTRT, TTRRRTT. 0 sure position: -------.

3 more questions and we're done:

Ask the last (7th) in the line if the first one is random.

If Yes - TTRTTRR, RTRTTRT, RRTTTRT. Now the mask is ---TTR-. Ask an Oracle if the last is R (one case). If not, ask if second is R (one case for each answer).

If No - TTRTTRR, TTRRTRT, TTRRRTT. Now the mask is TTR----. Ask an Oracle if the last is R (one case). If not, ask if the sixth is R (one case for each answer).

Excellent strategy! I didn't realize that it could be done in 9. After reading your post, I re-examined my strategy and realized that there was an inefficient part that essentially wasted 1 question, hence my limit of 10. Great work and thanks for that detailed post. I learned something new today.

Alternative strategy

As araver noted, this problem can simplified by replacing all liars with truth tellers. This does not affect the solution.

Let's say that the 7 people are standing in a line. If we look at the last 3 people, there are 4 possibilities: either there is 0, 1, 2, or 3 random answerers inside this group. Another fact of note is that since there are 4 truth tellers and 3 random answerers, if we ask all 7 the same question, we can get the correct answer by comparing the number of NO's to the number of YES's. For instance, if we get 4 NO and 3 YES to a particular question, we know that the true answer is NO. In fact, if we are asking questions sequentially, we might as well stop when we get 4 YES or 4 NO.

1) Start going from left to right, and ask 1 person at a time, "Are there 0 or 1 random answerers within the last 3 people in this line?".

2) As soon as we get 4 YES or 4 NO, stop asking since we already know the true answer.

3) Once we know the answer to number 1, we can construct a group of of 3 that has more truthtellers than random answerers. For instance, if there are 0 or 1 random answerers within the last 3 people in line, choose those 3. If there are 2 or 3 random answerers in the last 3, choose 3 people from the first 4 in line.

4) We can narrow down a truth teller with 1 question from the group of 3 that has more truthtellers than random answerers (see this )

5) Having identified a truth tellers, we can identify the random answerers using binary search.

Note that in step 2, if we get answers contrary to the majority opinion, those are guaranteed to be random answerers. For instance, we get 4 YES and 1 NO to any question, then the NO must be coming from a random answerer. The cases that requires the most questions are when the first 4 people all answer YES or all NO to part 1). Let's consider the case when the first 4 all answer YES. If that is so, then the last 3 people have 0 or 1 random answerer. We can identify a truth teller from the last 3 with 1 question. That means that there are either 3 random answerers distributed in the first 4 (₄C₃= 4 ) or 2 random answerers distributed in the first 4 and 1 random answerers from the last 3 minus the truth teller (₂C₁ * ₄C₂ = 12 ). Since there are 4+ 12 = 16 states, we can narrow it down in 4 questions using binary search. That makes a total of 4 + 1 + 4 = 9 questions required. The case with 4 NO can be done similarly.

Edited November 25, 2010 by bushindo

[araver]

Did not thought of the majority argument. Seems trivial now

Kudos for the reasoning, smooth indeed.

After giving up my divide-et-impera illusions, I did not want to make such a long strategy ... actually started it thinking it will take 8q most, and ended kinda brute-forcing it with 6 static questions.

I'm still pondering if it's possible to get an adaptive/dynamic strategy that works faster for the first part i.e. balance the tree a little, since it looks too far from an equilibrated tree.

Thanks a lot for the challenge.

[bushindo]

Did not thought of the majority argument. Seems trivial now

Kudos for the reasoning, smooth indeed.

After giving up my divide-et-impera illusions, I did not want to make such a long strategy ... actually started it thinking it will take 8q most, and ended kinda brute-forcing it with 6 static questions.

I'm still pondering if it's possible to get an adaptive/dynamic strategy that works faster for the first part i.e. balance the tree a little, since it looks too far from an equilibrated tree.

Thanks a lot for the challenge.

That's an interesting issue you bring up, I'll have to think about it some. I'm glad you like the puzzle. I greatly enjoy your insights on this puzzle. I have another one that is similar to this but with a twist. However, I'm going on vacation tomorrow and I probably won't be able check this board for the next few days, so I'll post the puzzle next week.

Edited November 25, 2010 by bushindo

[araver]

I realized I haven't told why I expected my first hunch to work. It might be worth something so I'm sharing it.

My hunch was based on a greedy approach on constructing an optimal adaptive strategy (unsuccessful so far).

Looking at "Is the next one random?" types of questions made me realize you can half the truth tellers on that position into two branches (one cannot answer Yes, and the other half cannot answer No).

Looking at the first static questions I could think of I noticed that from 35 combinations after 1Q you can get two branches with 25-combinations (since for any position there are 15 R combinations, 10 T followed by T and 10 T followed by R).

Easier to see in the picture when asking #6Q if next is random. (where 1 stands for can answer, 0 stands for cannot answer)

So 35->(25, 25). But further, I always got less lucky / unbalanced.

E.g. if you split by asking #6 if #7 is Random:

- the No branch has 20T and 5Rs for the last position which you can exploit by again halving the number of truthtellers (going backwards and asking #7 if #6 is Random). You get 2x15-combinations branches (5+20/2)

- the Yes branch does not exhibit the same pattern. The most T's you can get on the same position is 16. (with 9 Rs in the rest of the combinations), so at the most, a same-type of question can only give you 2x17-combination branches (9+16/2).

This inherent non-equilibrium has been puzzling me. (or flummoxing since I learned a new word the other day ) I based my initial calculations on an (inaccurate so far) estimate of the time/questions it takes to reduce it to a very small of combinations.