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)?
If you're the first question, then I think the answer is
If you're asking the second question, then I'll guess
Originally posted by AnthemUnder 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.
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.
- Joined
- 29 Dec 08
- Moves
- 6788
Originally posted by David113Wouldn't the same principles apply if there were just three people in the room with you, one of them a sometimes liar?
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.
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)
Originally posted by David113Any chance of a timely clue?
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:
Originally posted by AnthemI 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.
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 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.
Originally posted by David113There 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 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?
.
Originally posted by Grampy BobbyLet'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".
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]
.