Author |
Topic: Four Liars at a party (birth order) (Read 1877 times) |
|
BMAD
Junior Member
Posts: 57
|
 |
Four Liars at a party (birth order)
« on: May 23rd, 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 13th, 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 13th, 2014, 8:57pm » |
Quote Modify
|
Notation:
2QL = 2-qestion liar who lies every other time (youngest person)
3QL = 3-qeustion liar who lies twice for every three questions
4QL = 4-question liar who lies trice for every four questions
5QL = 5-question 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 2-question 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 family-oriented 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 13th, 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 3-question 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 family-oriented who is who questions.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Four Liars at a party (birth order)
« Reply #4 on: Jul 13th, 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: 2872
|
|
Re: Four Liars at a party (birth order)
« Reply #5 on: Jul 14th, 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 15th, 2014, 5:24am by rmsgrey » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Four Liars at a party (birth order)
« Reply #6 on: Jul 14th, 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 14th, 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 14th, 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 14th, 2014, 1:48pm » |
Quote Modify
|
on Jul 14th, 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 14th, 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 14th, 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 14th, 2014, 10:29pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: Four Liars at a party (birth order)
« Reply #10 on: Jul 15th, 2014, 5:21am » |
Quote Modify
|
on Jul 14th, 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 15th, 2014, 9:12am » |
Quote Modify
|
on Jul 15th, 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: 2872
|
|
Re: Four Liars at a party (birth order)
« Reply #12 on: Jul 16th, 2014, 5:52am » |
Quote Modify
|
on Jul 15th, 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: 7526
|
|
Re: Four Liars at a party (birth order)
« Reply #13 on: Jul 16th, 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 16th, 2014, 11:45am » |
Quote Modify
|
on Jul 16th, 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 clear-cut.
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: 7526
|
|
Re: Four Liars at a party (birth order)
« Reply #15 on: Jul 17th, 2014, 12:39am » |
Quote Modify
|
on Jul 16th, 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 self-referential 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: 7526
|
|
Re: Four Liars at a party (birth order)
« Reply #16 on: Jul 17th, 2014, 12:47am » |
Quote Modify
|
on Jul 16th, 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 17th, 2014, 12:48am by Grimbal » |
IP Logged |
|
|
|
EdwardSmith
Junior Member
Posts: 61
|
|
Re: Four Liars at a party (birth order)
« Reply #17 on: Jul 17th, 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: 2872
|
|
Re: Four Liars at a party (birth order)
« Reply #18 on: Jul 17th, 2014, 6:13am » |
Quote Modify
|
on Jul 17th, 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 17th, 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 18th, 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 18th, 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 18th, 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: 2872
|
|
Re: Four Liars at a party (birth order)
« Reply #23 on: Jul 18th, 2014, 5:12am » |
Quote Modify
|
on Jul 18th, 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print