4

I stumbled upon a mathematical/logical puzzle that I figured was impossible to solve. Here it is, straight from puzzles SE:

Two friends, Mark and Rose, are very famous logicians; they are so clever that they can deduce any logic connection possible in a matter of minutes even from the most vague situation.

Unfortunately, one day, the two friends are abducted by the Evil Logician, who is envious of their fame, and believes they don't deserve it. He imprisons them in his castle and decides to test their cleverness. They are kept in two different cells, which are located on opposite sides of the castle, so that they cannot communicate in any way. Mark's cell's window has twelve steel bars, while Rose's cell's window has eight.

The first day of their imprisonment, the Evil Logician tells first Mark and then Rose that he has decided to give them a riddle to solve. The rules are simple, and solving the riddle is the only hope the two friends have for their salvation:

In the castle there are no bars on any window, door or passage, except for the windows in the two logicians' cells, which are the only barred ones (this implies that each cell has at least one bar on its window). The Evil Logician will ask the same question to Mark every morning: "are there eighteen or twenty bars in my castle?" If Mark doesn't answer, the same question will then be asked to Rose the night of the same day. If either of them answers correctly, and is able to explain the logical reasoning behind their answer, the Evil Logician will immediately free both of them and never bother them again. If either of them answers wrong, the Evil Logician will throw away the keys of the cells and hold Mark and Rose prisoners for the rest of their lives. Both Mark and Rose know these rules. Can the two logicians redeem themselves? If so, what will the reasoning behind the correct answer be, and what's the minimum number of days it will take either of them to answer correctly?

https://puzzling.stackexchange.com/questions/45664/are-there-eighteen-or-twenty-bars-in-my-castle/45710#45710

Now my problem with this is, I do believe it cannot be solved, i.e. "logicians" arent going to escape anywhere since it's impossible to determine the total number of bars from the knowledge any single person has; and it's also impossible for them to share their knowledge in any way. The only information any of them can get is that the other one didnt answer the question when it was their turn, its impossible to draw any logical conclusion from that.

Now there's an accepted and 18+ upvoted answer that solves the problem. Incorrect, illogical answer in my opinion, but since the vast majority disagrees, I probably can't see something. Can the prisoners escape using only maths and logic and the info they have, i.e. no secret code agreed upon beforehand or anything like that? Where am I wrong? I am not pasting the accepted answer here since its very long, but you can check it following the link, if you wish. Or you may try and solve the puzzle yourselves before you check what others have answered. I am only interested if it can be done and if yes, where am I wrong in my reasoning.

Edit: there seems to be a misunderstanding. I am not asking whether there is a strategy that they can follow if both knew it in advance. I am asking if this can be solved by only using maths and logic. Lets say I am Rose in this situation. Day 1. Here's what I know:

-- I have 8 bars. I can see them.

-- Castle has either 18 or 20 total. Evil Logician says so.

-- Therefore Mark has either 10 or 12 total. Because only those numbers would add up with my 8 to 18 or 20 total bars in the castle.

-- Mark must realize, seeing his 10 OR 12, that I have either 10 or 8 (if he has 10); or 6 or 8 (if he has 12). Because only those numbers Would add up to one of the two possibly correct answers 18 or 20.

-- No matter if Mark has 10 or 12 he cannot answer how many I have. Therefore he's gonna stay silent.

So far so logical? Or was there a mistake in my chain of reasoning? If it was good so far...

There comes the kidnaper in the night 1, and asks me his question. Form that I learn that Mark didnt answer anything as I knew he wouldnt. What else can I logically conclude? That Mark had less than 18 bars? But of course, I already know it. He has either 10 or 12, both numbera are less than 18. What am I missing?

Community
  • 1
Sejanus
  • 143
  • 1
    Vote to close as off-topic: there is a tacit assumption that the two prisoners will try to maximise their outcome by not making counterfactual claims. That said, please argue your case on puzzling.stackexchange.com and only bring it to MSE if there is a significant mathematical point of dispute. – Rob Arthan Nov 15 '16 at 20:39
  • I am asking to help to solve this puzzle or to say whether its solvable, not to argue any point. Which by the way looks on topic to me: logic, maths and puzzle. Its not a prisoners dilemma or anything like that, its about pure formal logic and maths and nothing else. If you think reference to puzzles se may be misleading I can remove everything about it from the question. – Sejanus Nov 15 '16 at 20:45
  • To the op, I'm not on puzzle.se so I couldn't comment there. However I can see how you might reduce numbers per day. Day 1 silence from M, tells R that M has $leq 17$ bars. Why? If he had $18$ and he knows R has at least one bar, then he'd say $20$. So he must not know for certain, ie $\leq 17$ bars. Then silence from R, tells M that R has $\geq 2$ bars. Why? Because if $R$ had precisely 1 bar then one of the answers being correct means M has 17, and R says 18. But there was silence. Then M silence again, says that M's bars are $\leq 16$, because if he had $17$, $17+2>18$ ... – snulty Nov 15 '16 at 20:47
  • @snulty but R already had that information since she knew M had exactly 10 or 12 and no other number. "if he had 18" was an impossible situation and she knew it. Hence day 1 silence provides no new information to her to draw any conclusions upon. Where am I wrong? – Sejanus Nov 15 '16 at 20:52
  • ...and he'd answer $20$, and so on $\ldots$ – snulty Nov 15 '16 at 20:52
  • Why do you think R knew 10 or 12? Where does that info come from? – snulty Nov 15 '16 at 20:53
  • R knows she has 8. R knows the question is whether 20 or 18 total. The only way it can be either 20 or 18 total is if M had acordingly either 12 or 10. The Evil Logician will ask the same question to Mark every morning: "are there eighteen or twenty bars in my castle?" – Sejanus Nov 15 '16 at 20:54
  • @Sejanus to put maths terminology on it, not gaining useful information after day $n$ is not an inductive statement. As in if I get no useful information after day $n$ $\not\implies$ no useful information after day $n+1$. At least that is according to the upvoted answers. Like I said I can see how they work, and I think a graphical image of ruling out integers and zoning in on the correct answer would help – snulty Nov 15 '16 at 21:07
  • @Sejanus I see what you mean though, that I know it's one of two answers from day one, but at least the idea is that after so much silence one can be ruled out. – snulty Nov 15 '16 at 21:08
  • I agree that the solution seems correct, but I think there could be a faster solution : at the beginning of the "game", mark and Rose know the number of bars on the window of the other with a margin of two, so the hypothesis "the other may see 0 or 20" is useless... But I don't know how to shortcut the reasoning. I'll think about it before bedtime :-) – Nicolas FRANCOIS Nov 15 '16 at 21:13
  • 1
    I love formal logic and I'm really eager to learn the solution of this interesting puzzle if there is one. I dont want to make these comments into a discussion, so I'll just wait for the answers from the professionals in the field. But thanks for your comments @snulty and Nicolas FRANCOIS in the meantime I am also trying to find the solution myself, or at least errors in my logical reasoning that there isnt one. – Sejanus Nov 15 '16 at 21:24
  • As you say, "straight from puzzles.se". There are solutions there: http://puzzling.stackexchange.com/questions/45664/are-there-eighteen-or-twenty-bars-in-my-castle. @Sejanus you can look there. – Ethan Bolker Nov 15 '16 at 21:29
  • "The only information any of them can get is that the other one didn't answer when it was their turn, and it's impossible to draw any conclusion from that" not at all! You can conclude a lit of infi from that! First time the they know the other has fewer than 20. Each time they don't answer more possibilities are ruled out. – fleablood Nov 15 '16 at 21:48
  • @fleablood I was under impression first time they already know the other one has either 20 minus what I have, or 18 minus what I have. Because those two are the only cases where their number of bars would add up to respectively 20 or 18. And 20 or 18 are the only numbers allowed as "bars total". If I have 12, the other one cannot have 1 because that would not add up to neither 18 nor 20 but 13, and 13 is not the possibly correct answer and I know it from the start, from day 1. Where am I wrong? – Sejanus Nov 15 '16 at 22:14

2 Answers2

5

The correct answer to the Puzzling SE question is not hard to understand, but OP's assertion (that no one learns anything on the first day) also seems extremely plausible. I'd like to resolve that apparent contradiction by specifically addressing OP's answer:

Neither Mark nor Rose cannot figure the answer without info from the other one. I hope that much is obvious. Now, the only way for them to send a message to each other is by answering or not answering the question. Mark goes first, he knows Rose has either 8 or 6 bars. He does not know how many, so he does not answer.

Rose knows, that Mark didnt answer, and that Mark has either 10 or 12, and that Mark must have guessed Rose has 8||10 or 8||6 and in either case Mark wouldn't have answered. So Rose didnt receive absolutely no new information from Mark non answering, and cannot answer herself. Mark in turn didn't get anything new from Rose not answering. They cannot relay any information to each other than they already had before, hence each of them can only guess with 50 % chance. They cannot escape by using logic, and being genius logicians they do know it. The end.

The key assertion is that "Rose [received] no new information from [Mark's not answering on the first day]." Even if we're convinced (by the existence of a correct answer) that this is false, it's not immediately clear why it's false. What information, specifically, does Rose (or, even less intuitively, Mark) learn from Mark's non-answer, given that both logicians already knew what he would do?

Let's use $\square_M$ to denote a fact that Mark knows, $\square_R$ to denote a fact that Rose knows, $\square_{RM}$ to denote a fact that Rose knows that Mark knows, etc., and $N_M,N_R$ to denote the number of bars each person has. It's common knowledge that $N_M+N_R\in\{18,20\}$ and that $N_M,N_R\ge 1$; the rules of the puzzle are also considered to be common knowledge, as are the players' non-answers, once they're made. (Recursive definition of "common knowledge": a fact is common knowledge when everyone knows it is both true and common knowledge.) Now, Mark doesn't have $18$ or more bars; but if he did, he'd know that there were $20$ bars in the castle, and he'd give that answer on the first day. Here's the tricky bit. Rose knows that Mark doesn't have $18$ bars. Mark knows that she knows it. She knows that Mark knows that she knows it. Et cetera, but not et cetera forever: $$ \square_{R} N_M < 18, \\ \square_{MR} N_M < 18,\\ \square_{RMR} N_M < 18,\\ \square_{MRMR} N_M < 18,\\ \square_{RMRMR} N_M < 18, \\ \square_{MRMRMR} N_M < 18,\\ $$ but $$ \neg\square_{RMRMRMR} N_M < 18. $$ On the other hand, once it becomes common knowledge that Mark didn't answer on the first day, it's also common knowledge that $N_M < 18$. And so Rose does know something she didn't before: she knows that Mark knows that she knows that he knows that she knows that he knows that she knows that Mark has less than $18$ bars. And while this seems like a ridiculous little piece of information, because humans aren't very good at reasoning about multiple levels of hypothetical, it clearly is useful data; by assembling just these sorts of data, the logicians are able to eventually escape.

In case it's not completely obvious (j/k), why doesn't Rose initially know this fact?

  1. She knows that she has $8$ bars, so she knows that Mark could have either $10$ or $12$ bars. For her to know for sure that $\square_{MRMRMR} N_M < 18$, it would have to be true in either possible case. She considers the case where Mark has $12$ bars. In that (perfectly plausible, from Rose's point of view) case:
  2. Mark knows that he has $12$ bars, so he knows that Rose could have either $6$ or $8$ bars. For him to know for sure that $\square_{RMRMR} N_M < 18$, it would have to be true in either possible case. He considers the case where Rose has $6$ bars. In that (perfectly plausible, from this hypothetical Mark's point of view) case:
  3. Rose knows that she has $6$ bars, so she knows that Mark could have either $12$ or $14$ bars. For her to know for sure that $\square_{MRMR} N_M < 18$, it would have to be true in either possible case. She considers the case where Mark has $14$ bars. In that (perfectly plausible, from this twice-hypothetical Rose's point of view) case:
  4. Mark knows that he has $14$ bars, so he knows that Rose could have either $4$ or $6$ bars. For him to know for sure that $\square_{RMR} N_M < 18$, it would have to be true in either possible case. He considers the case where Rose has $4$ bars. In that (perfectly plausible, from this thrice-hypothetical Mark's point of view) case:
  5. Rose knows that she has $4$ bars, so she knows that Mark could have either $14$ or $16$ bars. For her to know for sure that Mark knows that she knows that $N_M < 18$, it would have to be true in either possible case. She (4x-hypothetical Rose) considers the case where Mark has $16$ bars. In that case:
  6. Mark knows only that Rose has $2$ or $4$ bars. For him to know for sure that Rose knows that $N_M < 18$, it would have to be true in either possible case. But if Rose had only $2$ bars, she couldn't rule out his having $18$ bars. So, Mark thinks, it's possible that Rose doesn't know that $N_M < 18$. Mark can't know whether she knows it or not. Hence $\neg \square_{MR} N_M < 18$...
  7. (5) ... so, 4x-hypothetical Rose would think, it's possible that $\neg \square_{MR} N_M < 18$. Hence $\neg \square_{RMR} N_M < 18$...
  8. (4) ... so, thrice-hypothetical Mark would think, it's possible that $\neg \square_{RMR} N_M < 18$. Hence $\neg \square_{MRMR} N_M < 18$...
  9. (3) ... so, twice-hypothetical Rose would think, it's possible that $\neg \square_{MRMR} N_M < 18$. Hence $\neg \square_{RMRMR} N_M < 18$...
  10. (2) ... so, hypothetical Mark would think, it's possible that $\neg \square_{RMRMR} N_M < 18$. Hence $\neg \square_{MRMRMR} N_M < 18$...
  11. (1) ... so, Rose correctly concludes, it's possible that $\neg \square_{MRMRMR} N_M < 18$.

And so it's actually the case (before Mark's non-answer, but not after) that $\neg \square_{RMRMRMR} N_M < 18$.

Indeed, with each successive non-answer, the two logicians are able to chip away a little more at this wall of hypotheticals, until eventually they tunnel through to freedom.

Community
  • 1
mjqxxxx
  • 41,358
  • Thanks for your answer! So, since I am not a master logician, I will need some clarification here. Since R. already knew M. will not answer she was already in the position to draw all the logical conclusions that follow from the fact that M does not answer? – Sejanus Nov 16 '16 at 06:32
  • 1
    R did know that M would not answer. And M knew that she did. And R knew that he knew that. Etc... but R did not know that M knew that R knew that M knew that R knew that M knew that R knew that M would not answer (if I counted that right). Just like if I have the 9 of clubs in my hand and I ask if you have it. We both know you'll say "no". But you saying no still changes things, because before, you didn't know that I knew you'd say no. This is the same idea, just with more layers. Try to carefully read the argument... you don't need to be a master logician. – mjqxxxx Nov 16 '16 at 07:41
  • So by asking me whether I have 9 of clubs you ensure that I know that you know that I dont have it, right? You give me information I didnt have before. Therefore you too have new info now, i.e. that I now know that... well thats interesting and does seem to lead somewhere. I am going to try and work this out, thanks again for the help! – Sejanus Nov 16 '16 at 08:12
2

So Rose didnt receive absolutely no new information from Mark non answering, and cannot answer herself. Mark in turn didn't get anything new from Rose not answering.

Consider the case where Mark has 4 bars, and Rose has 6, and the question is 8 or 10 bars.

Day 1

  • Mark is asked.

What does he know so far? He knows that Rose has between 1 and 9 bars.

He knows that Rose knows that he has between 1 and 9 bars. Their information so far is symmetric.

Notice that though he actually knows that Rose has 4 or 6 bars, both 4 and 6 are in the range 1 and 9. Thus it is fair to make the claim.

  • Before Rose is asked.

She knows Mark has between 1 and 9 bars.

She knows that Mark knows the same.

  • After Rose is asked.

She knows that Mark didn't answer. From this, she deduces that he cannot have 8 or 9 bars. Otherwise, he would have answered 10 and they would be free.

She revises her estimate that Mark has between 1 and 7 bars.

Day 2

  • Right before Mark is asked.

Mark realizes that when he didn't answer, Rose deduced that he couldn't have more than 7 bars. If she only had 1 bar, she then would have guessed 8. But she didn't, so he knows that she can't have only 1 bar.

Since he was not freed the night before, he knows that Rose also does not have enough information to answer. If she had 8 or 9 bars, she could have answered 10 with confidence. Thus he knows she has less than 7 bars.

  • Mark is asked. He similarly knows that Rose cannot have 8 or 9 bars, or else she would have answered yes. Furthermore, Mark knows that Rose can deduce he has between 1 and 7 bars. Thus, if she had only 1 or 2 bars, then the possibilities for the total number of bars (according to her) would have been between 2 and 9. So she could answer 8. Thus, Mark now knows that Rose has between 3 and 7 bars.

  • Rose can deduce everything Mark can (note we NEVER use the number of bars either of them has in our logic so far). So she knows that Mark knows that she has between 3 and 7 bars. If Mark had 6 or 7 bars, he knew that she has between 3 and 7 bars so the total number of bars would have been 9 or greater, and he could have answered 10. Thus, she knows that he has between 1 and 5 bars. She can also do the same analysis Mark did, to conclude that Mark cannot have 1 or 2 bars. So she now knows Mark has between 3 and 5 bars.

She then concludes, knowing she has 6 bars, that there must be greater than 8 bars. Thus she answers 10.

But your logic (if it were correct, would also have applied to this scenario).

Nitin
  • 2,948
  • Why should I consider a different case? We are discussing this case not a different one. Proposed answer might be correct in a different case. It is not in this case. – Sejanus Nov 15 '16 at 21:29
  • Because of my comment at the end. Your answer would even apply to my simplified scenario. Thus it must be incorrect. – Nitin Nov 15 '16 at 21:30
  • At the very least (if you don't accept that the original question is solvable), you need a different refutation. – Nitin Nov 15 '16 at 21:31
  • He knows that she has 4 or 6 but we don't need that information. He also knows she has between 1 and 7. That is true, regardless of if he knows she has 4 or 6. – Nitin Nov 15 '16 at 21:45
  • Sorry I dont want to be argumentative but would you please explain where's logic in interpreting the Marks silence in that particular way when the knowledge she has dictates a different logical way? And sorry about that other comment of mine I already deleted. Mistook you for a different person and also tired. Thanks for trying to answer my question :) I will read and think through your answer in the morning, with a clear head – Sejanus Nov 15 '16 at 21:59
  • Please wait for my update. I will try to explain more fully. – Nitin Nov 15 '16 at 22:00
  • I apologize too, I was getting irrationally upset. I'm confident we can work through this. – Nitin Nov 15 '16 at 22:08
  • Amazing explanation! I saw this on Puzzling.SE first and all the explanations there were so complex, but this one is brilliant! OP, try writting down all the possible numbers that both M and R might have (ignoring the 12 & 8). So start with "2, 4, 6, 8, 10, 12, 14, 16, 18" set for both. First step: If M had 18, he would say "20!", but he doesn't so remains silent. Then you can cross out the 18 from is set. Next step: cross out 18 from R's set (same reasoning), also If R had 2, she would say "18!" because M's set is now only [2,...,16], but she doesn't so cross out 2 from R's set. So on... – Gintas K Nov 16 '16 at 15:25