There are 100 people in a room - 51 truth-tellers and 49 liars. A truth-teller always tells the truth. A liar somtimes tells the truth and sometimes lies. You are allowed to pick a person X, point to a person Y and ask X "is that person a truth-teller?". (X and Y may be the same person.) Your goal is to find a truth-teller (you must be absolutely sure that person is a truth-teller). How many questions of the above type do you need?
To clarify: Are you asking for the minimum number of questions after which you could discover a truth-teller (and be sure you are correct), or are you asking how many questions you need to be sure that you can find a truth-teller (no matter what strategy the liars use to decide whether to lie or not and no matter what the identity of the people you ask about happens to be)?
I would ask only one question ... wich person isn't telling the truth the truthful one will say its the liar and the liar will say its himself. cause a liar will even lie about being a liar....he,he,he
Originally posted by Anthem To clarify: Are you asking for the minimum number of questions after which you could discover a truth-teller (and be sure you are correct), or are you asking how many questions you need to be sure that you can find a truth-teller (no matter what strategy the liars use to decide whether to lie or not and no matter what the identity of the people you ask about ...[text shortened]... 74[/hidden] but I need to think about it a bit more to call this something more than a guess.
Under the first construal, I would think your answer has to be wrong. Consider the following. If X = Y and X responds "No" to your question, then you can be absolutely sure X is a liar (who happened to tell the truth there). But this could, conceivably, happen 49 times in a row to 49 different Xs; in which case, you can be absolutely sure you can identify a truth-teller (actually 51 of them). So, I think this undermines your first answer.
I'm asking the second question. You must find the minimum N such that you can be sure, before asking the first question, that after N question you will find a truth-teller.
Originally posted by David113 I'm asking the second question. You must find the minimum N such that you can be sure, before asking the first question, that after N question you will find a truth-teller.
Wouldn't the same principles apply if there were just three people in the room with you, one of them a sometimes liar?
I started to do this problem, then realized - there may be a 'smaller' answer depending on the conditions: Are you saying that the 'liars' MUST sometimes tell the truth and sometimes lie (ie if I ask a 'liar' about all 100 people and he says the truth about all of them, he's ALWAYS telling the truth - isn't he? So in the other scenario he MUST lie at least once about at least one person's status)... In the manner I had it originally set up it
was that the liar's could choose a strategy to answer one way or another to delay the number of questions as long as possible (according to a 'favorable' -for the liars -distribution of who you pick 🙂 I'm also assuming that the liar's KNOW who all
the truth tellers are)
There are 100 people in a room - 51 truth-tellers and 49 liars. A truth-teller always tells the truth. A liar somtimes tells the truth and sometimes lies. You are allowed to pick a person X, point to a person Y and ask X "is that person a truth-teller?". (X and Y may be the same person.) Your goal is to find a truth-teller (you must be absolutely sure that person is a truth-teller). How many questions of the above type do you need?
Still haven't had time to think more about it (the ability to ask someone about themselves is what I haven't thought about), but here is how I got my first guess:
The maximum number of people that can lie to you is equal to the number of liars in the group, therefore if more people agree about something than the number of liars, you know it to be true. So, start by choosing a person and ask the others about this person until you get 50 agreeing responses. If they agreed that he/she is a truth-teller we are done, if not continue on. Now you can ignore that person, as well as anyone who you now know lied to you, because you know they are liars. Repeat, asking those you have not eliminated about someone new (who you have not eliminated). Because you have eliminated some number of liars (one minimum) you need less agreeing responses. Continue to repeat until you either find a truth-teller, or have eliminated all 49 liars. The maximum number of questions this method requires is 50 + 49 + ... + 2, if the person you choose is always a liar and all liars tell the truth when you ask (so you cannot eliminate them).
Originally posted by Anthem Still haven't had time to think more about it (the ability to ask someone about themselves is what I haven't thought about), but here is how I got my first guess:
I think your analysis makes sense. In my first pass above I was thinking of the same plan as what you outline, but I realize now I jacked up the analysis.
I do not yet see how implementing any X=Y cases will help here. We have to assume worst case scenarios; and in the scenario that X = Y and X responds "Yes", I do not see how that could give you any useful information.
There are 100 people in a room - 51 truth-tellers and 49 liars. A truth-teller always tells the truth. A liar somtimes tells the truth and sometimes lies. You are allowed to pick a person X, point to a person Y and ask X "is that person a truth-teller?". (X and Y may be the same person.) Your goal is to find a truth-teller (you must be absolutely sure that person is a truth-teller). How many questions of the above type do you need?
There could be 100 truthful answers if the 49 liars told the truth. This result could continue to occur indefinitely as long as all liars kept buying into the party line without breaking rank. My sense is that this clever appeal to logic and math, which intentionally invites the overkill of myopic approaches to the correct solution, represents a colossal time waster. There really isn't any riddle inside a mystery wrapped in an enigma. This emperor is quite naked, no matter how loud all the befuddled townspeople sing his praises.
There could be 100 truthful answers if the 49 liars told the truth. This result could continue to occur indefinitely as long as all liars kept buying into the party line without breaking rank. My sense is that this clever appeal to logic and math, which intentionally invites the overkill of myopic approaches to the correct solution, represents a c peror is quite naked, no matter how loud all the befuddled townspeople sing his praises.
.[/b]
Let's visit that first sentence again. If the liars all told the truth the result would be an accurate 51/49 mix with all 49 liars identified. Wording should be "There could be 100 truthful answers if the 49 liars all lied about themselves... with no truthteller identified".
26 Aug '11 13:47
Reveal Hidden Content
Liars and truth-tellers
Back to Top