[bushindo]

You are an explorer traveling in the Amazon rain forest. You need to explore a particularly dangerous region of the forest, so you drop by a local village of Tourguidians to hire a native as an expedition guide. The Tourguidians are the best guides to the Amazon forest. However, they are divided into 2 sub-groups: the truth tellers and the random speakers. The truth tellers will always respond to questions with the truth, while the random speakers will randomly tell the truth or lie to any question.

There are 11 Tourguidians in this particular village, 6 of whom are truth tellers, and 5 are random speakers. You don't know which person belongs to which group. You would like to find a truth teller and hire him for obvious reasons ("Umm, is this herb poisonous, Mr. Tour Guide?"). However, you are only allowed to address a total of 10 questions to the villagers. Each question may be addressed to any 1 of the 11 villagers. The restrictions are that they be Yes/No questions, and that you can not ask any question which is impossible for a truth teller to answer with a yes/no (ie. asking a truth teller what a random answerer would say to a particular question, asking paradoxes, etc. )

Devise a strategy that is guaranteed to identify a truth teller in the 11 villagers using only 10 questions. Assume that each villager know the identity/persona of his fellow villagers.

Edited April 15, 2011 by bushindo

[Peekay]

I ask person A the following question:

"If I were to ask you whether Person B is a 'Truthteller', would you say Yes?"

If A is a TT and B is a TT: Answer Yes

If A is a RS and B is a TT: Answer Yes

If A is a TT and B is a RS: Answer No

If A is a RS and B is a RS: Answer No

So, is the answer is Yes, you choose B.

If you are unlucky, you may have to repeat this for maximum six times to get your man.

[Guest]

In the lines where speaker A is a random sayer, he is just as likely to lie to you as to say the truth, so you get a set of 6 possibilities, not 4 and it would not be clear cut.

I ask person A the following question:

"If I were to ask you whether Person B is a 'Truthteller', would you say Yes?"

If A is a TT and B is a TT: Answer Yes

If A is a RS and B is a TT: Answer Yes

If A is a TT and B is a RS: Answer No

If A is a RS and B is a RS: Answer No

So, is the answer is Yes, you choose B.

If you are unlucky, you may have to repeat this for maximum six times to get your man.

[bushindo]

I ask person A the following question:

"If I were to ask you whether Person B is a 'Truthteller', would you say Yes?"

If A is a TT and B is a TT: Answer Yes

If A is a RS and B is a TT: Answer Yes

If A is a TT and B is a RS: Answer No

If A is a RS and B is a RS: Answer No

So, is the answer is Yes, you choose B.

If you are unlucky, you may have to repeat this for maximum six times to get your man.

Ah, I see I was sloppy in phrasing this problem. By random speakers, I mean that these people randomly answer Yes or No to any question. That should bring the puzzle back along the intended line.

Edited April 15, 2011 by bushindo

[k-man]

I haven't verified that this solution works in all cases, but here are my thoughts...

With 11 Tourguidians standing in line address the same question to the first 10 people going down the line: Is the next person in line a truth teller? So, the person #1 will speak about the person #2. The person #2 will speak about the person #3 and so on. Based on the answers and knowing that there are 6 truth tellers and 5 random speakers we can narrow down to one or few possible arrangements from which we (hopefully) can find one truth teller. Again, I haven't completed the exhaustive analysis of all scenarios, but looking at some it seems to work.

For example, if all the answers are Yes, then the only possible arrangement is people 1-5 are RS and 6-11 are TT.

If all the answers are No, then odd numbers are TT and even numbers are RS.

For any other set of Yes/No answers we can build a logical tree starting from the last person and working backwards in the following manner. The last person could be either TT or RS. First assume that the last person is TT. Then if the last answer was No, then the previous person must be RS. If the answer was Yes, then the previous person could be either TT or RS. Assume he's TT. Continue in the same manner until you get either

1) a valid arrangment

2) too many TTs

3) too many RSs

Then wherever you assumed TT try with RS. From the set of valid arrangements find the person that is TT in all of them.

For example, if the answers are YNYNYNYNYN the following arrangements are possible:

.1 Y.....TT TT TT TT TT

.2 N.....TT TT TT TT TT

.3 Y.....RS RS RS RS RS

.4 N.....TT RS RS RS TT

.5 Y.....RS TT TT TT RS

.6 N.....RS TT TT TT RS

.7 Y.....TT RS RS RS TT

.8 N.....TT RS TT TT TT

.9 Y.....RS TT RS RS RS

10 N.....RS TT TT TT TT

11 ......TT RS RS RS RS

In all the above arrangements the first 2 people are TT, so pick one of them.

Edit: formatting

Edited April 18, 2011 by k-man

[k-man]

I wrote a little program to validate my solution and it works in all 1024 possible combinations of Yes/No answers. Amazingly enough, every combination of Yes/No answers produces at least one valid arrangement of people. And, in cases when multiple arrangements are possible, there is always at least one Truth Teller that can be identified.

[bushindo]

I wrote a little program to validate my solution and it works in all 1024 possible combinations of Yes/No answers. Amazingly enough, every combination of Yes/No answers produces at least one valid arrangement of people. And, in cases when multiple arrangements are possible, there is always at least one Truth Teller that can be identified.

Great work, k-man. The exhaustive proof is a very nice bonus. This board never fails to amaze me =)

[superprismatic]

I wrote a little program to validate my solution and it works in all 1024 possible combinations of Yes/No answers. Amazingly enough, every combination of Yes/No answers produces at least one valid arrangement of people. And, in cases when multiple arrangements are possible, there is always at least one Truth Teller that can be identified.

What about the answer sequence YNYYNYNNNN?

There are 10 arrangements (T=Truth Teller, R=Random Speaker) which give this answer:

TTRTTRTRTRR

TTRTTRTRRTR

TTRTTRRTRTR

TTRTTRTRRRT

TTRTTRRTRRT

TTRTTRRRTRT

RTRTTRTRTRT

TTRRTRTRTRT

RRTTTRTRTRT

TTRRRTTRTRT

So, a Truth Teller cannot be identified here.

Am I missing something?

[k-man]

What about the answer sequence YNYYNYNNNN?

There are 10 arrangements (T=Truth Teller, R=Random Speaker) which give this answer:

TTRTTRTRTRR

TTRTTRTRRTR

TTRTTRRTRTR

TTRTTRTRRRT

TTRTTRRTRRT

TTRTTRRRTRT

RTRTTRTRTRT

TTRRTRTRTRT

RRTTTRTRTRT

TTRRRTTRTRT

So, a Truth Teller cannot be identified here.

Am I missing something?

You're right. I found a bug in my program (it's been a while since I wrote anything myself) where it was verifying the results. Now I see that there are 123 sets of answers that produce multiple arrangements with no way to identify a truth teller.

Bushindo, is this the same answer you had in mind?

[bushindo]

You're right. I found a bug in my program (it's been a while since I wrote anything myself) where it was verifying the results. Now I see that there are 123 sets of answers that produce multiple arrangements with no way to identify a truth teller.

Bushindo, is this the same answer you had in mind?

Apparently you and I both had bugs in our codes. My bug has no other explanation besides a sloppiness on my part. Mea culpa.

What about the answer sequence YNYYNYNNNN?

There are 10 arrangements (T=Truth Teller, R=Random Speaker) which give this answer:

TTRTTRTRTRR

TTRTTRTRRTR

TTRTTRRTRTR

TTRTTRTRRRT

TTRTTRRTRRT

TTRTTRRRTRT

RTRTTRTRTRT

TTRRTRTRTRT

RRTTTRTRTRT

TTRRRTTRTRT

So, a Truth Teller cannot be identified here.

Am I missing something?

This board never fails to amaze me. Good work, superprismatic.

[k-man]

But if you change the OP slightly to say that there are 7 truth tellers and 4 random speakers (instead of 6 and 5) then the solution works! (unless of course my program still has bugs )

I got 912 sets of answers with an identifiable truth teller and 112 sets of answers with no possible arrangements.

Edit: grammar

Edited April 18, 2011 by k-man

[superprismatic]

But if you change the OP slightly to say that there are 7 truth tellers and 4 random speakers (instead of 6 and 5) then the solution works! (unless of course my program still has bugs )

I got 912 sets of answers with an identifiable truth teller and 112 sets of answers with no possible arrangements.

Edit: grammar

I just checked this with my program. I get the same results. Thus, k-man has successfully repaired a nice little problem!