Author 
Topic: Four Liars at a party (birth order) (Read 1883 times) 

BMAD
Junior Member
Posts: 57


Four Liars at a party (birth order)
« on: May 23^{rd}, 2014, 3:07pm » 
Quote Modify

You meet four quadruplets at a party with a unique character flaw: they are all liars. When answering questions, the youngest of them lies every other time. The second youngest lies twice for every three questions. The next oldest lies three times for every four questions. And the oldest lies four times for every five questions. Each person must maintain their rate of telling lies but does not have to tell them in a pattern....eg. The oldest must tell four lies and one truthful answer for every five questions, so if asked five questions they may respond with lie, lie, true, lie, lie..then when asked another five questions they may respond with true, lie, lie, lie, lie. What is the minimum amount of questions needed to work out the order of birth for the quadruplets if you can't repeat questions or ask the same person a question consecutively?


IP Logged 



EdwardSmith
Junior Member
Posts: 61


Re: Four Liars at a party (birth order)
« Reply #1 on: Jul 13^{th}, 2014, 4:01am » 
Quote Modify

Ask each brother an obvious question with an obvious true answer (eg are you male or are you aged under 700) which he would answer yes if on that occasion he is telling the truth or no if he is lying. Rotate the questions around 3 of the 4 brothers. 1st brother true 2nd brother true 3rd brother true 1st brother false 2nd brother false 3rd brother false 1st brother true  proving he is the youngest 2nd brother false 3rd brother false 2nd brother false 3rd brother true proving he is 2nd youngest 2nd brother true proving he is the 3rd youngest Therefore the remaining brother is the eldest So the minimum would be 12 questions.


IP Logged 
Schottland Pension



rloginunix
Uberpuzzler
Posts: 1029


Re: Four Liars at a party (birth order)
« Reply #2 on: Jul 13^{th}, 2014, 8:57pm » 
Quote Modify

Notation: 2QL = 2qestion liar who lies every other time (youngest person) 3QL = 3qeustion liar who lies twice for every three questions 4QL = 4question liar who lies trice for every four questions 5QL = 5question liar who lies four times for every five questions. Questioning: Line up all the liars in one place at the same time. Current person: uncover the eyes, unplug the ears. Remaining three: cover their eyes (so that they can't see), plug their ears (so that they can't hear). Purpose: eliminate the human element of conjuring up. Question type (at first): binary, yielding only a "yes" or "no" answer. Source: Number Theory. Sample: "Zero equal zero. Yes?", next question: "Zero equals one. Yes?", next: "Zero equals two. Yes?", etc. If the answer is correct  mark it down as 1, 0 otherwise. From the definition of the "youngest person" who "lies every other time" (emphasis on other) we deduce that 1) that person must start with a 1, 2) must follow it up with a 0, 3) the only one in the group to produce a guaranteed sequence 10.10.10.10 and so on, where the period marks a 2question batch. Idea. Find the 2QL and use him/her to deduce who the remaining persons are by switching the question source  instead of number theory ask the familyoriented questions like "person B is 3QL. Yes?".


IP Logged 



rloginunix
Uberpuzzler
Posts: 1029


Re: Four Liars at a party (birth order)
« Reply #3 on: Jul 13^{th}, 2014, 9:31pm » 
Quote Modify

Line up all four liars and start asking each of them number theoretic questions. You are not allowed to ask the same person consecutive questions but that's just an awkward detail. Do it in a round robin fashion, keep the state (even though I'd argue they must be able to do it to be worthy of their titles). What are the choices? 2QL can only produce 10101 for the first 5 questions. 3QL: 100. or 010. or 001. where the period marks a 3question batch. Only 2 positions left: 10 or 01 or 00. 4QL: 1000. or 0100. or 0010. or 0001. with the only choices for the last position: 1 or 0. 5QL: 10000 or 01000 or 00100 or 00010 or 00001. It looks like 3, 4 and 5 QLs can not produce the same string of 1s and 0s as 2QL's no matter what the permutation of their choices will be. From this we conclude that people who do not speak the truth on the first round of questions can be safely eliminated from the questioning pool. Those who do not lie on the second question  eliminated from further questioning. Those who do not speak the truth on the third question  also relieved from questioning and so on. Name the persons A, B, C, D. Since randomness is involved it may so happen that A is 2QL and B, C and D decide to lie first. Well, you just found 2QL in 4 questions. If D is 2QL and A, B and C speak the truth first  that's 4 questions. A, B and C have no choice but to lie the second time around  that's 4 more questions, 8 total. In the third and final round you eliminate A, B, C and catch D as 2QL in a known state  after 8 + 3 = 11 questions you know that on your next question 2QL must speak the truth: switch from number theoretic to familyoriented who is who questions.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1029


Re: Four Liars at a party (birth order)
« Reply #4 on: Jul 13^{th}, 2014, 9:44pm » 
Quote Modify

In the binary decision tree below the question nodes alternate  somewhere 2QL must speak the truth, somewhere (s)he must lie. We squeeze every bit of opportunity to cut down the number of questions. Question numbers jump from 12 to 14 to 16 to conform to "no consecutive questions" requirement. I simply wasted these questions elsewhere (may be you can optimize even these). The questions themselves are of the form "this person (pointing at B, say) is 3QL. Yes?": So a number of scenarios are possible but in the worst case it looks like you can sort this bunch of liars in 16 questions.


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2873


Re: Four Liars at a party (birth order)
« Reply #5 on: Jul 14^{th}, 2014, 7:20am » 
Quote Modify

There are 24 possible birth orders, so, if you can devise a formula for getting a useful response to a given question regardless of whether the respondent is lying or telling the truth on that occasion, allowing you to get 1 bit of information each time, you could potentially do it in 5 questions. *** Just asking questions with known answers, and comparing them with the known truth, if your first question to a given brother starts a new block of n questions, it's possible to ask 19 questions of one brother and still not be able to tell 4QL from 5QL; if they both start with the second question of a block, 4QL and 5QL can tell the truth or lie in the exact same pattern as each other for 38 consecutive questions to one of them. Looking at how many questions it takes to separate the various pairs: 2QL v 3QL: 11 questions 2QL v 4QL: 07 questions 09 questions 2QL v 5QL: 07 questions 3QL v 4QL: 23 questions 3QL v 5QL: 17 questions 4QL v 5QL: 39 questions So, in the worst case, it takes at most 85 87 questions to identify all 4 brothers by asking them known truths  start by asking ABCABCABCABC... after 21 27 questions (7 9 each), you'll know that one of the four brothers is definitely neither 4QL nor 5QL. Continue questioning, alternating between two brothers who both could be either 4QL or 5QL, and are among the three you've been questioning. After another 16 14 questions each (32 28 between them; 53 55 total) to bring them to 23 each you'll know whether either of them is 3QL. If one of them is, you also know who 2QL is, and you just need to ask them the next 16 each (32 between them; 85 87 total) to bring them both to 39 answers to settle the 4QL/5QL question. If neither of them is 3QL, swap the one you last questioned for D (the other guy would take fewer questions to identify, but you've got questions to spare at this point)  you know which pair are 2QL and 3QL, and which pair are 4QL and 5QL, and you need another 16 questions to one of them to distinguish 4QL and 5QL, so you have 15 questions to use up on D, 11 of which tell you which of 2QL and 3QL he is, leaving you at 84 86 questions total. So, worst case for this approach looks like needing 85 87 questions (and must be more than the 77 questions needed to distinguish 4QL from 5QL)

« Last Edit: Jul 15^{th}, 2014, 5:24am by rmsgrey » 
IP Logged 



rloginunix
Uberpuzzler
Posts: 1029


Re: Four Liars at a party (birth order)
« Reply #6 on: Jul 14^{th}, 2014, 9:25am » 
Quote Modify

Thank you for your reply, rmsgrey. I guess I'm hitting a mental block or a blind spot. My plan was to not distinguish the siblings via explicit questions but rather to flush out the 2QL and use him/her to identify the rest. You are saying I'm not allowed to do that or I have a major flaw in doing so? I see your point if I interpreted "2QL must start with 1" too tightly. Say 2QL goes with a 0 first: 010101. Then yes, 2*lcm(2,3)  1 will distinguish it from 3QL. But I thought that in the span of the first 4 questions 4QL and 5QL can't possibly produce enough 1s  they can have only one 1 somewhere within the first 4 bits and thus can be eliminated from questioning. What am I missing?


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Four Liars at a party (birth order)
« Reply #7 on: Jul 14^{th}, 2014, 10:51am » 
Quote Modify

With a sufficiently tortured question (think fork in the road), you can get 1 bit of useful information out of any brother every time, so you can probably do it in 5 questions. Example question: Would an alternate universe version of you, who's in the same state of mind that you are now, say yes to the question "are you one of the two youngest brothers" If he's in the state of mind where he would lie, then the alt version would lie, and he'll lie about it, so you'll get a truthful answer to your "wrapped" question. If he's in a truthful state of mind, you'll also get a truthful answer. It's probably most efficient to just do a binary search in a list of permutations of possible birth orders. Which also gives a simple guarantee that every question is different. (Since the pivot point is different each time)

« Last Edit: Jul 14^{th}, 2014, 10:53am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



dudiobugtron
Uberpuzzler
Posts: 735


Re: Four Liars at a party (birth order)
« Reply #8 on: Jul 14^{th}, 2014, 1:48pm » 
Quote Modify

on Jul 14^{th}, 2014, 10:51am, towr wrote:With a sufficiently tortured question (think fork in the road), you can get 1 bit of useful information out of any brother every time, so you can probably do it in 5 questions. Example question: Would an alternate universe version of you, who's in the same state of mind that you are now, say yes to the question "are you one of the two youngest brothers" If he's in the state of mind where he would lie, then the alt version would lie, and he'll lie about it, so you'll get a truthful answer to your "wrapped" question. If he's in a truthful state of mind, you'll also get a truthful answer. 
 I don't see how this particular question gives you any more information than just asking "are you one of the two youngest brothers?". edit: OK, now I do see. However, the brothers aren't always forced to lie or tell the truth on any particular question. So I'm not sure they would know for sure whether an alternate version of them would lie for any particular question.

« Last Edit: Jul 14^{th}, 2014, 2:39pm by dudiobugtron » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Four Liars at a party (birth order)
« Reply #9 on: Jul 14^{th}, 2014, 10:26pm » 
Quote Modify

My intention was that if they're in the same frame of mind their next choice to answer truthfully or not will be the same. If there's any doubt, that's just a matter of further torturing the question. You just somehow have to equate the truthfulness of the alt's answer to the truthfulness of theirs. (You don't really need an alternate universe version, either). You can just make it more explicit:  If you were going to answer the question "... ?" as truthfully as you're going to answer this question, would you answer it with yes?

« Last Edit: Jul 14^{th}, 2014, 10:29pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rmsgrey
Uberpuzzler
Gender:
Posts: 2873


Re: Four Liars at a party (birth order)
« Reply #10 on: Jul 15^{th}, 2014, 5:21am » 
Quote Modify

on Jul 14^{th}, 2014, 9:25am, rloginunix wrote:Thank you for your reply, rmsgrey. I guess I'm hitting a mental block or a blind spot. My plan was to not distinguish the siblings via explicit questions but rather to flush out the 2QL and use him/her to identify the rest. You are saying I'm not allowed to do that or I have a major flaw in doing so? I see your point if I interpreted "2QL must start with 1" too tightly. Say 2QL goes with a 0 first: 010101. Then yes, 2*lcm(2,3)  1 will distinguish it from 3QL. But I thought that in the span of the first 4 questions 4QL and 5QL can't possibly produce enough 1s  they can have only one 1 somewhere within the first 4 bits and thus can be eliminated from questioning. What am I missing? 
 The question explicitly says that none of the brothers follows any particular pattern beyond having the right number of truths in each block of answers (though you don't necessarily know when a block starts). 2QL could go 01101001 rather than 10101010 or 01010101. If any of the brothers is on the last answer of a block when you start questioning, they could start 11  it's not until the 2QL is guaranteed to have told the truth for a third time (after question seven) that you can guarantee to distinguish him from 5QL. And, it turns out I got my numbers wrong for 2QL/4QL  both can produce 01001010 so it takes nine questions to distinguish them, bringing the worst case up to 87 questions.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1029


Re: Four Liars at a party (birth order)
« Reply #11 on: Jul 15^{th}, 2014, 9:12am » 
Quote Modify

on Jul 15^{th}, 2014, 5:21am, rmsgrey wrote: (though you don't necessarily know when a block starts). 
 That's the key! Now I see what's going on. I didn't really read the problem statement that way. I assumed that I'm in full control of exactly when the interrogation begins. I don't know how you've figured it out but what you're saying is that I'm more like a witness to an interrogation that's already in progress. In other words a constant stream of zeros and ones is coming in from each liar, now go figure out who is who. That changes the strategy. So mine will work only in one particular case (leaving the fork in the road compound questions idea aside). I also see I interpreted "lies every other time" differently. Apparently that definition (and all others) is relative  within any block of 2 (n=3,4,5) bits. Boy, did I simplify the problem in my favor or what. I don't know. You guys have infinitely more experience with this but I just wish the problem statements were less ambiguous and spelled these things out. In any case, thanks a lot rmsgrey.


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2873


Re: Four Liars at a party (birth order)
« Reply #12 on: Jul 16^{th}, 2014, 5:52am » 
Quote Modify

on Jul 15^{th}, 2014, 9:12am, rloginunix wrote:That's the key! Now I see what's going on. I didn't really read the problem statement that way. I assumed that I'm in full control of exactly when the interrogation begins. I don't know how you've figured it out but what you're saying is that I'm more like a witness to an interrogation that's already in progress. 
 The problem statement is vague on that point. If you do get to start questioning at the start of a block for each of them, then you can pin them down in 44 questions you already know the truthful answers to.


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527


Re: Four Liars at a party (birth order)
« Reply #13 on: Jul 16^{th}, 2014, 10:08am » 
Quote Modify

One problem with towr's twisted questions is that it works only in a deterministic universe. If there is a way to make a true random choice then you cannot ask about what one would do. And referring in a question to the truthfulness of the answer to that very question is problematic. There could be no valid answer at all.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Four Liars at a party (birth order)
« Reply #14 on: Jul 16^{th}, 2014, 11:45am » 
Quote Modify

on Jul 16^{th}, 2014, 10:08am, Grimbal wrote:And referring in a question to the truthfulness of the answer to that very question is problematic. There could be no valid answer at all. 
 While that is true for some questions, I don't see how it's a problem for questions in this form. These aren't liar's paradox type questions. If the subject is either going to lie or tell the truth, then the result is clearcut. If the subject wants to bullsh*t (i.e. answer independent of the truth, rather than affirming or denying it), then he's not following the premises of the problem. Quote:One problem with towr's twisted questions is that it works only in a deterministic universe. If there is a way to make a true random choice then you cannot ask about what one would do. 
 That might be an issue for the alternative universe formulation, but I don't see why that would be a problem for the other one. It's not like I'm asking two questions, so there are not two random choices to consider about whether to lie or not. The subject has to choose whether to lie or not, and then answer the question according to that choice. He can't answer randomly, because that would be neither lying nor telling the truth; he can only choose randomly how to answer (truthfully or not).


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527


Re: Four Liars at a party (birth order)
« Reply #15 on: Jul 17^{th}, 2014, 12:39am » 
Quote Modify

on Jul 16^{th}, 2014, 11:45am, towr wrote: While that is true for some questions, I don't see how it's a problem for questions in this form. These aren't liar's paradox type questions. 
 Maybe it is a philosophical question, but I feel selfreferential questions are not valid because they cannot be evaluated in a straightforward way. To answer the question you need to put it in an equation and solve the equation.


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527


Re: Four Liars at a party (birth order)
« Reply #16 on: Jul 17^{th}, 2014, 12:47am » 
Quote Modify

on Jul 16^{th}, 2014, 11:45am, towr wrote:That might be an issue for the alternative universe formulation, but I don't see why that would be a problem for the other one. 
 It was for the "alternate universe" question. A liar could decide randomly whether he wants to lie or not. Another problem is that the decision to lie could depend on the question. So in a question of the type "If I would ask you "...?" would you lie?" the lie doesn't necessarily cancel out in a double lie.

« Last Edit: Jul 17^{th}, 2014, 12:48am by Grimbal » 
IP Logged 



EdwardSmith
Junior Member
Posts: 61


Re: Four Liars at a party (birth order)
« Reply #17 on: Jul 17^{th}, 2014, 4:39am » 
Quote Modify

Best solution I can find 6 different questions rotated to 2 brothers. I have called the brothers A, B, C and D. Question 1 put to A Are you the youngest and is B the second youngest. Answer YES Question 2 put to B Are you the youngest and is D the eldest. Answer YES. Question 3 put to A Are C and D the two eldest. Answer YES Either his first or second questions is true. Question 4 put to B Are you and B the middle 2 Answer NO Either his first or second questions is true Question 5 put to A Are you the youngest Answer YES. This contradicts the first question so he is the youngest and B is the second youngest. Question 6 put to B Is D the third youngest Answer NO  We know this is a lie because this is his fouurth question and he has told the truth once. Thefore the brothers were born in A,B,C,D order


IP Logged 
Schottland Pension



rmsgrey
Uberpuzzler
Gender:
Posts: 2873


Re: Four Liars at a party (birth order)
« Reply #18 on: Jul 17^{th}, 2014, 6:13am » 
Quote Modify

on Jul 17^{th}, 2014, 4:39am, EdwardSmith wrote:Best solution I can find 6 different questions rotated to 2 brothers. I have called the brothers A, B, C and D. Question 1 put to A Are you the youngest and is B the second youngest. Answer YES Question 2 put to B Are you the youngest and is D the eldest. Answer YES. Question 3 put to A Are C and D the two eldest. Answer YES Either his first or second questions is true. Question 4 put to B Are you and B the middle 2 Answer NO Either his first or second questions is true Question 5 put to A Are you the youngest Answer YES. This contradicts the first question so he is the youngest and B is the second youngest. Question 6 put to B Is D the third youngest Answer NO  We know this is a lie because this is his fouurth question and he has told the truth once. Thefore the brothers were born in A,B,C,D order 
 There are several problems with this answer. You ask A whether he's the youngest and B's 2nd youngest, and then later ask A whether he's the youngest, get a "yes" to both, and declare that the answers contradict each other? You ask B whether he and B (himself) are the middle two and don't recognise his "no" as having to be true. After B answers his third question you say it's his fourth. You conclude an order that makes all three of A's answers true, which is impossible according to the problem statement.


IP Logged 



EdwardSmith
Junior Member
Posts: 61


Re: Four Liars at a party (birth order)
« Reply #19 on: Jul 17^{th}, 2014, 6:48pm » 
Quote Modify

I may have another go at this tomorrow. I rushed my last attempt a bit. It just reminds me of a game called mastermind that uses coloured pegs.


IP Logged 
Schottland Pension



EdwardSmith
Junior Member
Posts: 61


Re: Four Liars at a party (birth order)
« Reply #20 on: Jul 18^{th}, 2014, 1:09am » 
Quote Modify

Ask the first person for the answer, then prove that answer correct. This can be done in a minimum 5 questions. Question 1 to A What is the Birth order of the four brothers. Answer  A,B,C,D Question 2 Any random question to another brother. Question 3 to A Are you the youngest and is B the second youngest and is D the eldest. Answer  NO This disagrees with question 1 so either on question 1 or question 3 he told the truth. Question 4 Another random question to another brother Question 5 to A Are you the youngest and is B the second youngest and is C the third youngest. Answer  NO I think this proves the order is A,B,C,D.


IP Logged 
Schottland Pension



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Four Liars at a party (birth order)
« Reply #21 on: Jul 18^{th}, 2014, 2:19am » 
Quote Modify

Why do you assume the answer to question 5 must be a lie? I don't think that has to be the case.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



EdwardSmith
Junior Member
Posts: 61


Re: Four Liars at a party (birth order)
« Reply #22 on: Jul 18^{th}, 2014, 3:31am » 
Quote Modify

I'm pretty sure that I am right Question 3 asks if he was lying on question 1 The answer NO means he was telling the truth on one of the questions. On the fifth question he has to lie because he has told the truth once.


IP Logged 
Schottland Pension



rmsgrey
Uberpuzzler
Gender:
Posts: 2873


Re: Four Liars at a party (birth order)
« Reply #23 on: Jul 18^{th}, 2014, 5:12am » 
Quote Modify

on Jul 18^{th}, 2014, 3:31am, EdwardSmith wrote:I'm pretty sure that I am right Question 3 asks if he was lying on question 1 The answer NO means he was telling the truth on one of the questions. On the fifth question he has to lie because he has told the truth once. 
 Only if he's not the youngest, and started a new block of 3+ questions with your first question.


IP Logged 



