[Guest]

While hiking through the mountains, you get lost and end up in a village, population 99. You only have 200 USD left. Everyone is greedy, so they will not do anything for free. The majority of the townsfolk are also honest, but some are troublemakers. You need to hire one of the honest citizens as your guide home, which will cost 100 USD. But as the first thing you need to ID one that is honest. For 1 USD, you can ask any villager if another villager is honest. If you ask an honest villager, they tell the truth. If you ask a troublemakers, they might say anything. (The villagers do not understand other kinds of questions.)

Come up with a way to identify an honest person for sure, and with enough money left to get home.

important:

1. the villagers do NOT understand any other questions

2. the troublemakers may lie OR tell the truth

[Guest]

There is no way to be certain given those conditions. The best that can be hoped for is to have a fair chance of being pretty sure, since we are told the majority are honest, so we know over half are honest. So I would choose one villager and ask ten others if that one is honest. If most of them say no, I would say that is a bad start and find another villager to ask another ten about, until I find one that most of the ten say is honest. After finding such a villager, proceed to ask another ten about that same one, and so on but stopping when my money is at 100, and hopefully the majority will agree and I will have found an honest one. That method has no guarantees and works better the more the honest people outnumber the troublemakers.

I can see no other methods that would work. If we knew the exact numbers of troublemakers, or if they always lied, then there might be another way. Or if we could continue asking questions without having to pay another dollar for extra questions, there could be a way then by pairing them off and eliminating pairs when one says the other is not honest and then remixing the pairs up. Any two who say each other are honest must either be both honest or both troublemakers, so by mixing pairs up after each round of questions, the troublemakers would eventually be eliminated and all that is left are the honest ones who outnumber them. But that would cost a lot of money to do.

[superprismatic]

Since the majority of the 99 are honest, then at least 50 of them are honest.

Chose one of the 99 and spend 98 dollars asking each of the other 98 whether

the chosen one is honest. If a group of 50 or more of the 98 all answer the

same way, then each one of that group must be honest as they are in the majority

of the 99. Just hire one of these as your guide. The only other case is that

the ones you asked are split evenly, 49-49, on the question about the chosen

one. In this case, 49 of the 98 asked are honest and 49 are troublemakers.

Since the honest ones are in the majority of all 99, the one you have chosen

to ask about must be honest, so hire him as your guide. Thus you only need to

spend $198 -- $98 for the questions and $100 for the guide.

[Guest]

There is a problem with that solution. Troublemakers can choose to tell the truth. If the split is 49/49 you are correct. If it is 50/48 and the 50 all answered no, you are correct in that case. If it is 50/48 and the 50 all answered yes however, it is possible that 1 of the 50 is a troublemaker, and you should chose the 1 person you asked about instead. If the split is 51/47 or larger and the majority answer yes then you are safe picking the 1 chosen person, but if the majority answer no then you can only be certain that 50 of your majority are honest and anything over 50 might be either honest or troublemaker. That is still decent odds if the majority is only 55 or so, but what if all 98 all answer no? All you really know then is not to pick that 1 person.

Since the majority of the 99 are honest, then at least 50 of them are honest.

Chose one of the 99 and spend 98 dollars asking each of the other 98 whether

the chosen one is honest. If a group of 50 or more of the 98 all answer the

same way, then each one of that group must be honest as they are in the majority

of the 99. Just hire one of these as your guide. The only other case is that

the ones you asked are split evenly, 49-49, on the question about the chosen

one. In this case, 49 of the 98 asked are honest and 49 are troublemakers.

Since the honest ones are in the majority of all 99, the one you have chosen

to ask about must be honest, so hire him as your guide. Thus you only need to

spend $198 -- $98 for the questions and $100 for the guide.

[superprismatic]

There is a problem with that solution. Troublemakers can choose to tell the truth. If the split is 49/49 you are correct. If it is 50/48 and the 50 all answered no, you are correct in that case. If it is 50/48 and the 50 all answered yes however, it is possible that 1 of the 50 is a troublemaker, and you should chose the 1 person you asked about instead. If the split is 51/47 or larger and the majority answer yes then you are safe picking the 1 chosen person, but if the majority answer no then you can only be certain that 50 of your majority are honest and anything over 50 might be either honest or troublemaker. That is still decent odds if the majority is only 55 or so, but what if all 98 all answer no? All you really know then is not to pick that 1 person.

Thanks, it seems that I was a little too quick on the trigger. I was curious as to why I had $2 left over! I expect there is a solution, but ya gotta spend every last dollar.

I'll get back to thinking about it. Thanks again!

[Guest]

I guess I would spend five dollars asking each villager a few times about any given other villager. The one who is consistent about this would therefore be my guide. I don't really know if this is legit, as they could just deliberately lie to my face.

[voider]

There is no way to be certain given those conditions. The best that can be hoped for is to have a fair chance of being pretty sure, since we are told the majority are honest, so we know over half are honest. So I would choose one villager and ask ten others if that one is honest. If most of them say no, I would say that is a bad start and find another villager to ask another ten about, until I find one that most of the ten say is honest. After finding such a villager, proceed to ask another ten about that same one, and so on but stopping when my money is at 100, and hopefully the majority will agree and I will have found an honest one. That method has no guarantees and works better the more the honest people outnumber the troublemakers.

I can see no other methods that would work. If we knew the exact numbers of troublemakers, or if they always lied, then there might be another way. Or if we could continue asking questions without having to pay another dollar for extra questions, there could be a way then by pairing them off and eliminating pairs when one says the other is not honest and then remixing the pairs up. Any two who say each other are honest must either be both honest or both troublemakers, so by mixing pairs up after each round of questions, the troublemakers would eventually be eliminated and all that is left are the honest ones who outnumber them. But that would cost a lot of money to do.

All of your conclusions are wrong or off-track, except the bolded thought.

[voider]

Thanks, it seems that I was a little too quick on the trigger. I was curious as to why I had $2 left over! I expect there is a solution, but ya gotta spend every last dollar.

I'll get back to thinking about it. Thanks again!

I haven't thought about the worst case scenario yet, but in general I think the amount of money left is arbitrary.

[Guest]

Perhaps - And this is but wishful thinking:

If a majority of the villagers speak the truth, how about this:

Ask any two if a third is honest. If they both agree no, or there's an inconsistency eliminate said villager.

This means that (perhaps one third of the time) someone would "pass" the test.

As soon as a band of ten villagers passed (assuming one third of the time they would pass, costing us $60), we would start over.

Those who had passed would now be banded together in groups of 5, and asked if any of the remaining 5 were honest.

That would cost us an extra $25, bringing us to $85. If the majority agreed that one was honest he would pass.

Let's assume this happened every other time (just simple possibility). Now we'd be left with 5 contestants.

Pairing up four of them 2 & 2, asking if the other 3 were honest. This would give us two pairs each demanding 3 dollars each person, a total of $12.

Unless they both agree, one would be kicked out - Again assuming it's half of the time, we're left with either two or three contestants.

We still have three dollars left, so we'll look at the villager whose answers have been consistent with our decision all the way (for the highest possibility]and ask the remaining three if he speaks the truth. If more than one person says he does, we will pick him. If more than one says he does not (we have three judges so only one of the two are possible), we will pick one of those who claims the other does not speak the truth.

This theory is by NO means bulletproof, but it'll probably kick the chances up a bit.

[voider]

This is a nice challenging puzzle.

There must be a way to establish FACTS.

There must be an interrogation system that can be used repeatedly to establish facts.

To find an honest one you must sift out the others, using the 'honest majority' to your advantage. To sift out 49 troublemakers with 100 questions you have to aim to learn 1 fact per 2 questions. (How can you learn 1 fact with 2 questions as in the above spoiler?).

[Guest]

WAIT!

You ask two villagers if the other is lying. It's like the two guardians to hell and heaven.

Scenario:

Is that guy over there lying? No.

Walk over to the other guy.

Is that guy over there lying? No.

So, there's a consistency, ergo none are lying or both are lying - We'll filter them out..

If there's any inconsistency it means that one must at least be a liar, and therefore the one who claimed the other was a liar must be truthful!

Example:

Asking guy 1: "Is he a liar? No."

Asking guy 2: "Is he a liar? Yes."

Inconsistency - Therefore, the one who claimed that the other person was a liar, must be the truthful one, as he told us the truth.

Am I on the right track here?

Edited July 12, 2011 by Artificial

[Guest]

WAIT!

You ask two villagers if the other is lying. It's like the two guardians to hell and heaven.

Scenario:

Is that guy over there lying? No.

Walk over to the other guy.

Is that guy over there lying? No.

So, there's a consistency, ergo none are lying or both are lying - We'll filter them out..

If there's any inconsistency it means that one must at least be a liar, and therefore the one who claimed the other was a liar must be truthful!

Example:

Asking guy 1: "Is he a liar? No."

Asking guy 2: "Is he a liar? Yes."

Inconsistency - Therefore, the one who claimed that the other person was a liar, must be the truthful one, as he told us the truth.

Am I on the right track here?

Except that the liars don't always lie...so it's "Is he a troublemaker?" and the troublemaker could still tell the truth...

[Guest]

Except that the liars don't always lie...so it's "Is he a troublemaker?" and the troublemaker could still tell the truth...

I see your point, but imagine it like this.

If they both claim that the other is a liar, there are three possible outcomes: One speaks the truth and we can't tell who, both lie, or both speak the truth.

The same applies if they claim the other speaks the truth - Consistency therefore equals elimination.

Here's for the inconsistency and their possible scenarios:

A says "Yes", B says "No" when asked "Is your friend a troublemaker?"

We know not yet if A has lied, so there are three outcomes:

B is a liar, which means A tells the truth.

A is a liar, which means B tells the truth, which would create a logical contradiction and a paradox - A lies, so B does not. Therefore, neither does A, and so forth.

Neither lie which means B is a troublemaker.

This means, if A says yes, and B says no, we can assume with certainty that A is truthful.

Let's go for B:

Assuming B is telling us the truth it means A is truthful when he says that B is a troublemaker. Therefore, B is discarded.

Assuming B is lying to us, A would too either be lying or telling the truth, bringing us to the above deduction.

Therefore, with these two scenarios in place, A is truthful regardless of the situation.

I might be missing something, and most likely am, this was just my take on it.

[Guest]

The question we can ask is if another villager is honest. A troublemaker can answer that question truthfully or with a lie, only honest villagers are limited. So if you ask A and B that question, and let's say they are both troublemakers, then they can answer that question in any way they wish. They can both answer yes, both answer no, or one of them can say yes while the other says no. So if you have one yes and one no, you only know that at least one is a troublemaker. If you did happen to know they could not both be troublemakers, then you could say the one who answered no is the honest one.

[Guest]

The question we can ask is if another villager is honest. A troublemaker can answer that question truthfully or with a lie, only honest villagers are limited. So if you ask A and B that question, and let's say they are both troublemakers, then they can answer that question in any way they wish. They can both answer yes, both answer no, or one of them can say yes while the other says no. So if you have one yes and one no, you only know that at least one is a troublemaker. If you did happen to know they could not both be troublemakers, then you could say the one who answered no is the honest one.

I knew there had to be a margin of error somewhere..

Well, it's back to the drawing table for me. Dagnabbit!

[Guest]

Just some thoughts.

If I were a troublemaker, I would want to maximize my chance of earning the $100 guide fee so would try not to be identified. When paired with one other person, I would consider what their answer would be to decide how to respond; I would recognize that a pair with 1 no and 1 yes, positively identifies the one saying yes as a troublemaker; hence, when paired with truth teller, who I know would respond no, I would also respond no. Then when paired with a trouble maker would assume that his thinking would be the same so would respond yes and he would also respond yes. With such responses from 50 pairs, the best that can be determined is a slight statistical advantage by picking one from the yes-yes answering group.

for improving odds, use the scenario on 26 pairs maximum ($52 spent), or until 13 pairs have given yes-yes answers. From these 13 pairs, change partners and ask again ($26). and again with yes-yes answers of 7 pairs(making sure no pair as any previously)($14) and one last time with 4 pairs ($8). Note that every step improves the odds of truth teller-truth teller group. If you have fewer pairs than specified, your odds of truth-teller pair is even better, just saved you some money.But this still does not guarantee success.

[Guest]

In the core basics that would work quite well, however there's one annoying detail that rules out every statistical approach so far - Their free will. I might have read this wrong, but assuming they truly are troublemakers, my way of looking at it was not that they are trying to maximize their own gain (what if no-one tells them they can become a $100 guide) but simply to make us as confused as humanly possible.

If they are in fact aware of the $100 dollars beforehand, your idea would work. However the riddle does not state if they are or are not, and if they are not we're back to square one.

[Guest]

In the core basics that would work quite well, however there's one annoying detail that rules out every statistical approach so far - Their free will. I might have read this wrong, but assuming they truly are troublemakers, my way of looking at it was not that they are trying to maximize their own gain (what if no-one tells them they can become a $100 guide) but simply to make us as confused as humanly possible.

If they are in fact aware of the $100 dollars beforehand, your idea would work. However the riddle does not state if they are or are not, and if they are not we're back to square one.

If we take away the assumption that they would attempt try to fool us, the same scenario works since the other possibility would be yes-no in which case we can be certain the one responding yes is a trouble maker since he claims the other one is a truth teller but would make him a give a false statement. For my technique specified in the additional thought, their is only selecting the ones that are yes-yes responses. If the number is less than those specified, the odds of them being truth tellers increases since the majority are truth tellers. If you felt the number of yes-yes pairs was too small, then using only the no responders of the yes-no pairs could fill out the number of pairs desired.

Edited July 13, 2011 by thoughtfulfellow

[Guest]

If we take away the assumption that they would attempt try to fool us, the same scenario works since the other possibility would be yes-no in which case we can be certain the one responding yes is a trouble maker since he claims the other one is a truth teller but would make him a give a false statement. For my technique specified in the additional thought, their is only selecting the ones that are yes-yes responses. If the number is less than those specified, the odds of them being truth tellers increases since the majority are truth tellers. If you felt the number of yes-yes pairs was too small, then using only the no responders of the yes-no pairs could fill out the number of pairs desired.

Given the one saying yes is the trouble-maker, so must we assume they're both - As if the other one is the truth-teller, and he tells us the "yes" is a truth-teller we'll have a truth contradiction and the liar's paradox.

However, the scenario involves that they can indeed try to fool us, and therefore your solution is not bulletproof. While I understand that it will have a 4 to 1 chance of us ending up with the correct person. we need to expand the idea so that there's no way we could be fooled. If they for example both say yes they could as well both be fooling troublemakers who told us the truth about the opposite. Which means, assuming our initial thirteen pairs all repeat this process, we will end up with twentysix troublemakers, and from there on out there's nothing we can do about it.

I might've misunderstood your initial idea, but this is my take on what I understood.

[Guest]

Below are my findings bruteforcing the 5-person case.

Some notation examples so you understand:

atbtctdter means [a is truthful] [b is truthful] [c is truthful] [d is truthful] [e is random]

AofB=y means, when you ask A whether or not B is truthful, he says "yes".

BofC=n means, when you ask B whether or not C is truthful, he says "no".

CofD=x means, when you ask C whether or not D is truthful, he says either "yes" or "no"

The "(yyyny, yyynn)" type things are the possibilities for the given scenario.

5 villagers (saving a dollar?)

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

atbtctdter

AofB=y

BofC=y

CofD=y

DofE=n

EofA=x

(yyyny,yyynn)

atbtctdret

AofB=y

BofC=y

CofD=n

DofE=x

EofA=y

(yynyy,yynny)

atbtcrdtet

AofB=y

BofC=n

CofD=x

DofE=y

EofA=y

(ynyyy,ynnyy)

atbrctdtet

AofB=n

BofC=x

CofD=y

DofE=y

EofA=y

(nyyyy,nnyyy)

arbtctdtet

AofB=x

BofC=y

CofD=y

DofE=y

EofA=n

(yyyyn,nyyyn)

atbtctdrer

AofB=y

BofC=y

CofD=n

DofE=x

EofA=x

(yynyy,yynnn,yynyn,yynny)

atbtcrdret

AofB=y

BofC=n

CofD=x

DofE=x

EofA=y

(ynyyy,ynnny,ynyny,ynnyy)

atbrcrdtet

AofB=n

BofC=x

CofD=x

DofE=y

EofA=y

(nyyyy,nnnyy,nynyy,nnyyy)

arbrctdtet

AofB=x

BofC=x

CofD=y

DofE=y

EofA=n

(yyyyn,nnyyn,ynyyn,nyyyn)

atbtcrdter

AofB=y

BofC=n

CofD=x

DofE=n

EofA=x

(ynyny,ynnnn,ynynn,ynnny)

atbrctdret

AofB=n

BofC=x

CofD=n

DofE=x

EofA=y

(nynyy,nnnny,nynny,nnnyy)

arbtcrdtet

AofB=x

BofC=n

CofD=x

DofE=y

EofA=n

(ynyyn,nnnyn,ynnyn,nnyyn)

atbrctdter

AofB=n

BofC=x

CofD=y

DofE=n

EofA=x

(nyyny,nnynn,nyynn,nnyny)

arbtctdret

AofB=x

BofC=y

CofD=n

DofE=x

EofA=n

(yynyn,nynnn,yynnn,nynyn)

arbtctdter

AofB=x

BofC=y

CofD=n

DofE=n

EofA=x

(yynny,nynnn,yynnn,nynny)

Results of what truthful people are in common regardless of the scenario:

yyyyn = D/E

yyyny = A/B/C/D

yynyy = A/B/C

ynyyy = A/B/E

nyyyy = A/D/E

yyynn = A/B/C/D

yynny = B/C

ynnyy = A/B/E

nnyyy = A/D/E

yynyn = B/C

ynyny = A/B

nynyy = A/E

ynyyn = D/E

nyyny = A/C/D

nyyyn = D/E

yynnn = B/C

ynnny = A/B

nynyn = B/C/E

nnyny = A/D/E

nynny = A/C

ynynn = A/B/D

ynnyn = B/D/E

nnnyy = A/E

ynnnn = A/B/E

nnnny = A/C/E

Pattern discovered:

(Reading left to right.) The "n" preceded by the most y's is always a truthful person (including wraparound).

What I mean by that:

yyyyn... The last n (E) is preceded by 4 y's. There are no other n's anyways.

nnnny... The first n (A) is preceded by the last y. All the other n's are preceded by n's.

ynnyn... (If there's a tie)... the first n (B) is preceded by 1 y. The last n (E) is preceded by 1 y. Then they are both acceptable choices / both truthful people, as is reflected by the fact that they are both listed.

My solution for 99 people would be to ask 99 questions, having AofB,BofC,DofE,EofF,FofG,etc...98of99,99ofA.

You would get a list of 99 y's and n's. Find the largest number of y's, including wraparound, and select the "n" after them. This is your truthful person.

I haven't tested the 99-person case though. Maybe the pattern changes... but I don't think it does.

[Guest]

Below are my findings bruteforcing the 5-person case.

Some notation examples so you understand:

atbtctdter means [a is truthful] [b is truthful] [c is truthful] [d is truthful] [e is random]

AofB=y means, when you ask A whether or not B is truthful, he says "yes".

BofC=n means, when you ask B whether or not C is truthful, he says "no".

CofD=x means, when you ask C whether or not D is truthful, he says either "yes" or "no"

The "(yyyny, yyynn)" type things are the possibilities for the given scenario.

5 villagers (saving a dollar?)

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

atbtctdter

AofB=y

BofC=y

CofD=y

DofE=n

EofA=x

(yyyny,yyynn)

atbtctdret

AofB=y

BofC=y

CofD=n

DofE=x

EofA=y

(yynyy,yynny)

atbtcrdtet

AofB=y

BofC=n

CofD=x

DofE=y

EofA=y

(ynyyy,ynnyy)

atbrctdtet

AofB=n

BofC=x

CofD=y

DofE=y

EofA=y

(nyyyy,nnyyy)

arbtctdtet

AofB=x

BofC=y

CofD=y

DofE=y

EofA=n

(yyyyn,nyyyn)

atbtctdrer

AofB=y

BofC=y

CofD=n

DofE=x

EofA=x

(yynyy,yynnn,yynyn,yynny)

atbtcrdret

AofB=y

BofC=n

CofD=x

DofE=x

EofA=y

(ynyyy,ynnny,ynyny,ynnyy)

atbrcrdtet

AofB=n

BofC=x

CofD=x

DofE=y

EofA=y

(nyyyy,nnnyy,nynyy,nnyyy)

arbrctdtet

AofB=x

BofC=x

CofD=y

DofE=y

EofA=n

(yyyyn,nnyyn,ynyyn,nyyyn)

atbtcrdter

AofB=y

BofC=n

CofD=x

DofE=n

EofA=x

(ynyny,ynnnn,ynynn,ynnny)

atbrctdret

AofB=n

BofC=x

CofD=n

DofE=x

EofA=y

(nynyy,nnnny,nynny,nnnyy)

arbtcrdtet

AofB=x

BofC=n

CofD=x

DofE=y

EofA=n

(ynyyn,nnnyn,ynnyn,nnyyn)

atbrctdter

AofB=n

BofC=x

CofD=y

DofE=n

EofA=x

(nyyny,nnynn,nyynn,nnyny)

arbtctdret

AofB=x

BofC=y

CofD=n

DofE=x

EofA=n

(yynyn,nynnn,yynnn,nynyn)

arbtctdter

AofB=x

BofC=y

CofD=n

DofE=n

EofA=x

(yynny,nynnn,yynnn,nynny)

Results of what truthful people are in common regardless of the scenario:

yyyyn = D/E

yyyny = A/B/C/D

yynyy = A/B/C

ynyyy = A/B/E

nyyyy = A/D/E

yyynn = A/B/C/D

yynny = B/C

ynnyy = A/B/E

nnyyy = A/D/E

yynyn = B/C

ynyny = A/B

nynyy = A/E

ynyyn = D/E

nyyny = A/C/D

nyyyn = D/E

yynnn = B/C

ynnny = A/B

nynyn = B/C/E

nnyny = A/D/E

nynny = A/C

ynynn = A/B/D

ynnyn = B/D/E

nnnyy = A/E

ynnnn = A/B/E

nnnny = A/C/E

Pattern discovered:

(Reading left to right.) The "n" preceded by the most y's is always a truthful person (including wraparound).

What I mean by that:

yyyyn... The last n (E) is preceded by 4 y's. There are no other n's anyways.

nnnny... The first n (A) is preceded by the last y. All the other n's are preceded by n's.

ynnyn... (If there's a tie)... the first n (B) is preceded by 1 y. The last n (E) is preceded by 1 y. Then they are both acceptable choices / both truthful people, as is reflected by the fact that they are both listed.

My solution for 99 people would be to ask 99 questions, having AofB,BofC,DofE,EofF,FofG,etc...98of99,99ofA.

You would get a list of 99 y's and n's. Find the largest number of y's, including wraparound, and select the "n" after them. This is your truthful person.

I haven't tested the 99-person case though. Maybe the pattern changes... but I don't think it does.

I do not at all see a problem with that solution IF we assume that the troublemakers WILL answer at random - The problem is that the original problem does not quite state if these villagers are intelligent enough to consistently provide one answer, or even communicate in between. Given they do neither, the solution above should work fine for 99 people as well, it'd just be a load of more work of course, and the expense would likely exceed the $100 permitted. The thing is, that these villagers might be able to deliberately provide one answer regardless of the times asked, depending on the perception of the original problem. I see absolutely no way to be completely certain if the troublemakers may communicate in between, or even worse - are intelligent.

[superprismatic]

Below are my findings bruteforcing the 5-person case.

Some notation examples so you understand:

atbtctdter means [a is truthful] [b is truthful] [c is truthful] [d is truthful] [e is random]

AofB=y means, when you ask A whether or not B is truthful, he says "yes".

BofC=n means, when you ask B whether or not C is truthful, he says "no".

CofD=x means, when you ask C whether or not D is truthful, he says either "yes" or "no"

The "(yyyny, yyynn)" type things are the possibilities for the given scenario.

5 villagers (saving a dollar?)

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

atbtctdter

AofB=y

BofC=y

CofD=y

DofE=n

EofA=x

(yyyny,yyynn)

atbtctdret

AofB=y

BofC=y

CofD=n

DofE=x

EofA=y

(yynyy,yynny)

atbtcrdtet

AofB=y

BofC=n

CofD=x

DofE=y

EofA=y

(ynyyy,ynnyy)

atbrctdtet

AofB=n

BofC=x

CofD=y

DofE=y

EofA=y

(nyyyy,nnyyy)

arbtctdtet

AofB=x

BofC=y

CofD=y

DofE=y

EofA=n

(yyyyn,nyyyn)

atbtctdrer

AofB=y

BofC=y

CofD=n

DofE=x

EofA=x

(yynyy,yynnn,yynyn,yynny)

atbtcrdret

AofB=y

BofC=n

CofD=x

DofE=x

EofA=y

(ynyyy,ynnny,ynyny,ynnyy)

atbrcrdtet

AofB=n

BofC=x

CofD=x

DofE=y

EofA=y

(nyyyy,nnnyy,nynyy,nnyyy)

arbrctdtet

AofB=x

BofC=x

CofD=y

DofE=y

EofA=n

(yyyyn,nnyyn,ynyyn,nyyyn)

atbtcrdter

AofB=y

BofC=n

CofD=x

DofE=n

EofA=x

(ynyny,ynnnn,ynynn,ynnny)

atbrctdret

AofB=n

BofC=x

CofD=n

DofE=x

EofA=y

(nynyy,nnnny,nynny,nnnyy)

arbtcrdtet

AofB=x

BofC=n

CofD=x

DofE=y

EofA=n

(ynyyn,nnnyn,ynnyn,nnyyn)

atbrctdter

AofB=n

BofC=x

CofD=y

DofE=n

EofA=x

(nyyny,nnynn,nyynn,nnyny)

arbtctdret

AofB=x

BofC=y

CofD=n

DofE=x

EofA=n

(yynyn,nynnn,yynnn,nynyn)

arbtctdter

AofB=x

BofC=y

CofD=n

DofE=n

EofA=x

(yynny,nynnn,yynnn,nynny)

Results of what truthful people are in common regardless of the scenario:

yyyyn = D/E

yyyny = A/B/C/D

yynyy = A/B/C

ynyyy = A/B/E

nyyyy = A/D/E

yyynn = A/B/C/D

yynny = B/C

ynnyy = A/B/E

nnyyy = A/D/E

yynyn = B/C

ynyny = A/B

nynyy = A/E

ynyyn = D/E

nyyny = A/C/D

nyyyn = D/E

yynnn = B/C

ynnny = A/B

nynyn = B/C/E

nnyny = A/D/E

nynny = A/C

ynynn = A/B/D

ynnyn = B/D/E

nnnyy = A/E

ynnnn = A/B/E

nnnny = A/C/E

Pattern discovered:

(Reading left to right.) The "n" preceded by the most y's is always a truthful person (including wraparound).

What I mean by that:

yyyyn... The last n (E) is preceded by 4 y's. There are no other n's anyways.

nnnny... The first n (A) is preceded by the last y. All the other n's are preceded by n's.

ynnyn... (If there's a tie)... the first n (B) is preceded by 1 y. The last n (E) is preceded by 1 y. Then they are both acceptable choices / both truthful people, as is reflected by the fact that they are both listed.

My solution for 99 people would be to ask 99 questions, having AofB,BofC,DofE,EofF,FofG,etc...98of99,99ofA.

You would get a list of 99 y's and n's. Find the largest number of y's, including wraparound, and select the "n" after them. This is your truthful person.

I haven't tested the 99-person case though. Maybe the pattern changes... but I don't think it does.

I don't understand what that last table says. I'm talking about the one whose first line is yyyyn = D/E. Please explain.

[Guest]

Hint: simplify the bigger case to a smaller one and work from there. For example, start with 3 villagers and use the fact that the majority is honest (2 people are honest) to find out one honest person for sure.

Hint*: you don't need to find out the identities of all 3 people, just find out 1 honest one for sure.

Hint**: you can find 1 honest person among 3 people with just $1

Hint***: once you find out about the base case of 3 people, you can move on to 5, in which you will be using the procedure you found out with 3 people. and you move on to 7, so mathematical induction here can be useful.

[Guest]

I don't understand what that last table says. I'm talking about the one whose first line is yyyyn = D/E. Please explain.

It means, for all cases that have the possibility of coming out as yyyyn, both D and E are truthful.

Edited July 13, 2011 by ihavenoidea

[Guest]

For 3 people it is simple. It gets harder with 5 if this is the right track. I almost had 5 with 2 dollars until the very end.

Case of 3 people, 2 honest, 1 dollar.

Ask person 1 if 2 is honest. If answer is no, then 3 is known honest since 1 or 2 is troublemaker. If answer is yes, then 2 is honest since 1 is either honest too or is the only troublemaker.

Case of 5 people, 3 honest, 3 dollars

Ask 1 if 2 is honest. If 1 says no then

Ask 3 if 4 is honest.

If 3 says no, both groups have troublemakers, 5 must be honest.

If 3 says yes, then

case of 1 and 2 are troublemakers, honest are 3,4,5

case of 1 is troublemaker, other troublemaker must be 3 or 5. 4 is safe bet.

If 1 said yes, then ask 3 if 2 is honest.

If 3 says yes,

case of 3 and 1 troublemaker, 2 is honest

case of 3 honest and 1 troublemaker, 2 is honest

case of 3 troublemaker and 1 honest, 2 is honest

case of 3 and 1 honest, 2 is honest.

If 3 says no, then 1,2,3 have at least 1 troublemaker

ask 4 if 5 is honest.

if yes then 5 must be honest

if no, one of them is troublemaker and only 1 of 1,2,3 is troublemaker, so 2 must be honest

[Guest]

OP's hints were very potent.

3-person case

---

2 truthful, 1 random

I ask A about B. A says "yes"

There is only one random.

If A is random, B is truthful (we pick B)

B can't be random, because if he were, A would be truthful, and he wouldn't say that B is truthful.

OR

I ask A about B. A says "no"

Either A is random, and he's giving us a random answer about B.

or

B is random, and A is pointing out that he is.

In either case, we pick C, because he couldn't have caused the "no".

(Victory)

---

5-person case

-----

3 truthful, 2 random

I ask A about B. A says "no"

Well now there's 2 possible randoms. We have for sure eliminated one of the randoms though. Scrap A and B and move on, as one of them caused the "no".

I ask C about D. C says "no". We have eliminated both randoms in this case and pick E.

--

I ask A about B. A says "no" (scrap A and B)

I ask C about D. C says "yes". Well we know A or B is the first random, so there's only one random between C,D, and E. It should be clear that this makes it identical to the 3-person case.

--

I ask A about B. A says "yes"

Move on so that you force yourself to bump into one of the randoms.

I ask C about D. C says "no" (Scrap C and D)

There's one random between A,B, and E again.

(Victory)

---

Questions required vs people is 2Q+1=P

We want to know how many questions or dollars you need for 99 people

99=2Q+1

98=2Q

49=Q

We need 49 dollars.

Cool puzzle / hint definitely gives it away though =(