How to find 1 honest villager out of 99 with $100?

[hahaputao]

While hiking through the mountains, you get lost and end up in a village, population 99. You only have $200 left. Everyone is greedy, so they won't 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. But first you need to nd one that is honest. For $1, 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 don't understand other kinds of questions.)

Come up with a way to nd an honest villager 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

Edited July 11, 2011 by hahaputao

[uncool]

While hiking through the mountains, you get lost and end up in a village, population 99. You only have $200 left. Everyone is greedy, so they won't 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. But first you need to nd one that is honest. For $1, 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 don't understand other kinds of questions.)

Come up with a way to nd an honest villager 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

So it is a given that at least 51 of the villagers are honest?

=Uncool-

[md65536]

At most 49 / 99 are troublemakers.

 

 

 

Ask any 50 a question and you'll get at least one honest person answering.

Also, ask about any 50 and you'll be asking about at least one honest person.

 

 

 

If you ask 49 people about 49 others, and you get all "no" answers, you know that each person asked is either an honest person talking about a troublemaker, or a troublemaker answering the question. Regardless, you know that all 49 possible troublemakers are involved and you can safely assume the 99th person that you haven't involved is honest.

 

Otherwise (if you get at least one 'yes'), take all the people whom you were told were honest, and ignore all the rest (the question answerers and the 'no's and the one you'd ignored).

You've now spent 49 dollars and have 51 to spend, and you have a group of at most 49 people who may be honest or troublemakers.

Also, for every one of this group that is a troublemaker, they got into this group because another troublemaker lied and said they were honest. At most, you could have 24 troublemakers getting 24 other troublemakers into a group of 49.

That means you can assume that this group is mostly honest.

 

You're in a similar situation to what you started with. So repeat the process until you get all "no" answers, and take the one who was ignored, or until you get a group of one (who will be honest).

 

(I guess I left out some details but if you have an even group, you'll get at least one "yes".)

 

 

Edited July 23, 2011 by md65536