Sunday, September 17, 2017

strategy - Identify who is who between 3 persons who tell the truth and lie alternately


Dipsy tells the truth in 1 day and lies in the next day alternately.
If today he tell the truth, tomorrow he will lying, 2 days later he will tell the truth, and so on.


Lala tells the truth in 2 days and lies in the next 2 days alternately.
If today, and tomorrow he tell the truth, 2 days and 3 days later he will lying, and so on.


Poo tells the truth in 4 days and lies in the next 4 days alternately.


You do not know which one is Dipsi, which one is Poo, and which one is Lala.
You only can ask a Yes/No question with only Yes/No answer.
Every question you ask, to each person cost 10 dollars.
Waiting for a day to ask, cost 2 dollars.

If you ask a non Yes/No question you will be fined 100 dollars, and you will not get any answer.


How many dollar minimum you have to prepare, before asking,
to identify, which one is Dipsi, which one is Poo, and which one is Lala.


Note :


I have my own answer, But I'm not sure whether my answer is the best answer or not.



Answer



If the questions you ask can be somewhat "meta", one can ignore the time aspect entirely to reach a worst case of 3 questions asked on the same day (30 dollars):



1) Ask A: “Are you Lala, or lying today, but not both?”

If the answer is yes, A is Lala, move to question 3, else:

2) Ask A: “Are you Dipsi, or lying today, but not both?”

If the answer is yes, A is Dipsi, else they are Poo.

3) We now know who A is. Let N be one of the remaining identities.
Ask B: “Are you N, or lying today, but not both?”

If the answer is yes, B is N and C is the remaining one, else C is N and B is the remaining one.




Explanation



The question gives the correct answer about the identity regardless of whether they are lying or not, since the exclusive-or (either, but not both) inverts the answer for liars only (“lying today” is true). An alternative way to phrase the question would be “is exactly one of the following true: a) you are Lala, b) you are lying today”.

For telling the truth today:



  • Lala = no, lying = no -> neither is true, so "no"

  • Lala = yes, lying = no -> exactly one is true, so "yes"



For lying today, if they only lie about the whole statement:


  • Lala = no, lying = yes -> one is true but not both, so lying "no"

  • Lala = yes, lying = yes -> both are true, so lying "yes"



For lying today, if they lie about every part separately:

  • Lala = no, !Lala = yes, !lying = no -> one is true but not both, so lying "no"

  • Lala = yes, !Lala = no, !lying = no -> neither is true, so lying "yes"




Hence the question gets the true answer no matter whether they are lying today or not, and no matter whether they lie about every part of the question or only the answer as a whole.

Looking at it graphically, consider a classic Venn diagram;



the truth table for “A or B, but not both” looks like:

but if B is “Are you lying today?”, then the person’s answers in the B circle are lies (shown in red):

so the answer to the compound/meta question will be “Yes” if and only if A is true, regardless of whether the person is lying.




The worst case of 3 questions is also optimal for yes/no questions, since there are 6 permutations of identities and each question can extract only one bit of information. Using a “no answer” question where the lack of answer is a distinct case from yes/no could theoretically help, but due to the $100 fine it is not worthwhile in this context.


Waiting for tomorrow is also not worthwhile since it conveys no information without asking a question, and it's cheaper to ask the questions without waiting.


No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...