The World of Layonara

The Layonara Community => General Discussion => Topic started by: darkstorme on June 14, 2009, 06:12:05 PM

Title: Three Prisoners Puzzle & Solution
Post by: darkstorme on June 14, 2009, 06:12:05 PM

For those who wanted the solution to the three prisoners puzzle from the quest today (http://forums.layonara.com/calendar.php?do=getinfo&e=12312&day=2009-6-14&c=3) (or anyone else who might be interested):

Three Prisoners Puzzle
... and solution.

So, the puzzle, in the context of the quest:

Three prisoners are being held for questioning by a Rofireinite court.  They are:

• Andrei "Nimblefingers" Ianos - rumoured to know his way around a lock, particularly when there are valuables beyond it.
• Barda "Soft Touch" Galerai - rumours abound in the darker parts of town that men who go home with her wake up with a headache.  In an alley.  Missing all their possessions.
• Cedrick "The Fist" Coaciala - Several previous arrests, usually to do with property damage to bars and their patrons.

The following facts are known:

• A substantial robbery occurred.  One of the three prisoners was the perpetrator.
• All three are suspected to be members of the Tattered Cowl thieves' guild, so it's likely that they all know who did it.
• A mage (likely also from the guild) got to the subjects before the Rofireinites did, and cast the following (non-canon) spells on them:
• One (the perpetrator) is compelled to tell the truth to all questions asked of him or her.
• A second is compelled to answer any question presented to them with a lie.
• The third is compelled either to tell the truth or lie, at random, for each question presented.
• All three had their speech centers scrambled identically by the mage.  Their language is now incoherent (though they understand Common), but the following is known: "ja" and "da" stand for no and yes - but which is which is unknown.


• A solicitor (hired by some unknown benefactor) has, through an obscure loophole in the local laws, limited the Rofireinites to three yes/no questions.  (Though, of course, the answers will be "ja" or "da".)  If they don't find the perpetrator within these three questions, all three prisoners must go free.

So.  There's the puzzle.  Those who want to try to work it out on their own, don't scroll down.

*
*
*
*

Hint: Hypothetical questions can help a lot here.

*
*
*
*

Hint the second: Particularly of the form "If I were to ask you Q, would you say X?"

*
*
*
*


Solution

Step One: Choose any one of the prisoners (we'll say Andrei, who will hereafter go by "A"), and ask the following question: "If I were to ask you 'Are you the one whose answers are true or false at random?', right now, would you say 'Ja.'?"  If A says "Ja", they're the Random one.  If they say "Da", they're either the liar or the truthteller.

How this works: Because the Random prisoner is either lying or telling the truth (and not simply answering at random) there's actually information here.  The key is to break it down into cases.  The first two cases to break down are whether A is Random, or Not Random.  Assuming A is Random:

• Case 1: A is telling the truth, and "Ja" means yes.  In which case, if the question were "Are you the Random prisoner?", he would answer "Ja".  So his answer to the larger question is also "Ja".
  
• Case 2: A is telling the truth, and "Ja" means no.  To the simple question ("Are you the Random prisoner?"), he would answer "Da", or yes, so to the larger question, he would answer "Ja".
  
• Case 3: A is lying, and "Ja" means yes.  To the simple question, he would answer "Da", and lie.  He is therefore compelled to answer "Ja" to the larger question.
  
• Case 4: A is lying, and "Ja" means no. To the simple question, he would answer "Ja", then, so he would also answer "Ja" to the larger question.
  

The case where A is non-random is left to the interested reader to flesh out, but in all cases, A is compelled to answer "Da".

Step 2(a):So, if A answers "Ja", we know he's the random one.  We then choose one of B or C and ask them "If I were to ask you 'Are you the truthteller?', would you say 'Ja'?"  If they answer "Ja", they're the truthteller.  If "Da", they're the liar.

How this works: As above, cases are the key, but this one is much simpler. Assume our questionee is the truthteller.

• Case 1: "Ja" means yes.  They would answer "Ja" to the simple question, so the larger question would also be "Ja".
  Case 2: "Ja" means no.  They would answer "Da" to the simple question, so the larger question would be "Ja".
  

This is easily extensible to the liar case as well, and we have our perpetrator.

Step 2(b): A isn't Random, so the next step is to determine whether he's the truthteller or the liar.  We borrow the logic from 2(a), and we've got him.

Step 3: This is only required if A is the liar.  We then know that one of B and C is Random, and one is our perp.  The remaining question, then, posed to A, would be "If I were to ask you 'Is B the prisoner who answers randomly?', would you say 'Ja.'?"  If B is Random, then A will answer "Ja", and C is our perp.  If not, "Da", and B gets thrown in jail.

How this works: See step 2(a).

Hope this got you all thinking; if anyone has any questions or clarification needed, post it here. :)

Title: Re: Jörmungandr's Journies, Quetzalcoatl's Quests...
Post by: Nehetsrev on June 14, 2009, 11:04:40 PM

Maybe I'm just not seeing the logic the way you do, but to me random means it really doesn't matter what the question is, because the answer is err..  random.

If you flip a coin, it doesn't matter whether you flipped it with your right hand, or your left, or a spoon, or a fork, or whatever (what it was flipped with or even how it was flipped repressents the question that was asked, or even how the question was asked) if it's truly random there's a 50/50 chance you'll get heads, and an equal chance you'll get tails, for that one flip.  Now say you flip the coin 100 times, you might have ten, or 27, or even 99 results in a row that turn up heads, it's not probable, but it is possible if the result is truly random.  Nesting one question inside another doesn't guarantee that the answer to the nested question will affect the answer to the larger question, since the answer to both questions is randomly generated independently to eachother.

For instance, if you ask, "If I were to ask you 'Are you the one whose answers are true or false at random?', right now, would you say 'Ja.'?"

If the prisoner is the randomized one his answer to the nested question (in red) has a 50% chance to be 'Ja', but at the same time his answer to the larger question (in blue) has an equal chance to be 'Ja' as much as it could be 'da', regardless of his answer for the nested question.

Mathematicly it might look like:
Answer = x * (y * a) * b
Where x is the 'larger' question, y is the 'nested' question and a & b each repressent seperate results of the randomness compulsion.
If the value for a or b can either be true (1) or false (0) at any given time you ask your question independently of eachother then you cannot solve the equation with a certainty.
If a = 1 and b = 1 you'd simplify to Answer = xy
If a = 1 and b = 0 it becomes Answer = x * (y * 1) * 0 = 0
If a = 0 and b = 1 it becomes Answer = x * (y * 0) * 1 = 0
If a = 0 and b = 0 it becomes Answer = x * (y * 0) * 0 = 0
The problem then is that you can never rely on both a and b to equal 1 and be truthful answers because they're random. So you don't know if the answer you're getting from the prisoner is truthful (xy) or false (0).

Am I making sense?

Title: Re: Jörmungandr's Journies, Quetzalcoatl's Quests...
Post by: Nehetsrev on June 14, 2009, 11:35:40 PM

Another way to solve your problem, assuming the identities of the three being interogated are known might be first to ask each individual, "Is your name variable?" where the variable is equal to the suspects own name.

The one who's compelled to tell the truth will do so, the one who lies will lie, the one that's compelled to be random could go either way, but at the least if he answers truthfully, you know who the liar is. If he answers falsely, you know who the truth-teller is.

Once you know either which prisoner always lies, or which always tells the truth you could ask "did prisoner x commit the crime?".
If you're asking the known truth-teller and he answers 'yes' you've now solved the crime.  If he says 'no', then you ask "did prisoner y commit the crime?"  If he still says 'no' then you know the truth-teller himself is the one who did it.
 If you're asking the known liar the same question, the first time if he says 'yes' you know he's lying so you know prisoner x didn't do it.  if he says 'no' then you've solved the crime, because prisoner x did do it.

Of course I've just realized that this doesn't account for the additional twist of solving for whether 'ja' or 'da' means 'yes'.

Title: Re: Jörmungandr's Journies, Quetzalcoatl's Quests...
Post by: Script Wrecked on June 15, 2009, 01:44:17 AM

The cleverness of this natty logic puzzle gets hung up on the semantic difference between "answering randomly" and "answering each (whole) question truthfully or liarly on a random basis."(1) Unfortunately, if you didn't get that when the puzzle was presented, you didn't stand a chance.



(1) and I only got that because the solution was presented and I tried to solve it for myself, and reread it several times, and then the whole thing made more and more sense, but yes, I would also have been stuck on "but he answers each question randomly".

Title: Re: Jörmungandr's Journies, Quetzalcoatl's Quests...
Post by: darkstorme on June 15, 2009, 11:52:41 PM

Quote from: Nehetsrev

Maybe I'm just not seeing the logic the way you do, but to me random means it really doesn't matter what the question is, because the answer is err..  random.

Quote from: Script Wrecked

The cleverness of this natty logic puzzle gets hung up on the semantic difference between "answering randomly" and "answering each (whole) question truthfully or liarly on a random basis."(1) Unfortunately, if you didn't get that when the puzzle was presented, you didn't stand a chance.

I tried to be explicit, both in the forum version and the in-game version, with the phrase "The third is compelled either to tell the truth or lie, at random, for each question presented." (Emphasis added.)  Not "Say 'Ja' or 'Da', at random."  However...

Let's allow our Random answer individual to be truly random - that is, regardless of the question posed of him, he simply answers "ja" or "da", as if flipping a coin, to use Nehetsrev's example.  The puzzle is still solveable - but the questions become a bit trickier.

As before, you choose one of the prisoners (again, for simplicity, we'll go with Andrei.)  The question then posed would be "Are an odd number of the following statements true: you are the liar, 'ja' means 'yes', Barda is the one who answers randomly?"

Alright, now, brace yourself for a huge truth table, in list form:
[list=1]

• Andrei is the truthteller.

[list=1]

• 'Ja' means 'yes'.

[list=1]

• Barda is Random. -> This results in the answer "da". (Andrei is not the liar.)
• Barda is the liar. -> This results in the answer "ja". (Only the middle statement is true.)

• 'Ja' means 'no'.

[list=1]

• Barda is Random -> This results in the answer "da". (Barda being random is the only true statement.)
• Barda is the liar. -> This results in the answer "ja". (None of the statements are true.)

[/list]

• Andrei is the liar.

[list=1]

• 'Ja' means 'yes'.

[list=1]

• Barda is Random. -> This results in the answer "da". (All three statements are true, but he's lying.)
• Barda is the truthteller. - > This results in the answer "ja".

• 'Ja' means 'no'.

[list=1]

• Barda is Random -> This results in the answer "da". (Only two correct statements, but Andrei's lying again.)
• Barda is the truthteller - > This results in the answer "ja". (One correct statement, but again - liar.)

[/list]
[/list]

So, regardless of whether Andrei is a liar or a truthteller, an answer of "da" means that Barda is random, and "ja" means that Cedrick is random.  

"But," I hear you protest, "What if Andrei is the Random one?"  Well, let's change what the statements above mean, then.  An answer of "da" means that Cedrick is not random, and "ja" means that Barda is not random.  And this doesn't change if Andrei is the random one!

So, one question down, and we have an (effective) truthteller at our disposal, using the same logic as in the previous incarnation of the problem.  We turn to whichever one of them we know not to be Random, and ask, "If I were to ask you 'Are you are the truthteller?', would you say 'ja'?"  (See step 2(a) in the original problem.)  If s/he is our truthteller, we're done.  But if they are the liar, we simply modify the question slightly, and ask, of the liar, "If I were to ask you, 'Is Andrei the truthteller?', would you say 'ja'?"

And presto, we have our truthteller.  Even if we treat our Random prisoner, whomever s/he is, as a flipped coin.

Title: Re: Jörmungandr's Journies, Quetzalcoatl's Quests...
Post by: darkstorme on June 15, 2009, 11:56:29 PM

Quote from: Nehetsrev

Another way to solve your problem, assuming the identities of the three being interogated are known might be first to ask each individual, "Is your name variable?" where the variable is equal to the suspects own name.

The one who's compelled to tell the truth will do so, the one who lies will lie, the one that's compelled to be random could go either way, but at the least if he answers truthfully, you know who the liar is. If he answers falsely, you know who the truth-teller is.

Once you know either which prisoner always lies, or which always tells the truth you could ask "did prisoner x commit the crime?".
If you're asking the known truth-teller and he answers 'yes' you've now solved the crime.  If he says 'no', then you ask "did prisoner y commit the crime?"  If he still says 'no' then you know the truth-teller himself is the one who did it.
 If you're asking the known liar the same question, the first time if he says 'yes' you know he's lying so you know prisoner x didn't do it.  if he says 'no' then you've solved the crime, because prisoner x did do it.

Of course I've just realized that this doesn't account for the additional twist of solving for whether 'ja' or 'da' means 'yes'.

Not only does this not solve for whether 'ja' or 'da' means yes, but it also doesn't take into account the limitation of three questions.  Good thought, though. :)

Title: Re: Three Prisoners Puzzle & Solution
Post by: darkstorme on June 15, 2009, 11:59:45 PM

I decided to give this discussion its own thread, so my quest thread doesn't get too cluttered. :)

Title: Re: Three Prisoners Puzzle & Solution
Post by: Pseudonym on June 16, 2009, 12:24:50 AM

Was killing all three and then acting all righteous and indignant an option?

Title: Re: Jörmungandr's Journies, Quetzalcoatl's Quests...
Post by: Script Wrecked on June 16, 2009, 12:28:26 AM

Quote from: darkstorme

Let's allow our Random answer individual to be truly random - that is, regardless of the question posed of him, he simply answers "ja" or "da", as if flipping a coin, to use Nehetsrev's example. The puzzle is still solveable - but the questions become a bit trickier.

...

"But," I hear you protest, "What if Andrei is the Random one?"  Well, let's change what the statements above mean, then.  An answer of "da" means that Cedrick is not random, and "ja" means that Barda is not random.  And this doesn't change if Andrei is the random one!

Isn't this dependent on the outer questions being answered as modifiers to the inner question, rather than being answered in a truly random(1) fashion?

Because when answering in a truly random fashion, you can get two different answers when asking the same question multiple times.



(1) unpredictably, having no relation to possible influencing factors (or, being uninfluenced by factors within its proximity)

Title: Re: Jörmungandr's Journies, Quetzalcoatl's Quests...
Post by: darkstorme on June 16, 2009, 12:36:09 AM

Quote from: Script Wrecked

Isn't this dependent on the outer questions being answered as modifiers to the inner question, rather than being answered in a truly random(1) fashion?

Because when answering in a truly random fashion, you can get two different answers when asking the same question multiple times.

Nope, not dependent.  If Andrei's the liar, "da" means Cedrick's the truthteller.  If he's the truthteller, "da" means Cedrick's the liar.  If he answers "da" or "ja" at random, whether or not he's lying, for any component of the question, doesn't matter.  If Andrei's the random one, then regardless if his answer is "da", or "ja", the person who would be indicated as non-random if Andrei were non-random is guaranteed to be non-random; because if Andrei is random, both of the others are non-random.

So if he is Random, you're guaranteed that the others are not.  If he's not Random, then you have a question that will give you another one that isn't as well.

Title: Re: Three Prisoners Puzzle & Solution
Post by: darkstorme on June 16, 2009, 12:40:56 AM

Quote from: Pseudonym

Was killing all three and then acting all righteous and indignant an option?

Oddly enough, Steel asked much the same question.  The answer, of course, was no; the prisoners weren't even actually there.

I think there's a knot in Gordium (http://en.wikipedia.org/wiki/Gordian_Knot) that needs the tender attention of you two.

Title: Re: Jörmungandr's Journies, Quetzalcoatl's Quests...
Post by: Script Wrecked on June 16, 2009, 01:22:54 AM

Quote from: darkstorme

Nope, not dependent.  If Andrei's the liar, "da" means Cedrick's the truthteller.  If he's the truthteller, "da" means Cedrick's the liar.  If he answers "da" or "ja" at random, whether or not he's lying, for any component of the question, doesn't matter.  If Andrei's the random one, then regardless if his answer is "da", or "ja", the person who would be indicated as non-random if Andrei were non-random is guaranteed to be non-random; because if Andrei is random, both of the others are non-random.

So if he is Random, you're guaranteed that the others are not.  If he's not Random, then you have a question that will give you another one that isn't as well.

How do you recognise a random answer from a non random answer?

Title: Re: Jörmungandr's Journies, Quetzalcoatl's Quests...
Post by: darkstorme on June 16, 2009, 02:36:58 AM

Quote from: Script Wrecked

How do you recognise a random answer from a non random answer?

Sorry, I'm not explaining this clearly enough.

If you accept the logic I've given for (case: Andrei is the truthteller) and (case: Andrei is the liar), then "da" means that Cedrick is definitely not random and "ja" means that Barda is definitely not random.  So those two cases are covered.

So we'll assign the answers those values:

• "Da" == Cedrick is non-random.
• "Ja" == Barda is non-random.

If Andrei is the Random prisoner, both of these values remain true!  So you don't need to know whether he's answering randomly or non-randomly, only that both random and non-random answers are possible. :)

Title: Re: Jörmungandr's Journies, Quetzalcoatl's Quests...
Post by: Script Wrecked on June 16, 2009, 03:15:25 AM

Quote from: darkstorme

So you don't need to know whether he's answering randomly or non-randomly, only that both random and non-random answers are possible. :)

Yes, I think the penny has just dropped. The answer that the random answerer gives (by application of "what would you say he says" and "not" logic)... is non-random!

So, even though it says "he answers randomly", that's a bit of a furphy, because, in the end, he doesn't (by lieu of the question, rather than his intent).

Thanks for your patience, matie.

Regards,

Script Wrecked.



PS. I hope this right... :rolleyes:

Title: Re: Three Prisoners Puzzle & Solution
Post by: lonnarin on June 16, 2009, 04:51:54 AM

Due Process?!!  Pah!  Rael scoffs at your trickery.  Thumbscrews and hot coals for all of them, they are ALL guilty by association! Find me this Loophole finder, he has exposed his membership with the guild with his interference and shall be put to death for obstruction of justice.  Let this be a lesson to all who would attempt to protect the wicked in a court of law!  And the Rofirienite Judges shall be executed for heresy against the supreme will of Sulterio in allowing this madness to continue.  

Hail the Deep Lord!  May Prantz and it's Master stand for a thousand years!

(that's how Brother Gloom would dispense justice ;) )

Seriously though, if you're limited to three questions, wouldn't it be easiest to ask all three of them a single scrutinizing question at once?  The limitations posed seem to expressly dictate only the number of questions posed by the interrogator, not the quantity of answers obtained or the number of people addressed per question.  I would have loved to spring that one on the loophole finder.  In the first round you could easily find the liar (or the truthsayer if 2 people lie) and have a 50% chance of finding the random guy with just one question.  Or an absolute chance if you took the one you identified and asked him if either one of the other two people did it, since they all supposedly know.  If he's the truthsayer and he says yes, then that guy did it and the other one didn't.  And if he's been identified as the liar you just need to take the opposite of what he says.  You could solve it with absolute certainty in just 2 questions with this method, without even having to discern whether the second two are lying, telling the truth or random.  All you need is one truth sayer or one liar confirmed, and then the solution is automatic.

I think that if the Rofirienites would feel beholden to honor the obscure loophole based on the way that it is written in the books, then they would appreciate the irony that there is no distinction stated in precisely in what manner a question is posed.  One could easily ask a crowd of 50 people a rhetorical question like "be ye all mad?" and that doesn't mean he asked 50 questions.  Fighting fire with fire seldom works, but loopholes can dismantle other loopholes.

I would however, declare a mistrial in any case, since a truth spell only finds what a person BELIEVES to be true.  If some crazy hobo claims that he is Elvis and you put him on a polygraph, it will indicate that he is indeed Elvis.  If the suspect THINKS that another person did it based on a false assumption, then the truth spell would be unable to discern the actual truth or falseness of the events, only his belief in it and that he is not lying.  It would be far wiser to ask no questions and simply weigh the case on forensic evidence alone.  In addition, they can only assume the nature of the mage's spell, so it could very well be programmed to change during specific questions.  The very fact that there was enchantment used against the suspects in the first place is grounds for anything they say to be a forced confession and thrown out.  Hence why we don't use sodium pentathol during court cases in free nations.  I would let the three of them go and execute the loophole finder and the mage on charges of high treason.  That'll teach the guild not to mess with the justice system.

Title: Re: Three Prisoners Puzzle & Solution
Post by: lonnarin on June 16, 2009, 06:03:29 AM

As for the girl in Labyrinth who faced the two doormen, one of them always telling the truth and the other always lying, it cracks me up how quickly she jumped to conclusions in her single question.  It would have been far easier to ask just two questions.  

1) Am I a blonde? YES! NO!  
*walks up to the one who said no*
2) Where do each of these doors lead?

She didn't even ask them about what paths were behind them too.  She just tried to deduce which one lied and which one told the truth, immediately assuming the truth-sayer held the safer path.  He could have always been standing in front of the evil door, telling the truth, after all! :P

Title: Re: Three Prisoners Puzzle & Solution
Post by: Gulnyr on June 16, 2009, 12:13:43 PM

Quote from: lonnarin

And the Rofirienite Judges shall be executed for heresy against the supreme will of Sulterio in allowing this madness to continue.

This is going off topic, but it's kinda interesting.

I'm not sure there are any Rofireinite judges in Prantz.  Jennara had to attend a trial there as a witness, and the only other Rofireinites around were Caighd (who came along and sat quietly) and a guy who seemed to be some sort of clerk and/or advisor (who also sat quietly most of the time).  Yeah, I was kinda shocked.  You hear all this stuff about the Rofireinites administering the courts (http://forums.layonara.com/rumour-has/125792-important-missive-golden-voice-justice.html), but it's not really a Rofireinite court.  It's a Rael court with a deep dwarf judge and a Rofireinite watching to lend some legitimacy, at least in my experience, which is only once, but that's one more than pretty much everyone else, heh.