Three princesses

[Fleshpiston]

Greetings all, here is a logic puzzle I read online a while back.

You are the most eligible bachelor in the kingdom, and as such the King has invited you to his castle so that you may choose one of his three daughters to marry. The eldest princess is honest and always tells the truth. The youngest princess is dishonest and always lies. The middle princess is mischievous and tells the truth sometimes and lies the rest of the time.

As you will be forever married to one of the princesses, you want to marry the eldest (truth-teller) or the youngest (liar) because at least you know where you stand with them.

The problem is that you cannot tell which sister is which just by their appearance, and the King will only grant you ONE yes or no question which you may only address to ONE of the sisters. What yes or no question can you ask which will ensure you do not marry the middle sister?

[Shoofle]

How is this possible if one of the sisters has unpredictable behavior? I mean, if the middle sister is the one you ask, then there's a fifty-fifty chance that she will can be completely mistaken for one of the others.

They are completely indistinguishable because there are two answers, yes and no. Let's just get rid of those and say 'truth' or 'lie.' Now, we have a problem, because no matter what question you ask there is always a chance that you will get the middle sister and then it is impossible to know whether it's the oldest sister or the middle sister, because it seems to me that there's always a way that the middle sister could answer in such a way that you think the middle sister is the older sister, not to mention the fact that she might always seem like the younger sister.

See, this is a perfect example of why I cannot stand logic puzzles. I know that there is almost definitely going to be an answer, but my brain is so sure that it's impossible that I'm angry about it, and I know that no matter what, I'm not going to get it.[/i][/b]

[Fleshpiston]

Thanks for reading Shoofle.

I myself have never seen an answer for this problem. I came up with my own answer (several hours after reading the problem) which I believe to be verifiably correct, but I am interested to see if you guys will come up with the same one.

If there seems to be an interest, I will give hints. Maybe I will suggest that people who do find an answer do not post it right away, or cover it somehow.

[Shoofle]

The only viable solution I have come up with is inspired by the Order of the Stick. It is: Shoot each in the foot several times, and see which one always denies that they are in pain, or which one varies in response. By this method it might be determined who tells lies as well as truths, and avoid them like the plague.

[xkcd]

I'm pretty sure that any non-meta question is doomed by the fact that the sister who's deciding to lie or not can choose to flip her answer at any time; there's a chance that you're talking to her, and she can pick either one, and the information you got would just be her decision, in which case you'd determine nothing.

The exception would be meta-questions to which you could only answer "yes" whether you are lying or telling the truth (or "no"). If you posed one of these questions to a sister about another sister, I can see you figuring something out.

Also worth noting that questions like "are either of your sisters capable of lying" get a "yes" from both acceptable girls.

[Shoofle]

Also worth noting that questions like "are either of your sisters capable of lying" get a "yes" from both acceptable girls.

That question actually gets a "no" from the lying girl, right? Maybe you are thinking of the question "Are both of your sisters capable of lying?" which gives the answer yes from both acceptable girls. If the flip-flopper is telling the truth then she is the only one who could answer no, but there's no way to guarantee that she will be telling the truth. If she is lying at the moment, then she also says no.

[xkcd]

Also worth noting that questions like "are either of your sisters capable of lying" get a "yes" from both acceptable girls.

That question actually gets a "no" from the lying girl, right? Maybe you are thinking of the question "Are both of your sisters capable of lying?" which gives the answer yes from both acceptable girls. If the flip-flopper is telling the truth then she is the only one who could answer no, but there's no way to guarantee that she will be telling the truth. If she is lying at the moment, then she also says no.

Right, 'both'. My bad. And I think you mean 'yes' for your last word. Otherwise that'd be the answer, and also a nonmeta question to which the true and false answer is the same.

[Shoofle]

Right. What's an example of a question (if it exists) for which the answer to the question is the same whether telling the truth or lying?

Also, I have a revised method of completing the puzzle: I take a core sample from each sister and compare the number of rings each has. From this I determine their ages and marry the eldest.

[Pyrthas]

What happens if the answer is indeterminate?

Edit: Also, what constitutes a meta question?

[Fleshpiston]

As the author of this thread, I suppose I have some responsibility to follow up on your comments.

Of course, Shoofle, you cannot shoot or measure the rings of the sisters.

I believe xkcd knows that he has not yet come up with a solution.

I do not believe it matters what the girls do when asked a meta-question or an indeterminate question (e.g. the truth teller may just say "I don't know") but for simplicity's sake we can restrict the set of questions you can ask them to those that are unambiguously decidable.

For some reassurance, I believe there is an answer and it is not a trick. I may give hints soon, but I believe some of you out there are fully capable of finding a solution without any hints.

[xkcd]

Also, I have a revised method of completing the puzzle: I take a core sample from each sister and compare the number of rings each has. From this I determine their ages and marry the eldest.

That just made me laugh so hard.

I believe xkcd knows that he has not yet come up with a solution.

That's true, I haven't -- I was just posting the thoughts I'd had so far.

I do not believe it matters what the girls do when asked a meta-question or an indeterminate question (e.g. the truth teller may just say "I don't know") but for simplicity's sake we can restrict the set of questions you can ask them to those that are unambiguously decidable.

Okay; that can still be a meta-question, though. Pyrthas: A meta-question is a question about the answer to a question, including "the answer to this question." It may or may not be logically answerable. "What would that sister tell me if I asked her if she was the middle sister" is a weak meta-question, whereas "what will you answer to this question?" is a strong one in that it's not clearly decidable.

Fleshpiston is quite a name, by the way.

And you can go ahead and give a hint to me, at least; I've thought about it a bit and don't see an answer. It seems that the answer would have to involve a question to which both the true and the lying answer were the same, of which I haven't been able to think of one.

Hey, what about "Is the honest answer to 'are you lying to me in this overall answer' the same as the answer you would give to 'are you either the middle or truthy sister?' (under the same lying decision)?" If she decides her lying policy and then evaluates the answer question, this is workable, and the middle sister is forced to answer 'yes' whichever she decides to do (because what her decision was is part of the question).

The truthing and lying sisters both answer 'no' to this, and the middle sister answers 'yes' no matter what she decides. So that's a solution, assuming they don't have to be able to fully decide on an answer BEFORE deciding whether to lie and flip the answer.

(And if that's the case, I'm not sure it's solvable and would like a hint.)

[Pyrthas]

I do not believe it matters what the girls do when asked a meta-question or an indeterminate question (e.g. the truth teller may just say "I don't know") but for simplicity's sake we can restrict the set of questions you can ask them to those that are unambiguously decidable.

Okay. I was thinking about something like, "Would both of your sisters answer x to question y," the answer to whch only the middle sister will know (I think).

Anyway, I'm stumped, but I haven't given it as much thought as I'd like. And I'm busy for now. :/

[kira]

Okay. I was thinking about something like, "Would both of your sisters answer x to question y," the answer to whch only the middle sister will know (I think).

Even allowing that type of question, the problem is that the middle sister could lie and say that she doesn't know either. So then you'd have three "I dunno"s and no way of knowing who was who.

[Shoofle]

But that assumes that "I don't know" is a valid answer, and we don't tolerate lack of knowledge.

[Pyrthas]

Okay. I was thinking about something like, "Would both of your sisters answer x to question y," the answer to whch only the middle sister will know (I think).

Even allowing that type of question, the problem is that the middle sister could lie and say that she doesn't know either. So then you'd have three "I dunno"s and no way of knowing who was who.

This is precisely why I wanted to know what exactly would happen if a question with an indeterminate answer was asked. What you have said is certainly one of the, if not the most reasonable ways to handle such questions, but I figured that it should be made explicit.

[Fleshpiston]

Fleshpiston is quite a name, by the way.

I hope it doesn't offend. I figured that since you use the C-bomb in comic 75, it would be fine.

Hey, what about "Is the honest answer to 'are you lying to me in this overall answer' the same as the answer you would give to 'are you either the middle or truthy sister?' (under the same lying decision)?" If she decides her lying policy and then evaluates the answer question, this is workable, and the middle sister is forced to answer 'yes' whichever she decides to do (because what her decision was is part of the question).

This won't work because the middle sister might not answer the meta-question truthfully, either.

Pyrthas Posted: Sun Jul 16, 2006 7:20 am Post subject:

--------------------------------------------------------------------------------

kira wrote:
Quote:
Okay. I was thinking about something like, "Would both of your sisters answer x to question y," the answer to whch only the middle sister will know (I think).


Even allowing that type of question, the problem is that the middle sister could lie and say that she doesn't know either. So then you'd have three "I dunno"s and no way of knowing who was who.
This is precisely why I wanted to know what exactly would happen if a question with an indeterminate answer was asked. What you have said is certainly one of the, if not the most reasonable ways to handle such questions, but I figured that it should be made explicit.

Pyrthas makes a good point in that it does matter how we handle indeterminate questions. The "would both your sisters answer x to y" might distinguish between the middle sister, who can say for sure but might lie about it, and the other two, who cannot say for sure. But this solution is dissolved if we allow further mischief on the middle sister's part, to say "I dont know" which technically she is allowed to say (since it is a lie). Regardless, since that question is not "decidable" 2/3 of the time, it is not allowed as a solution.

It seems people are assuming something which was not my intention to imply. So (as a hint) I will give a timeline of events in this problem.

Time 0: You enter the castle and the King greets you. Next to him are all three sisters. He explains your problem.

Time 1: You choose the sister to which you will ask your question, and you ask it.

Time 2: That sister answers (must be Yes or No)

Time 3: You choose which sister you will marry.


This is not so much a hint as a clarification, to help you dispense with some assumptions which may have been hindering your progress toward finding a solution.

[xkcd]

Fleshpiston is quite a name, by the way.

I hope it doesn't offend. I figured that since you use the C-bomb in comic 75, it would be fine.

And I will probably say worse before the day is done. I'm just impressed. And I was imagining the series of thoughts that would lead you to pick "Fleshpiston" as your name.

"Well, hmm. How do I want to represent myself? Well, I'm kind of a piston of flesh. Yeah, fleshpiston."

It makes me laugh when I say it out loud.

Hey, what about "Is the honest answer to 'are you lying to me in this overall answer' the same as the answer you would give to 'are you either the middle or truthy sister?' (under the same lying decision)?" If she decides her lying policy and then evaluates the answer question, this is workable, and the middle sister is forced to answer 'yes' whichever she decides to do (because what her decision was is part of the question).

This won't work because the middle sister might not answer the meta-question truthfully, either.

Do you mean the sub-question, the question within the question? Which one? I am assuming, here certain things about where she decides to lie. I am assuming that she doesn't randomly decide to flip the value of things inside the question, she just works out the true answer to whatever you said, and then applies 'truth' or 'lie' to the whole thing as is her whim. If you assume she's going to change the answers to sub-questions, then you have to very carefully draw a line, which I don't think you can do, so that she doesn't just randomly change things you're referring to in the question.

Not to get mathematical, but I can't really find an easier way to say this -- if you combine several things with yes/no values into a single question, sometimes not very explicitly, do you assume she's going to flip them EACH at her whim, or does she just flip the final one? if it were programming, and you gave her ((q||q)&&(q||q)), does she evaluate the whole thing and then decide to lie, or does she evaluate each q and flip the answer? Because the individual q's could be pretty far removed from what it seems reasonable to expect her to flip . . . like "is the answer your other sister would give the same as the answer I would give in that situation?" do you assume she might lie about the answer the other sister would give before deciding to lie about the whole question? Does she lie about even more basic parts of the question?

I'm inclined to think she just lies once about the whole thing. Otherwise, any part of the question could get a random answer, and it really doesn't matter what you ask.

[Fleshpiston]

I'm inclined to think she just lies once about the whole thing. Otherwise, any part of the question could get a random answer, and it really doesn't matter what you ask.

You are correct about this. We must assume the middle sister lies (or tells the truth) once about the whole thing. Equivalently, we can think as if the middle sister always answers "yes" with probability 1/2, and "no" with probability 1/2, no matter what she is asked.

[raj]

the King will only grant you ONE yes or no question which you may only address to ONE of the sisters

So pick ONE question, but ask it several times. If the answer ever varies, it is the middle sister.

I believe there is an answer and it is not a trick.

Well, if my answer is the correct one, then it seems like a trick to me.

[Fleshpiston]

So pick ONE question, but ask it several times. If the answer ever varies, it is the middle sister.

very good try, but no. when I wrote one question I mean you get one opportunity to ask a question (once). asking the same question again would be another question and is not allowed.

sorry I wasn't more clear about that.

[Vonkwink]

How about a question like "Are you able to answer the following question _____"? That allows us to skirt around the indeterminate answer problem. Either that or "Are you always able to answer the following question _____?"

Now perhaps all that remains is figuring out what ____ is..?

[Vonkwink]

I think the way that we have to do it revolves around the fact that the middle sister must answer either truthfully or falsely - she can't answer with a solution that breaks logic. i.e. she couldn't answer a question like "can you answer this question falsely?"
This is obviously not the correct answer, but I think we might need to approach the program from these lines of thinking

[Fleshpiston]

Remember the question must be determinate (decidable), and we can think of the middle sister as saying "yes" or "no" with equal probability, no matter what comes out of your mouth.

It may be time for some hints about my solution. It turns out I can't figure out how to make my text invisible, so I will just make it white. This way you can skip it without accidentally reading it if you do not want hints. If you do, highlighting the following will make it easier to read.

1. You do not ask a meta-question (there is nothing about how someone would answer another question)

2. You ask something about more than one girl.


End of hints. Good luck.

[RealGrouchy]

This reminds me of the one I heard about a decade ago about the crossroads, and there were two brothers, one who always "lied" (i.e. answered yes/no questions with the opposite answer), and one who always truthfully answered yes/no questions.

Only one of the brothers would answer the door, and you'd get to ask him one question to find out what way to get to the village (the other fork in the road led, I'm sure, to some disastrous destination).

The proper question to ask was:

What direction would your brother tell me to go in to get to the village? (and you would take the other one)

However, for this quandry, I've tried a number of different questions, starting with meta-questions like "would both of your sisters deny you are the eldest?", but in his last post, the mechanical wankster said that 1. You do not ask a meta-question (there is nothing about how someone would answer another question) .

So taking Fleshpiston's (whose name I didn't actually read until xkcd commented onit) second clue of 2. You ask something about more than one girl. , I started again with questions like, Are either/both/neither of your sisters the eldest/youngest? and Is the younger/elder of your two sisters the eldest/youngest/middle?, but my brain is too fried to process all the variants.

The second hint is a bit unclear, as it seems to imply, contrary to the implication of the original question, that you can ask a compound and/or complex question.

I have no idea if I'm on the track, but I know that I'm not clever enough to find it on my own, so at least I won't lose any sleep over it. (plus I'm way too tired from this stupid flu....and getting up at 5:30 to do a morning show interview.)

- RG>

[Jesse]

"Time 2: That sister answers (must be Yes or No)"

You say the sister answers and it must be yes or no, but then you say that "I don't know" is an answer they may give, which just complicates things. If the middle sister can answer 'I don't know' then there can be no real solution as your question is wasted anyway.

[Fleshpiston]

"Time 2: That sister answers (must be Yes or No)"

You say the sister answers and it must be yes or no, but then you say that "I don't know" is an answer they may give, which just complicates things. If the middle sister can answer 'I don't know' then there can be no real solution as your question is wasted anyway.

You must not have read the latest version of the question. I narrowed the possible questions you can ask to those that have a definite answer and that the girls know.

So the oldest would answer yes or no (whichever is true)
The middle would answer yes or no (arbitrarily chosen)
The youngest would answer yes or no (whichever is not true)

Also, as a hint, you are wrong to say that there can be no real solution if the middle sister can answer "I don't know."

[xkcd]

Honestly, I'm at a loss.

[Jesse]

I still think I'm confused as to what's going on. Maybe I should get some sleep first.

[Nicolas Bourbaki]

I think Shoofle had it right with the very first reply to this thread. There is no question you can ask which will determine if you are talking to the middle sister or not.

Any question you come up with will either have both acceptable sisters giving the same response, or having the acceptable sisters giving opposite responses. Also, any question you come up with could either be answered "Yes" or "No" by the middle sister, so any answer you're looking for could be given by the middle sister, or by one or both of the acceptable sisters.

Another way of thinking about the middle sister is that she will always say the same thing (either Yes or No), no matter what the question. You don't know which response she will give, so it's impossible to construct a question with a Yes or No answer that will always be answered "correctly" by the middle sister.

[sniffels]

This is how I understand the puzzle:
- Given any question x (a truth statement which, when all the components are summed together, has one value which is either "true" or "false") all three sisters will determine a correct value for x.
- The eldest sister will respond giving an answer x (in sync with the correct solution.
- The youngest will give an answer !x (the opposite of the correct solution).
- The middle sister will discard x, generate a new answer y with probabilities 0.5 true and 0.5 false, and respond giving an answer y.

This implies that regardless of the question, the middle sister will answer unpredictably. Although one can force the eldest and youngest to respond with the same answer, there is no way to force the middle sister to give a particular answer.

[raj]

Sniffels, that's not completely correct.

If you ask the question "Are both your sisters capable of lying?", then both the oldest and youngest sister will answer "yes". So in this case, they both answer x instead of x and !x.

[Nicolas Bourbaki]

it's only his notation that was misleading, not his idea. If you look, he says that both acceptable sisters can be made to give the same answer.

x is the truth-value of the statement, not the answer given.

[sniffels]

Nicolas is correct. I think I need to restate this:

Given the three sisters, enumerate them as A, B, C (A being the eldest, C the youngest).
Given a truth statement X such that X is a function which, when given to a sister will be either true or false after being evaluated by that sister. In other words, X takes a sister as input and returns true or false.

As an example, assume X = "Do you always tell the truth?". X(A) = True, since the first sister always tells the truth. Also, the first sister will reply with the value Yes (true). X(C) = False, since the third sister always lies. However, the third sister will reply with True (in this case, the opposite of X, !X(C) ) since she always lies. X(B) = False, since the statement contains the term "always."
However, there remains a probability of 0.5 that the middle sister will tell the truth, regardless of the value of X(B). Thus, the middle sister always returns Y which is true half of the time and false half of the time.

The way I understand it is that regardless of how the truth statement X is formed there is an equal probability of the response being flipped by the middle sister, which means there is no way to predict the outcome.

[Vonkwink]

I think that to do this, we would NEED to force the middle sister to give an answer. The only way I can see of doing this is asking some question to her in which if she answers 'yes' (or 'no,' whatever, as long as it is one or the other)... then there would be a logical conundrum. Unfortunately, the only questions I can think of like that are meta questions.. so i too am stuck in xkcd's barrel..

[Nicolas Bourbaki]

I think that to do this, we would NEED to force the middle sister to give an answer. The only way I can see of doing this is asking some question to her in which if she answers 'yes' (or 'no,' whatever, as long as it is one or the other)... then there would be a logical conundrum. Unfortunately, the only questions I can think of like that are meta questions.. so i too am stuck in xkcd's barrel..

The other problem with this sort of question is that it's usually one that the truth-telling sister can't answer, and the rules state that all questions must be answerable.

For example,

Is the answer to my question "No?"

(of course, the lying sister could also answer this question, either with a yes or a no, so even if such questions were allowed, this would not be sufficient to solve the puzzle; I gave it merely as an example of a non-meta question which generates a logical conundrum.)

[Shoofle]

I gave it merely as an example of a non-meta question which generates a logical conundrum.

Actually, I think that is a meta-question, as it is a question about the question itself.

[sniffels]

I gave it merely as an example of a non-meta question which generates a logical conundrum.

Correct me if I am wrong, but I don't think it is possible to generate a question which doesn't refer to itself which is capable of producing a logical conundrum.


hehe, conundrum. i like that word.

[Nicolas Bourbaki]

Correct me if I am wrong, but I don't think it is possible to generate a question which doesn't refer to itself which is capable of producing a logical conundrum.

Well, for normal purposes, I think you're correct. However, you could have a nonsense question with no clear truth value: "Why is a mouse when it spins?" or "True or false: why is this flyer pink?"

Of course, multiple questions can easily produce the same effect:
A: Sentence B is true.
B: Sentence A is false.

[sniffels]

Nicolas,
To your first suggestion of forming a question with no clear truth value, the problem states that the question needs to be easily and clearly answerable as Yes or No (true or false). Thus, confusing the sisters as such is not allowed.

To your second suggestion of forming a compound question with two statements and a question evaluated with the assistance of those statements (I assume this is a correct interpretation of your idea), there is a single truth value determined from each question using the statements. Let us assume that the question is, "Is statement A true?" (For a true/false response ask, "Evaluate the truth value of statement A.") Since the truth statement needs statement A and statement B in order to be a complete question, than those statements are both contained within the truth statement making the truth statement self-referential.

[Nicolas Bourbaki]

sorry, I was posting out of the context of this "puzzle," since I was pretty sure we've decided that there's no possible solution?