[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]

In your last example, where A says yes, you did not address the case of C says yes. It seams to me in that case, that the 2 randoms could be AB, CD, AE, or CE. So nobody has a known identity. I also do not see how you go from 3 or 5 people to the general form for any number of people, so maybe an explanation would be nice?

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 =(

[Guest]

In your last example, where A says yes, you did not address the case of C says yes. It seams to me in that case, that the 2 randoms could be AB, CD, AE, or CE. So nobody has a known identity. I also do not see how you go from 3 or 5 people to the general form for any number of people, so maybe an explanation would be nice?

You're right. I overlooked that entirely x_x. I guess you need 3 questions for 5,

and we should especially be looking for if they keep saying "yes" as the cases go on, as it'll be the most question-demanding.

But yeah I need to go revisit this now. I think I'm going to wait a while to be really sure of what I post this time. Thanks for pointing that out.

[Guest]

: For 5people, you can actually do this:

If you get A says "yes" about B,

Ask B about C. If you get another "yes", these are the possibilities with 2 randoms:

atbtctdrer (d,e random)

arbrctdtet (a,b random)

arbtctdret (a,d random)

arbtctdter (a,e random)

I'm fairly certain C has to be truthful.

Let's TRY to make him random, to better illustrate...

If C is random, B HAS to be random, because a truthful person wouldn't lie.

If B is random, A HAS to be random, because a truthful person wouldn't lie.

This would make 3 randoms... a majority... which is impossible.

I think this basically gives you the formula to solve it for these worst cases with a bunch of yeses.

When you get a "yes", you start making a chain of interconnected people that makes them all depend on eachother.

I think this works such that 2*(questions) + 1 = people, but I've been wrong many times in this thread. It could very well have happened again. Continue with the feedback while I try 7 people.

Edited July 14, 2011 by ihavenoidea

[Guest]

I tried a similar approach and failed. In this case the problem is what happens when b says No about c. Take case of c is honest, a and b are free to be both honest or troublemakers, nothing known. If c is troublemaker, then a and b can both be honest. In both cases a and b can be mixed as well. So it still takes 1 more question, this time in response to the no rather than to a yes.But even 3 questions is not bad, as long as questions is always less than number of people. I am just too tired today to try for 7 people, but I would probably take your prior approach (ab, then cd) for that since it is simpler than this imo and more likely to point to a general solution. But without trying, who knows which is better?

: For 5people, you can actually do this:

If you get A says "yes" about B,

Ask B about C. If you get another "yes", these are the possibilities with 2 randoms:

atbtctdrer (d,e random)

arbrctdtet (a,b random)

arbtctdret (a,d random)

arbtctdter (a,e random)

I'm fairly certain C has to be truthful.

Let's TRY to make him random, to better illustrate...

If C is random, B HAS to be random, because a truthful person wouldn't lie.

If B is random, A HAS to be random, because a truthful person wouldn't lie.

This would make 3 randoms... a majority... which is impossible.

I think this basically gives you the formula to solve it for these worst cases with a bunch of yeses.

When you get a "yes", you start making a chain of interconnected people that makes them all depend on eachother.

I think this works such that 2*(questions) + 1 = people, but I've been wrong many times in this thread. It could very well have happened again. Continue with the feedback while I try 7 people.

[Guest]

It is not all that ugly really, and I see a pattern forming.

7 people, 4 honest, 3 troublemakers, 4 dollars

pair as this

ab

cd

ef

with g left over

Ask first member of each pair if 2nd member is honest.

In case answers are:

3 no, all 3 pairs have troublemakers, honest is g. 3 dollars

2 no, 2 no pairs have troublemakers. Take the pair that answered yes.

Ask g if one of them is honest. if g says no, the other pair member is honest. if g says yes, the one you asked about is honest. 4 dollars.

1 no, that pair has troublemaker. Remaining 5 has 1 or 2 troublemakers.

call these cd, ef, and g. cd and ef already have yes answers. If there is just one troublemaker, it must be c,e, or g. if there are 2, it could be cd, ef, ce, cg, or eg. Pick 3, d,f,g. Only 1 can be troublemaker. ask df. if no, then g is honest, if yes then f is honest. 4 dollars.

3 yes

troublemakers can be

g and any pair

any pair and first member of another pair

first members of any 3 pairs or of 2 pairs and g

troublemakers can not be from 2nd member of more than 1 pair.

so group 2nd members of pairs thus

bdf. That can only have 1 troublemaker. ask bd, if yes then d is honest, if no then f is honest. 4 dollars.

Edited July 14, 2011 by Nana7

[plainglazed]

Kept trying to reduce the number of possibilities by eliminating any pairs that gave a response of "no" as, at best, one of the two in a "no" response could be a truthteller thus within those remaining, the truthtellers would still hold a majority. But there's no guarantee you will get a "no" response in before you run out of money. Think this statement is the key -

3 yes

troublemakers can be

g and any pair

any pair and first member of another pair

first members of any 3 pairs or of 2 pairs and g

troublemakers can not be from 2nd member of more than 1 pair.

so group 2nd members of pairs thus

bdf. That can only have 1 troublemaker. ask bd, if yes then d is honest, if no then f is honest. 4 dollars.

For the general case it is not a stretch that the above quote in red could also read, "troublemakers can not be a majority of the 2nd members of each pair after eliminating any pairs that have responded "no". Eliminating pairs responding "no" either drops a troublemaker and a truthteller or drops two troublemakers. In both cases this just further promotes the truthtellers as the majority. So with 99 villagers, after 49 questions, consider the worst case where all respond "yes". As Nana7 did, let's collectively call those asking if another is a truthteller the 1st members and those being inquired about the 2nd members. There is obviously a maximum of 49 troublemakers in the 1st members. But in this case, the corresponding members of the second group all must be truthtellers (a clear cut majority which is what we want to prove). Each truthteller swapped with a troublemaker of the 49 1st members puts a corresponding truthteller in the group of second members thus maintaing a majority of truthtellers in that group. When the group of 1st members consists of 24 truthtellers (or more) and 25 troublemakers, the group of 49 2nd members consists of at most 24 troublemakers. So the group of 49 second members always has a majority of truthtellers irregardless of the 99th villager. We can now take the group of 49 second members with an established majority of truthtellers and repeat the process. For less than $100 we can establish a truthteller.

A most excellent puzzle hahaputao!

[Guest]

I hate to be a Debbie Downer, but aren't we again ignoring the fact that these people could probably be smart? They have the freedom of will to speak the truth.

Which means in the "Yes" cases we could actually wind up with troublemakers who deliberately lied to us all the time.

Even worse, we could end up with a truthteller and a troublemaker in the final round, and they could both say "Yes, he is a troublemaker" over and over and over and over and... Well, over, until we ran out of cash.

Or am I missing out on something here? The thing that bugs me is that they have the freedom of choice, AND we have absolutely no clue if they can communicate in between questions - Realistically, if this was a village and I asked one person, rumour would spread quite fast, and before I got to the 10th person, everyone in the village would know what I was up to, and the troublemakers could greatly use that to their advantage!

[plainglazed]

I hate to be a Debbie Downer, but aren't we again ignoring the fact that these people could probably be smart? They have the freedom of will to speak the truth.

Which means in the "Yes" cases we could actually wind up with troublemakers who deliberately lied to us all the time.

Even worse, we could end up with a truthteller and a troublemaker in the final round, and they could both say "Yes, he is a troublemaker" over and over and over and over and... Well, over, until we ran out of cash.

Or am I missing out on something here? The thing that bugs me is that they have the freedom of choice, AND we have absolutely no clue if they can communicate in between questions - Realistically, if this was a village and I asked one person, rumour would spread quite fast, and before I got to the 10th person, everyone in the village would know what I was up to, and the troublemakers could greatly use that to their advantage!

I think the added bit of information that allows us to make positive conclusions is the fact that truthtellers are a majority.

[Guest]

I think the added bit of information that allows us to make positive conclusions is the fact that truthtellers are a majority.

Yet the troublemakers can act exactly like the truthtellers straight up until we take them on a trip. They could be honest through every single question except for one (just to give the riddle some sense) - So, in fact, we need a solution which can identify as little as one answer as true or false. Lie detectors are unavailable, I assume.

The conclusions we made so far are only correct if we assume the swindlecants (too much BrainDen for me), are in fact picking their answers at random - If we assume they're smart enough to pick them wisely, we're screwed.

Edited July 14, 2011 by Artificial

[Guest]

I think the added bit of information that allows us to make positive conclusions is the fact that truthtellers are a majority.

We are not assuming they vote randomly, we are considering every single possible combination of votes. Say in the case of you have 3 people and two are honest, and you ask 1 if number 2 is honest. And 1 says yes. We have no idea if 1 is honest or a troublemaker. What we do know is that either way, 2 is honest, regardless. If 1 says no, again we have no idea if 1 is honest or troublemaker. We do know that 3 is honest though, either way. There is nothing a troublemaker can do to thwart us because we take all possibilities into account and still find an honest person. The same thing works for 5 people, 7, 99, the method works.

Edited July 14, 2011 by Nana7

[Guest]

Yes, I understand your train of thought, and I can see how it works with 3 people - If number one says yes; given he's honest, so is number 2. Given he lies and says yes.. Well, that's a paradox because two people would obviously be honest here.

However, I don't see that working for 5 people - I assume you'd be asking two people about the same guy here. You know 3 are honest, two are not. So what happens if you by mistake ask both liars? They could answer Yes/No. Now you would know one of them was a liar, however you would not know that both were. Therefore person number 3 could be either the second truthteller, or an honestant depending on who lied.

If number one lied with the "yes", then the third person would be an honestant. However, if number two lied with the no, then the third person (Who you would pick) would be the second liar (potentially, given you ask a liar and an honestant instead of both liars - The outcome would be the same in a yes/no situation.)

Furthermore, if you are asking 4 questions among these five people, you'll have the same paradox twice - Given we know 2 are liars, and that we won't ask the two people we already have asked (let's assume we got ta liar and an honestant) - Now we're asking two honestants (as we're lucky not to get a liar this time), and happen to ask about the third honestant, to which they both agree "No, he is not a troublemaker" . What can we deduct from this:

The third person could, or could not be a liar = We'll filter him out.

The two honestants could, for all we know be a liar and an honestant, but yet they agree the third person is an honestant.

Wait.. I just disproved myself. I see the point, I get it, I believe you, you were right. Sorry for making such a hassle.

Edited July 14, 2011 by Artificial

[Guest]

We do not start out asking anybody about the same person. We start by pairing everyone but the odd one out. For 5 people that is a and b, c and d, and e is left out. We ask a about b and we ask c about d. As long as a and c do not both say yes, we can find at least honest person with no more questions.

If they do both answer yes, then we will need another question. For our next question, we need to pick 3 people who we know only 1 of them can be a troublemaker. If we pick people b,d, and e, we know that only 1 of them can be a troublemaker. b and d can not both be troublemakers, because that makes a and c liars. e can not be a trouble maker if b is, that makes a a liar. ditto for e and d. No assuming here, we are looking at all cases. Now we have 3 people, 1 troublemaker, and 1 question gives us an honest person.

[Guest]

I

We do not start out asking anybody about the same person. We start by pairing everyone but the odd one out. For 5 people that is a and b, c and d, and e is left out. We ask a about b and we ask c about d. As long as a and c do not both say yes, we can find at least honest person with no more questions.

If they do both answer yes, then we will need another question. For our next question, we need to pick 3 people who we know only 1 of them can be a troublemaker. If we pick people b,d, and e, we know that only 1 of them can be a troublemaker. b and d can not both be troublemakers, because that makes a and c liars. e can not be a trouble maker if b is, that makes a a liar. ditto for e and d. No assuming here, we are looking at all cases. Now we have 3 people, 1 troublemaker, and 1 question gives us an honest person.

I've gone over it time and time again, and finally I got the idea. I'm sorry for the trouble caused. My brain's not running the way it should as I'm drifted off into a large web development project currently.

However, I tried to falsify the claim, and it seems it's bulletproof exactly because we have the majority. I had a little trouble understanding the "3 yes'es" argumentation, but I got it in the end.

Great puzzle, and great solution, Nana7.

[Guest]

Thanks but Plainglazed finished it off. And glad to see you understand the answer.

[voider]

Thanks but Plainglazed finished it off. And glad to see you understand the answer.

You all seem too happy to ditch the puzzle before solving it; Plainglazed notes (99 - 1) / 2 = 49, which is odd (PUN!)!

No one has demonstrated a complete solution yet: a complete solution needs induction or a general algorithm, along with stating the money spent in the worst case scenario.

While collectively, 3M, 5M and 7M cases have been solved fully, independent arguments were used to solve the worst case; there has been no induction. "3M, 5M, 7M have a pattern" is an illegitimate observation since the related series is actually 1M, 3M, 7M, 15M, ...

[5M is not a base case of 7M's worst case; nor is 9M related to 7M SINCE (9 - 1) IS A MULTIPLE OF 4!

Number of people: 1 3 7 15 31 63

Cost to shift/reduce: 0 1 3 7 15 31

Total cost to solve: 0 1 4 11 26 57]

New interest:

2M (1 Honest 1 Troubler)?, 4M (2H 2T)?, hence 9M?

These even-numbered groups seem less favourable.

It should be clear by now that with our popular algorithm the worst case is when, in an odd-sized group arranged for pairing off, every person in a pair that you question happens to be a Troubler and says Yes their 'partner' is honest. This minimises your information gain.

[plainglazed]

did notice the minor different strategy when analyzing the second round of 49. comparing 24 pairs all responding "yes" could result in 12 truthtellers and 12 troublemakers in the group of second members of each pair requiring inclusion of the 49th villager in the next round. So the sequence would be to ask 49, 24, 12, 6, 3, then 1 1$ questions. think a truthteller can be sessed out from the 99 villagers with some troublemakers but with a majority of truthtellers with at least 95 questions. as for a general algorythm, will think on that some but am more of a word guy.

[k-man]

One honest villager can be always found in an iterative manner. Each iteration must start with an ODD number of villagers (let's call it X=2n+1) with a majority of the villagers being honest. Let's call the number of honest villagers X_H and the number of troublemakers X_T. So, X_H>=n+1 and X_T<=n. The goal of each iteration is to reduce the number of villagers to another ODD number Y<=n+1 while preserving the majority of honest villagers (Y_H>Y_T). Each iteration requires asking n questions, so the cost of each iteration is $n.

In each iteration we arbitrarily pair 2n villagers leaving one unpaired. In each pair we call one villager A and the other B. We ask A "Is B honest?". Using H for Honest and T for Troublemaker the possible pairs and answers are:

AB Answer

-- ------

TT Yes or No

HT No

TH Yes or No

HH Yes

If the answer is NO, then we know that A and B cannot be both honest, so there is at least one troublemaker in this pair. So, we discard the pair entirely, thus reducing the total number of villagers by 2. The majority of honest villagers among remaining villagers is preserved because we know that at least one of the 2 discarded villagers is a troublemaker.

If the answer is YES, then we discard A and keep B for the next iteration. B can be a troublemaker, but ONLY if A is a troublemaker as well. Since we started with the majority of honest people, for every TT pair there must be a HH pair. In that HH pair the answer will be also YES, so for every troublemaker we keep for the next round there is at least one honest villager that we keep as well. So, in the worst case scenario, at the end of the iteration, the number of honest villagers kept for the next round will be at least equal to the number of troublemakers.

If at the end of the iteration we end up with an EVEN number of villagers we add the unpaired villager from THIS iteration to the group for the next round. The majority of honest villagers in the resulting group is guaranteed regardless of the type of the unpaired villager. If he is honest, then it's trivial as we already had at least a tie. If he is a troublemaker, then see spoiler for further proof that the honest majority is preserved.

If the unpaired villager is a troublemaker then the number of honest villagers among the pairs exceeds the number of troublemakers by at least 2 (X_H-X_T>=2). We need to prove that our selection method preserves the majority by at least 2 (Y_H-Y_T>=2).

We can ignore any HT pairs as they will all be eliminated and don't affect the majority. So, let's look at the other pairs. Every TT pair is matched by a HH pair. Since X_H-X_T>=2 there must also be at least one extra HH pair. There may or may not be TH pairs. There are 2 possibilities:

1) There are no TH pairs that answered YES. In this case, all selected villagers are villagers B from HH and TT pairs. For the resulting number of villagers to be an even number the total number of TT and HH pairs must be even. So X_HH-X_TT must be even and >1, so must be at least 2. Therefore, after selecting the villager B from each pair we will have at least 2 more honest villagers than troublemakers (Y_H-Y_T>=2).

2) There is at least one TH pair that answered YES. In this case we get at least one honest villager from the TH pair and one extra honest villager from the extra HH pair, so the total of honest villagers exceed the troublemakers by at least 2 again.

We continue these iterations until we reach Y=1, which is the object of the puzzle. The total cost depends on the pairs chosen and answers given, but the worst case scenario is when each iteration reduces the number of villagers to n or n+1 (whichever is odd). For 99 initial villagers the maximum cost of each iteration is:

1. $49 (49 villagers left)

2. $24 (25 left)

3. $12 (13 left)

4. $6 (7 left)

5. $3 (3 left)

6. $1 (1 honest villager left)

The total cost is $95.

[plainglazed]

take the number of villagers and break that down into a sum of powers of 2 and subtract the total number of terms from the total number of villagers. in the case presented here 99 = 2^6 + 2^5 + 2^1 + 2^0 so the least number of questions needed would be 99 - 4 = 95.

Edited July 15, 2011 by plainglazed

[voider]

My bad, I only read the start and end of plainglazed's post, but k-man's proof that you can add the unpaired one puts away any doubts.

Just wondering, can even cases be solved with limited questions?

[Guest]

My bad, I only read the start and end of plainglazed's post, but k-man's proof that you can add the unpaired one puts away any doubts.

Just wondering, can even cases be solved with limited questions?

Yes. Though remember one condition is we have a majority of honest. So for 2 people, there are 0 troublemakers. For 4 people, there is just one trouble maker, treat this case the same as n=3, spend 1 dollar. It should not be all that different from odd cases, as long as we have that majority which will be 1 larger than it was with odd cases.

Edited July 16, 2011 by Nana7

[Guest]

The simplest solution for even number of villagers where a majority are honest?

Shoot one of them.

Now you have an odd number of villagers with an honest majority. And we can solve that. And maybe they will give a discount on the questions now.

[plainglazed]

EDIT: rethinking general algorithm to include even number of villagers. need more coffee...

Edited July 16, 2011 by plainglazed

[Guest]

very good puzzle.

[voider]

Yeah I meant even cases where number of troublemakers is equal or less than the number of honest persons.

It is not solvable with 2 people, and 4 may be impossible too (perhaps an informal proof may arise, or simply a brute-force program demonstrates this one and we give up on the rest). If it is solvable, I wonder if there is a general pattern with even cases, particularly one with polynomial cost.

[bhramarraj]

You ask a villager about another villager, "what the other villager will tell if I ask him whether you are honest or not..?"

If the first & second persons are honest they will both say yes. If both are trouble makers then both may say any thing. Go on asking till you find combination of a honest and a troublemaker. Person saying "I don't know." will definitely be honest person and the other a trouble maker.