Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

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 by araver, 24 November 2010 - 11:05 PM.

0

Summer of 2014: Show the Mafia world you're back in action ... signup for Justice League Unleashed (Again) - Second Arc: Of Magic and Men. Come join the madness!

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?

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.

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.

0

Summer of 2014: Show the Mafia world you're back in action ... signup for Justice League Unleashed (Again) - Second Arc: Of Magic and Men. Come join the madness!

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).

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.

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

Spoiler for 2-sure

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).

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

Spoiler for 1-sure

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).

0

Summer of 2014: Show the Mafia world you're back in action ... signup for Justice League Unleashed (Again) - Second Arc: Of Magic and Men. Come join the madness!

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).

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.

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

Spoiler for 2-sure

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).

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

Spoiler for 1-sure

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

Spoiler for

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 puzzle) 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 (_{4}C_{3}= 4 ) or 2 random answerers distributed in the first 4 and 1 random answerers from the last 3 minus the truth teller (_{2}C_{1} * _{4}C_{2} = 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.

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.

0

Summer of 2014: Show the Mafia world you're back in action ... signup for Justice League Unleashed (Again) - Second Arc: Of Magic and Men. Come join the madness!

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.

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

Spoiler for

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)

Spoiler for Warning-large size picture

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.

0

Summer of 2014: Show the Mafia world you're back in action ... signup for Justice League Unleashed (Again) - Second Arc: Of Magic and Men. Come join the madness!