9 ms·

The Logic Puzzle You Can Only Solve with Your Brightest Friend

76 points by dnetesn 8y ago

owenversteeg 8y ago
Sure, the given solution is nice. But the absolutely critical thing is that both people would think of it, eventually, which I doubt. The given solution seems to confuse quite a bit of people. Are there other solutions? The first "solution" I thought of was the first friend just using their "pass" as a simple signal of how many statues they have. This has the benefit of being very simple and more likely for someone to think of it themselves. Sadly it does not work because there's no way for them to signal the "end" of when to stop counting.
- StavrosK 8y ago
  I thought that, when the keeper comes to ask you, you distract him and make him late for the other person. You do that for 12 days, and the next day you pass immediately, so your friend knows it was 12 by knowing that the keeper came early the 13th time.
- palotasb 8y ago
  I think that's a great question, but I would guess the answer is no, there are no other solutions. One important axiom for this type of puzzle is that everyone does deduce every piece of information that they can mathematically deduce with 100% certainty. That would eliminate the "just guess" and "guess because your friend will not play along" type of answers some are giving in the thread. With this, my hand-wavy reasoning for not being any other solution is that when you try to model the knowledge the players possess after each turn (or equivalently, the state of the game), there are no branches or decisions they could make except for the STOP condition of the game. In each turn, they can (and because of the "axiom" above: they DO) eliminate some numbers from the set of possible number of statues the other player could be seeing if they passed in their round. Once the set goes down to one, they KNOW the answer. Since there are no choices [1] they could possibly make to alter the game before it ends, I don't see how there could be an alternate solution. [1] I'm discounting the possibility that they insert a constant pattern of extra passes in the game. (E.g., "We will both pass 5 times and then deduce the number based on the strategy described above.")
- joleal 8y ago
  I thought about that too, if he passes 6 times (and I've passed 6 times) I know that he has at least 6 (and he knows I have 10 or 12), so I pass a 7th time, and he passes a 7th time too. So now I know he can't have 6 therefore he has 8. This, however isn't the quickest way so it would probably fail if your partner is optimizing.
  - owenversteeg 8y ago
    Hmm. I was pretty convinced that my method would work, then I got convinced it couldn't work, now I'm confused again. A few notes: You can see 12, your friend can see 8. So your friend knows you have either 12 or 10. You know your friend has either 8 or 6. Step 1: you pass, friend knows you have >=1. Friend passes, you know they have >=1. Step 2: you pass, friend knows you have >=2. Friend passes, you know they have >=2. [...] Step 7: you pass, friend knows you have >=7. Friend passes, you know they have >=7; you have 12, so there must be 20, you win. I'm actually pretty convinced that it would work now... anyone want to poke a hole in it?
    - AstralStorm 8y ago
      Only if you use + 1 as a rule. What if your friend uses more efficient + 2, as you know the difference is by two? (Then unless you know who has the lower number, you're out of luck.)
    - nomynous 8y ago
      I thought of something along those lines at first as well. However, the problem is that the answer is not logically deducible using this method as it requires both of you to agree on a counting system and an end condition. And since the puzzle states that the two of you are not able to communicate, this method would not be viable. The given solution allows you to deduce the result with only the information and actions you have readily available to you.
sweezyjeezy 8y ago
I'm not sure I get the setup of this puzzle. He tells you at the start that the total between between you is 18 or 20. So you know from the start that your friend sees 6 or 8 and she knows that you can see 10 or 12. So neither of you 'learn' that the other person sees at least 1 / fewer than 19 on the first round - you both already knew this. So what knowledge have you actually learned after the first round, that you can take forward into the second round?
- CJefferson 8y ago
  So, you don't know how many statues your friend can see. On day 1, imagine you go second. If your friend can see 19 or 20 statues, they know there is 20. Therefore, if you go second on the first day, you know your friend couldn't see 19 or 20 statues.
  - sweezyjeezy 8y ago
    But you already know your friend sees 6 or 8 based on what you can see, and that you know that between you, you see 20. Both of you knew already, that this was not a possibility. I think I'm missing something from the setup.
    - yorwba 8y ago
      You know that your friend sees 6 or 8 and you know that if your friend sees 6 then they know you see 12 or 14 and (you know that they know that) if you see 14 then you know that they see 4 or 6 and (you know that they know that you know that) if they see 4 then they know that you see 14 or 16 and ((you know that they know that)^2) if you see 16 then you know that they see 2 or 4 and ((you know that they know that)^2 you know that) if they see 2 then they know that you see 16 or 18 and ((you know that they know that)^3) if you see 18 then you know that they see 0 or 2 and ((you know that they know that)^3 you know that) if they see 0 they know you see 18 or 20 ((you know that they know that)^4) if you see 20 then you know the correct answer and it's over So when it's not over on the first day, that updates your knowledge about each other's knowledge (about each other's knowledge ...) by eliminating that particular possibility. That goes on until only one possibility remains and you know the answer.
pjmorris 8y ago
What if two of the 12 statues are also part of the 8 statues (or vice-versa?) There'd be 18 statues, making a guess of 20 statues incorrect. I don't see how that's ruled out here.
- n4r9 8y ago
  It's not made explicit but I think there is not supposed to be any overlap between the visible statues. Otherwise I'm pretty sure the problem would become impossible.
  - pol_throw_away 8y ago
    I took this statement: 'The caretaker tells you each, individually, that together you can see either 18 or 20 statues. ' as being: size(see_A) + size(see_B) = 18 or 20 as opposed to: size(see_A union see_B) = 18 or 20 i would have assumed they would add the word distinct if they wanted to not double count overlapping statues.
  - wnkrshm 8y ago
    Count the shadows during the day.
  - rimliu 8y ago
    > Out of your friend’s window, which overlooks > the opposite side of the graveyard I'd say it is pretty explicit, unless the same statues happen to be on the opposite side, which sound funny.
- talltimtom 8y ago
  On the first reading I thought that was the entire point. That they would have to deduce whether they where seeing the same statues from either side. Which by the end of the reading ofcause makes no sense since they don’t have and can’t pass information about that at all.
- davweb 8y ago
  > Out of your friend’s window, which overlooks the opposite side of the graveyard, she can see eight. It could be clearer, but it is in the description that your friend is looking in a different direction to you and so presumably at different statues.
n4r9 8y ago
Very similar to the "Blue-Eyed Islanders" riddle: https://www.popularmechanics.com/science/math/a26557/riddle-of-the-week-27-blue-eyed-islanders/ https://www.popularmechanics.com/science/math/a26557/riddle-... They should make it clearer in the introduction that there is no overlap between the visible statues from each side.
- joshumax 8y ago
  Funny enough, it was the exact puzzle which I read about on XKCD that allowed me to draw a conclusion for this one so quickly. The trick for these is using shared knowledge and a shared signaling mechanism to deduce overall state at a specific time period.
  - n4r9 8y ago
    xkcd calls it the "hardest logic puzzle in the world". I think this one is a lot harder: http://olivernash.org/2009/10/31/yet-another-prisoner-puzzle/index.html http://olivernash.org/2009/10/31/yet-another-prisoner-puzzle...
    - misterdata 8y ago
      Much better explanation by Nick Berry: http://datagenetics.com/blog/december12014/index.html http://datagenetics.com/blog/december12014/index.html
  - jacobush 8y ago
    Is this used by some cryptocurrency?
lucraft 8y ago
It’s strange because at the beginning you know for a fact that your friend sees either 6 or 8, and your friend knows you see either 10 or 12, but the given process throws that information away. I think it’s possible to escape on Day 2 if you keep that knowledge: A is 12, B is 8 A knows B is either 6 or 8. If 6, B knows A is either 12 or 14. If 8, B knows A is either 10 or 12. B knows A is either 10 or 12. If 10, A knows B is either 8 or 10. If 12, A knows B is either 6 or 8. So the common knowledge (they both know it and they both know the other knows it too) at the beginning is: A is between 10 and 14 and B is between 6 and 10. Day one: if A saw 13 or 14 they would know it was 20, so when A passes, that signals to B that A is between 10 and 12. Now, if B saw 9 or 10, they would know it was 20, so B must be between 6 and 8 Day two common knowledge: A between 10 and 12. B between 6 and 8. If A saw 10 or 11 they would know it was 18, so when they pass B knows it must be 12 B knows it’s 20, and wins. ... Right?
- Zarel 8y ago
  Nice try, but you actually do need to work up from nothing. > Day one: if A saw 13 or 14 they would know it was 20, so when A passes, that signals to B that A is between 10 and 12. Your problem here is that if A saw 13, they would conclude that B saw 7 or 5. If A saw 14, they would conclude that B saw 4 or 6. In no case can A guess immediately. So B can't conclude anything quite so strong from the fact that A passes on Day One.
  - lucraft 8y ago
    > Your problem here is that if A saw 13, they would conclude that B saw 7 or 5. If A saw 14, they would conclude that B saw 4 or 6. In no case can A guess immediately. The common knowledge at this point is that B sees between 6 and 10, so A knows B doesn’t see 5 or 4.
    - yorwba 8y ago
      Your definition of common knowledge (they both know it and they both know the other knows it too) is too weak. For something to be truly common knowledge, the knowledge needs to be nested arbitrarily deep (they know, they know they know, (they know)^3, ...). Otherwise there's some remaining uncertainty about whether the other knows the common knowledge. In particular, your assumption that if A saw 14 they'd know that B doesn't see 5 or 4 is wrong, because if A saw 14 they don't have the common knowledge that B sees between 6 and 10, because that's dependent on A seeing 12.
duke-from-prima 8y ago
Please help understanding the puzzle. Is it possible we see 18 statues together? (e.g. there is 2 common statues, so I see 10 "own" + 2 "common", and friend sees 6 "own" + 2 "common"?) So, would that count as 18 or as 20 anyways?
- EliRivers 8y ago
  No. There are no common statues.
benmmurphy 8y ago
I have a solution to the puzzle in Rust: https://play.rust-lang.org/?gist=c56bd7d745ffcc90d59e4801e4126ceb&version=stable&mode=debug&edition=2015 https://play.rust-lang.org/?gist=c56bd7d745ffcc90d59e4801e41... new_common_knowledge of A: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18] new_common_knowledge of B: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18] new_common_knowledge of A: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] new_common_knowledge of B: [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] new_common_knowledge of A: [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] new_common_knowledge of B: [6, 7, 8, 9, 10, 11, 12, 13, 14] new_common_knowledge of A: [6, 7, 8, 9, 10, 11, 12] new_common_knowledge of B: [8, 9, 10, 11, 12] A announces: 20
deleted 8y ago
[deleted]
laumars 8y ago
I don't really understand the point of this puzzle because if he asks you 18 or 20 each time then you can escape in fewer days than the "correct" solution just by brute forcing the correct answer. There's only a maximum of 4 permutations that you and your friend can come up with. [edit] ahhh, I missed the "get it wrong and you die" bit. Thanks for the clarification guys.
- palotasb 8y ago
  Guessing wrong gets you locked up forever.
  - rimliu 8y ago
    Buried. The captor says he is preparing graves.
- JFFalcon 8y ago
  If either of you guesses wrong, you both die.
- benmmurphy 8y ago
  'Get it wrong, and neither of you ever leave.' basically, you can either pass or attempt to give a correct answer. if you try to give a correct answer and fail you are stuck forever. you can YOLO a guess but you have a 50% chance of being stuck forever.
mhandley 8y ago
I wonder if there's too much common knowledge here for the proposed solution to actually work. We both know there are either 18 or 20 statues. I can see 12, so I know from the start my friend can see either 6 or 8. My friend can see 8, so she knows from the start that I can see 10 or 12. Now, when I don't give the answer, she knows I can't see 19 or 20, but she already knew that. Did she actually learn anything from the fact I didn't give the answer? She knows I can't answer already, so what does she learn?
- dmurray 8y ago
  She did not know that I knew that she knew that I could not see 20.
  - topmonk 8y ago
    I think that, yes, on her turn, she did know that I knew that she knew that I could not see 20. Postulate 1: Total number of statues are 18 or 20 Lemma 1, she knows that I can either see 10 or 12 statues. Proof: She saw 8 statues. Since the total is either 20 or 18, it means that she knows I can either see 10 or 12 by Postulate 1 Lemma 2, suppose she saw 10 statues, she knows that I did not see 20. Proof: Assume she saw 10 statues. Since the total is either 20 or 18, it means that she knows I can either see 8 or 10 by Postulate 1 Lemma 3, suppose she saw 6 statues, she knows that I did not see 20. Proof: Assume she saw 6 statues. Since the total is either 20 or 18, it means that she knows I can either see 14 or 12 by Postulate 1 Prop: She knows that I knew that she knew that I could not see 20. Proof: She knows I can see 10 or 12. (Lemma 1) Lets consider the first case, from her viewpoint, that I have 10 statues. If I saw 10 statues, then I know she can only have seen 8 or 10 statues, by Postulate 1 If she saw 8, then by Lemma 1, she knew I could not see 20. If she saw 10 statues, then by Lemma 2, she also knew I could not see 20. Therefore, if I have 10 statues, I know that she knows that I could not see 20. Now for the second case, from her viewpoint, that I have 12 statues. If I saw 12 statues, then I know she can only have seen 6 or 8 statues, by Postulate 1 If she saw 8, then by Lemma 1, she knew I could not see 20. If she saw 6 statues, then by Lemma 3, she knows I could not see 20. Therefore, if I have 12 statues, I know that she knows that I could not see 20. For all the cases she knows that I could have, I know that she knows that I could not see 20. Therefore she knows that I know that she knows that I could not see 20. QED.
ggambetta 8y ago
I think the puzzle isn't specified well enough. Critically, it doesn't say that your friend knows whether you passed or not when you're asked, and this is a central part of the proposed solution: > First, you and your friend have to realize that each “pass” counts as a signal. But the spec only says > The caretaker asks you each one at a time, once a day, and you can choose to answer or to pass. Both of you know that you’re always asked first. If you both pass on a given day, the question [...] is posed to each of you again the next day, and the next, and so on, until you get it right or wrong. Also, "both of you know that you’re always asked first" could have been written in a less confusing way, e.g. "both of you know who is asked first".
- skrebbel 8y ago
  Not true. You're always asked first. If you had not passed, then your friend would be either freed or locked up forever (thus not asked at all).
  - ggambetta 8y ago
    This assumes the caretaker uses short-circuit evaluation :) It's a reasonable assumption to make, but I'd still argue the problem is under-specified.
    - neogodless 8y ago
      I thought what you thought at first, but I re-read it, and it's quite clear. Especially this second sentence. > The only way for you both to escape is for one of you to give the total number of visible statues. Get it wrong, and neither of you ever leave.
- Aardwolf 8y ago
  I was especially annoyed by the "*" pointing to a footnote in the problem description, where you then had to scroll over the spoilers to read the footnote
- BoiledCabbage 8y ago
palotasb 8y ago
Can it still be solved if I generalize the question like this? * Same setup: two prisoners A and B overlooking two distinct gardens with a constant nonnegative integer number of statues each. * The guard asks A and B each day if there are more than N statues total. * They can either guess or pass. * Wrong guess is a life sentence for both, game over. * Good guess and they are both out instantly. * N is a nonnegative integer. * N is the same each day. * N is the same for both A and B. * The question is posed each day to A first. * They both know all rules of this game. * A and B can't exchange information except indirectly by the fact that the other has passed in his turn and they get the question posed to them again. So the same except generalizing [18 or 20?] to [more than N, in this case more than 18?]. The solution in the article doesn't seem to require the more specific question and the information derived from it ("the other guy must see either either 20 - X or 18 - X statues"), while this seems to confuse some solutions given here. The guard asks whether there are at least N statues total. [For any integer N which in the linked case would be 19.]
deleted 8y ago
[deleted]
idrios 8y ago
I think I solved the problem backwards but I ended up with the same answer. I made a table of what I know vs what my friend knows. I know they have 6 or 8. If they have 6, then I have 12 or 14. If they have 8, then I have 10 or 12. | Me Them || Them Me | Them Me | -------------------------------------------------------------------------------------------- I have | 12 6 .. 8 || 6 12 .. 14 | 8 10 .. 12 | They have | 6, 8 12 14..10 12 || 12,14 6 8 .. 4 6 | 10,12 8 10 .. 6 8 | The first column is what I see and what I know about my friend. The 2nd and 3rd columns are what this table looks like to my friend. ----------- My friend has 6 or 8. 4 is the first number to appear on the table so start on day 4. Day 4: If my friend has 6, he thinks I have 12 or 14. If I have 14, then I would have notified the caretaker today because now 14 + 6 = 20. Now he knows I don't have 14. As a result, if he has 6 then he knows I have 12 and should tell the caretaker that the total number is 18. | Me Them || Them Me | Them Me | -------------------------------------------------------------------------------------------- I have | 12 6 .. 8 || 6 12 .. | 8 10 .. 12 | They have | 6, 8 12 ..10 12 || 12 6 8 .. | 10,12 8 10 .. 6 8 | Day 5: I don't have 14, and now my friend knows that. If he has 6, he should now have alerted the caretaker the number is 18. He did not. This means he does not 6. | Me Them || Them Me | Them Me | -------------------------------------------------------------------------------------------- I have | 12 .. 8 || | 8 10 .. 12 | They have | 8 ..10 12 || | 10,12 8 10 .. 6 8 | So Day 5 I know I have 12 and he has 8.
jonahrd 8y ago
How do you know who starts as the "low" counter and who's the "high" counter?
- rhplus 8y ago
  You start with 12: you can infer that the most your friend can see is 8. Your friend starts with 8: they can infer that the least you can see is 10.
mimimihaha 8y ago
This reminds me of one of my favorite puzzles: "Three wise men are told to stand in a straight line, one in front of the other. A hat is put on each of their heads. They are told that each of these hats was selected from a group of five hats: two black hats and three white hats. The first man, standing at the front of the line, can’t see either of the men behind him or their hats. The second man, in the middle, can see only the first man and his hat. The last man, at the rear, can see both other men and their hats. None of the men can see the hat on his own head. They are asked to deduce its color. Some time goes by as the wise men ponder the puzzle in silence. Finally the first one, at the front of the line, makes an announcement: “My hat is white.” He is correct. How did he come to this conclusion?"
- 0xcafecafe 8y ago
  This is also one of my favorites. Not too difficult to put you off but not too easy as well. Just needs detailed thought with process of elimination of cases.
- Lewton 8y ago
  Reminds me of the joke Three logicians walk into a pub, the bartender goes "3 pints?" First logician goes "Maybe", second goes "Maybe", third goes "Yes!"
  - mimimihaha 8y ago
    Haha i love it
a008t 8y ago
For those of you that are interested, there is a formal logic that can be used to reason about such problems, called Dynamic Epistemic Logic: https://eprints.soton.ac.uk/261816/1/EUMAS2.pdf https://eprints.soton.ac.uk/261816/1/EUMAS2.pdf A book chapter on the topic is available here: http://www.vub.ac.be/CLWF/SS/DELhandbookarticle.pdf http://www.vub.ac.be/CLWF/SS/DELhandbookarticle.pdf Course slides and other information can be found here: https://sites.google.com/site/thealexandrubaltagsite/teaching/dynamic-epistemic-logic-2017-2018 https://sites.google.com/site/thealexandrubaltagsite/teachin... It is a fascinating topic. Equipped with DEL, you can approach similar problems dealing with knowledge, belief, private and public announcements systematically.
mcrowson 8y ago
Answer: 22. You're wrong so he prepares your graves bringing the count to 22.
heptathorp 8y ago
It'd be funny if the puzzle was to count graves. Then you would answer 20. Either there are 20 and you're right, or there are only 18 so the caretaker digs 2 more for you and your friend, so you become right.
yogascribble 8y ago
I think I have a solution at day 2. At the start: A sees 12. A knows B can see 6 or 8. If 6, B knows A sees 12 or 14. If 8, B knows A sees 10 or 12. A knows B knows A sees 10 or 12 or 14. B sees 8. B knows A can see 10 or 12. B knows if A sees 10, A would know B sees 8 or 10. B knows if A sees 12, A would know B sees 6 or 8. B knows that A knows B sees 6 or 8 or 10. Day 1: A passes. B thinks, since A sees 10 or 12 he knows I see 6 or 8 or 10. If I saw 6, I would think he saw 12 or 14. A knows I see 6 or 8 or 10, so if he actually saw 14 he would know I see 6 and the answer is 20. A just passed, which means A does not see 14. B passes. Day 2: A thinks, B sees 6 or 8. If he saw 6 and thought I saw 12 or 14, then when I passed he would know I did not see 14. That would mean if he saw 6, I would have had to see 12 and he would have known the answer was 18. B just passed, which means B does not see 6. That means B sees 8. The answer is 20.
skate22 8y ago
The answer is: 19 + 5 % -2 If he says you got it wrong, the answer is 18, then you tell him that you wrote the answer in python If he says you got it wrong, the answer is 20, then you tell him you wrote it in javascript Thanks modulo!

76 points by dnetesn 8y ago

Sure, the given solution is nice. But the absolutely critical thing is that both people would think of it, eventually, which I doubt. The given solution seems to confuse quite a bit of people. Are there other solutions? The first "solution" I thought of was the first friend just using their "pass" as a simple signal of how many statues they have. This has the benefit of being very simple and more likely for someone to think of it themselves. Sadly it does not work because there's no way for them to signal the "end" of when to stop counting.

StavrosK 8y ago
I thought that, when the keeper comes to ask you, you distract him and make him late for the other person. You do that for 12 days, and the next day you pass immediately, so your friend knows it was 12 by knowing that the keeper came early the 13th time.
palotasb 8y ago
I think that's a great question, but I would guess the answer is no, there are no other solutions. One important axiom for this type of puzzle is that everyone does deduce every piece of information that they can mathematically deduce with 100% certainty. That would eliminate the "just guess" and "guess because your friend will not play along" type of answers some are giving in the thread. With this, my hand-wavy reasoning for not being any other solution is that when you try to model the knowledge the players possess after each turn (or equivalently, the state of the game), there are no branches or decisions they could make except for the STOP condition of the game. In each turn, they can (and because of the "axiom" above: they DO) eliminate some numbers from the set of possible number of statues the other player could be seeing if they passed in their round. Once the set goes down to one, they KNOW the answer. Since there are no choices [1] they could possibly make to alter the game before it ends, I don't see how there could be an alternate solution. [1] I'm discounting the possibility that they insert a constant pattern of extra passes in the game. (E.g., "We will both pass 5 times and then deduce the number based on the strategy described above.")
joleal 8y ago
I thought about that too, if he passes 6 times (and I've passed 6 times) I know that he has at least 6 (and he knows I have 10 or 12), so I pass a 7th time, and he passes a 7th time too. So now I know he can't have 6 therefore he has 8. This, however isn't the quickest way so it would probably fail if your partner is optimizing.
- owenversteeg 8y ago
  Hmm. I was pretty convinced that my method would work, then I got convinced it couldn't work, now I'm confused again. A few notes: You can see 12, your friend can see 8. So your friend knows you have either 12 or 10. You know your friend has either 8 or 6. Step 1: you pass, friend knows you have >=1. Friend passes, you know they have >=1. Step 2: you pass, friend knows you have >=2. Friend passes, you know they have >=2. [...] Step 7: you pass, friend knows you have >=7. Friend passes, you know they have >=7; you have 12, so there must be 20, you win. I'm actually pretty convinced that it would work now... anyone want to poke a hole in it?
  - AstralStorm 8y ago
    Only if you use + 1 as a rule. What if your friend uses more efficient + 2, as you know the difference is by two? (Then unless you know who has the lower number, you're out of luck.)
  - nomynous 8y ago
    I thought of something along those lines at first as well. However, the problem is that the answer is not logically deducible using this method as it requires both of you to agree on a counting system and an end condition. And since the puzzle states that the two of you are not able to communicate, this method would not be viable. The given solution allows you to deduce the result with only the information and actions you have readily available to you.

sweezyjeezy 8y ago

I'm not sure I get the setup of this puzzle. He tells you at the start that the total between between you is 18 or 20. So you know from the start that your friend sees 6 or 8 and she knows that you can see 10 or 12. So neither of you 'learn' that the other person sees at least 1 / fewer than 19 on the first round - you both already knew this. So what knowledge have you actually learned after the first round, that you can take forward into the second round?

CJefferson 8y ago
So, you don't know how many statues your friend can see. On day 1, imagine you go second. If your friend can see 19 or 20 statues, they know there is 20. Therefore, if you go second on the first day, you know your friend couldn't see 19 or 20 statues.
- sweezyjeezy 8y ago
  But you already know your friend sees 6 or 8 based on what you can see, and that you know that between you, you see 20. Both of you knew already, that this was not a possibility. I think I'm missing something from the setup.
  - yorwba 8y ago
    You know that your friend sees 6 or 8 and you know that if your friend sees 6 then they know you see 12 or 14 and (you know that they know that) if you see 14 then you know that they see 4 or 6 and (you know that they know that you know that) if they see 4 then they know that you see 14 or 16 and ((you know that they know that)^2) if you see 16 then you know that they see 2 or 4 and ((you know that they know that)^2 you know that) if they see 2 then they know that you see 16 or 18 and ((you know that they know that)^3) if you see 18 then you know that they see 0 or 2 and ((you know that they know that)^3 you know that) if they see 0 they know you see 18 or 20 ((you know that they know that)^4) if you see 20 then you know the correct answer and it's over So when it's not over on the first day, that updates your knowledge about each other's knowledge (about each other's knowledge ...) by eliminating that particular possibility. That goes on until only one possibility remains and you know the answer.

pjmorris 8y ago

What if two of the 12 statues are also part of the 8 statues (or vice-versa?) There'd be 18 statues, making a guess of 20 statues incorrect. I don't see how that's ruled out here.

n4r9 8y ago
It's not made explicit but I think there is not supposed to be any overlap between the visible statues. Otherwise I'm pretty sure the problem would become impossible.
- pol_throw_away 8y ago
  I took this statement: 'The caretaker tells you each, individually, that together you can see either 18 or 20 statues. ' as being: size(see_A) + size(see_B) = 18 or 20 as opposed to: size(see_A union see_B) = 18 or 20 i would have assumed they would add the word distinct if they wanted to not double count overlapping statues.
- wnkrshm 8y ago
  Count the shadows during the day.
- rimliu 8y ago
  > Out of your friend’s window, which overlooks > the opposite side of the graveyard I'd say it is pretty explicit, unless the same statues happen to be on the opposite side, which sound funny.
talltimtom 8y ago
On the first reading I thought that was the entire point. That they would have to deduce whether they where seeing the same statues from either side. Which by the end of the reading ofcause makes no sense since they don’t have and can’t pass information about that at all.
davweb 8y ago
> Out of your friend’s window, which overlooks the opposite side of the graveyard, she can see eight. It could be clearer, but it is in the description that your friend is looking in a different direction to you and so presumably at different statues.

n4r9 8y ago

Very similar to the "Blue-Eyed Islanders" riddle: https://www.popularmechanics.com/science/math/a26557/riddle-of-the-week-27-blue-eyed-islanders/ https://www.popularmechanics.com/science/math/a26557/riddle-... They should make it clearer in the introduction that there is no overlap between the visible statues from each side.

joshumax 8y ago
Funny enough, it was the exact puzzle which I read about on XKCD that allowed me to draw a conclusion for this one so quickly. The trick for these is using shared knowledge and a shared signaling mechanism to deduce overall state at a specific time period.
- n4r9 8y ago
  xkcd calls it the "hardest logic puzzle in the world". I think this one is a lot harder: http://olivernash.org/2009/10/31/yet-another-prisoner-puzzle/index.html http://olivernash.org/2009/10/31/yet-another-prisoner-puzzle...
  - misterdata 8y ago
    Much better explanation by Nick Berry: http://datagenetics.com/blog/december12014/index.html http://datagenetics.com/blog/december12014/index.html
- jacobush 8y ago
  Is this used by some cryptocurrency?

lucraft 8y ago

It’s strange because at the beginning you know for a fact that your friend sees either 6 or 8, and your friend knows you see either 10 or 12, but the given process throws that information away. I think it’s possible to escape on Day 2 if you keep that knowledge: A is 12, B is 8 A knows B is either 6 or 8. If 6, B knows A is either 12 or 14. If 8, B knows A is either 10 or 12. B knows A is either 10 or 12. If 10, A knows B is either 8 or 10. If 12, A knows B is either 6 or 8. So the common knowledge (they both know it and they both know the other knows it too) at the beginning is: A is between 10 and 14 and B is between 6 and 10. Day one: if A saw 13 or 14 they would know it was 20, so when A passes, that signals to B that A is between 10 and 12. Now, if B saw 9 or 10, they would know it was 20, so B must be between 6 and 8 Day two common knowledge: A between 10 and 12. B between 6 and 8. If A saw 10 or 11 they would know it was 18, so when they pass B knows it must be 12 B knows it’s 20, and wins. ... Right?

Zarel 8y ago
Nice try, but you actually do need to work up from nothing. > Day one: if A saw 13 or 14 they would know it was 20, so when A passes, that signals to B that A is between 10 and 12. Your problem here is that if A saw 13, they would conclude that B saw 7 or 5. If A saw 14, they would conclude that B saw 4 or 6. In no case can A guess immediately. So B can't conclude anything quite so strong from the fact that A passes on Day One.
- lucraft 8y ago
  > Your problem here is that if A saw 13, they would conclude that B saw 7 or 5. If A saw 14, they would conclude that B saw 4 or 6. In no case can A guess immediately. The common knowledge at this point is that B sees between 6 and 10, so A knows B doesn’t see 5 or 4.
  - yorwba 8y ago
    Your definition of common knowledge (they both know it and they both know the other knows it too) is too weak. For something to be truly common knowledge, the knowledge needs to be nested arbitrarily deep (they know, they know they know, (they know)^3, ...). Otherwise there's some remaining uncertainty about whether the other knows the common knowledge. In particular, your assumption that if A saw 14 they'd know that B doesn't see 5 or 4 is wrong, because if A saw 14 they don't have the common knowledge that B sees between 6 and 10, because that's dependent on A seeing 12.

duke-from-prima 8y ago

Please help understanding the puzzle. Is it possible we see 18 statues together? (e.g. there is 2 common statues, so I see 10 "own" + 2 "common", and friend sees 6 "own" + 2 "common"?) So, would that count as 18 or as 20 anyways?

EliRivers 8y ago
No. There are no common statues.

benmmurphy 8y ago

I have a solution to the puzzle in Rust: https://play.rust-lang.org/?gist=c56bd7d745ffcc90d59e4801e4126ceb&version=stable&mode=debug&edition=2015 https://play.rust-lang.org/?gist=c56bd7d745ffcc90d59e4801e41... new_common_knowledge of A: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18] new_common_knowledge of B: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18] new_common_knowledge of A: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] new_common_knowledge of B: [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] new_common_knowledge of A: [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] new_common_knowledge of B: [6, 7, 8, 9, 10, 11, 12, 13, 14] new_common_knowledge of A: [6, 7, 8, 9, 10, 11, 12] new_common_knowledge of B: [8, 9, 10, 11, 12] A announces: 20

deleted 8y ago

[deleted]

laumars 8y ago

I don't really understand the point of this puzzle because if he asks you 18 or 20 each time then you can escape in fewer days than the "correct" solution just by brute forcing the correct answer. There's only a maximum of 4 permutations that you and your friend can come up with. [edit] ahhh, I missed the "get it wrong and you die" bit. Thanks for the clarification guys.

palotasb 8y ago
Guessing wrong gets you locked up forever.
- rimliu 8y ago
  Buried. The captor says he is preparing graves.
JFFalcon 8y ago
If either of you guesses wrong, you both die.
benmmurphy 8y ago
'Get it wrong, and neither of you ever leave.' basically, you can either pass or attempt to give a correct answer. if you try to give a correct answer and fail you are stuck forever. you can YOLO a guess but you have a 50% chance of being stuck forever.

mhandley 8y ago

I wonder if there's too much common knowledge here for the proposed solution to actually work. We both know there are either 18 or 20 statues. I can see 12, so I know from the start my friend can see either 6 or 8. My friend can see 8, so she knows from the start that I can see 10 or 12. Now, when I don't give the answer, she knows I can't see 19 or 20, but she already knew that. Did she actually learn anything from the fact I didn't give the answer? She knows I can't answer already, so what does she learn?

dmurray 8y ago
She did not know that I knew that she knew that I could not see 20.
- topmonk 8y ago
  I think that, yes, on her turn, she did know that I knew that she knew that I could not see 20. Postulate 1: Total number of statues are 18 or 20 Lemma 1, she knows that I can either see 10 or 12 statues. Proof: She saw 8 statues. Since the total is either 20 or 18, it means that she knows I can either see 10 or 12 by Postulate 1 Lemma 2, suppose she saw 10 statues, she knows that I did not see 20. Proof: Assume she saw 10 statues. Since the total is either 20 or 18, it means that she knows I can either see 8 or 10 by Postulate 1 Lemma 3, suppose she saw 6 statues, she knows that I did not see 20. Proof: Assume she saw 6 statues. Since the total is either 20 or 18, it means that she knows I can either see 14 or 12 by Postulate 1 Prop: She knows that I knew that she knew that I could not see 20. Proof: She knows I can see 10 or 12. (Lemma 1) Lets consider the first case, from her viewpoint, that I have 10 statues. If I saw 10 statues, then I know she can only have seen 8 or 10 statues, by Postulate 1 If she saw 8, then by Lemma 1, she knew I could not see 20. If she saw 10 statues, then by Lemma 2, she also knew I could not see 20. Therefore, if I have 10 statues, I know that she knows that I could not see 20. Now for the second case, from her viewpoint, that I have 12 statues. If I saw 12 statues, then I know she can only have seen 6 or 8 statues, by Postulate 1 If she saw 8, then by Lemma 1, she knew I could not see 20. If she saw 6 statues, then by Lemma 3, she knows I could not see 20. Therefore, if I have 12 statues, I know that she knows that I could not see 20. For all the cases she knows that I could have, I know that she knows that I could not see 20. Therefore she knows that I know that she knows that I could not see 20. QED.

ggambetta 8y ago

I think the puzzle isn't specified well enough. Critically, it doesn't say that your friend knows whether you passed or not when you're asked, and this is a central part of the proposed solution: > First, you and your friend have to realize that each “pass” counts as a signal. But the spec only says > The caretaker asks you each one at a time, once a day, and you can choose to answer or to pass. Both of you know that you’re always asked first. If you both pass on a given day, the question [...] is posed to each of you again the next day, and the next, and so on, until you get it right or wrong. Also, "both of you know that you’re always asked first" could have been written in a less confusing way, e.g. "both of you know who is asked first".

skrebbel 8y ago
Not true. You're always asked first. If you had not passed, then your friend would be either freed or locked up forever (thus not asked at all).
- ggambetta 8y ago
  This assumes the caretaker uses short-circuit evaluation :) It's a reasonable assumption to make, but I'd still argue the problem is under-specified.
  - neogodless 8y ago
    I thought what you thought at first, but I re-read it, and it's quite clear. Especially this second sentence. > The only way for you both to escape is for one of you to give the total number of visible statues. Get it wrong, and neither of you ever leave.
Aardwolf 8y ago
I was especially annoyed by the "*" pointing to a footnote in the problem description, where you then had to scroll over the spoilers to read the footnote
BoiledCabbage 8y ago

palotasb 8y ago

Can it still be solved if I generalize the question like this? * Same setup: two prisoners A and B overlooking two distinct gardens with a constant nonnegative integer number of statues each. * The guard asks A and B each day if there are more than N statues total. * They can either guess or pass. * Wrong guess is a life sentence for both, game over. * Good guess and they are both out instantly. * N is a nonnegative integer. * N is the same each day. * N is the same for both A and B. * The question is posed each day to A first. * They both know all rules of this game. * A and B can't exchange information except indirectly by the fact that the other has passed in his turn and they get the question posed to them again. So the same except generalizing [18 or 20?] to [more than N, in this case more than 18?]. The solution in the article doesn't seem to require the more specific question and the information derived from it ("the other guy must see either either 20 - X or 18 - X statues"), while this seems to confuse some solutions given here. The guard asks whether there are at least N statues total. [For any integer N which in the linked case would be 19.]

deleted 8y ago

[deleted]

idrios 8y ago

I think I solved the problem backwards but I ended up with the same answer. I made a table of what I know vs what my friend knows. I know they have 6 or 8. If they have 6, then I have 12 or 14. If they have 8, then I have 10 or 12. | Me Them || Them Me | Them Me | -------------------------------------------------------------------------------------------- I have | 12 6 .. 8 || 6 12 .. 14 | 8 10 .. 12 | They have | 6, 8 12 14..10 12 || 12,14 6 8 .. 4 6 | 10,12 8 10 .. 6 8 | The first column is what I see and what I know about my friend. The 2nd and 3rd columns are what this table looks like to my friend. ----------- My friend has 6 or 8. 4 is the first number to appear on the table so start on day 4. Day 4: If my friend has 6, he thinks I have 12 or 14. If I have 14, then I would have notified the caretaker today because now 14 + 6 = 20. Now he knows I don't have 14. As a result, if he has 6 then he knows I have 12 and should tell the caretaker that the total number is 18. | Me Them || Them Me | Them Me | -------------------------------------------------------------------------------------------- I have | 12 6 .. 8 || 6 12 .. | 8 10 .. 12 | They have | 6, 8 12 ..10 12 || 12 6 8 .. | 10,12 8 10 .. 6 8 | Day 5: I don't have 14, and now my friend knows that. If he has 6, he should now have alerted the caretaker the number is 18. He did not. This means he does not 6. | Me Them || Them Me | Them Me | -------------------------------------------------------------------------------------------- I have | 12 .. 8 || | 8 10 .. 12 | They have | 8 ..10 12 || | 10,12 8 10 .. 6 8 | So Day 5 I know I have 12 and he has 8.

jonahrd 8y ago

How do you know who starts as the "low" counter and who's the "high" counter?

rhplus 8y ago
You start with 12: you can infer that the most your friend can see is 8. Your friend starts with 8: they can infer that the least you can see is 10.

mimimihaha 8y ago

This reminds me of one of my favorite puzzles: "Three wise men are told to stand in a straight line, one in front of the other. A hat is put on each of their heads. They are told that each of these hats was selected from a group of five hats: two black hats and three white hats. The first man, standing at the front of the line, can’t see either of the men behind him or their hats. The second man, in the middle, can see only the first man and his hat. The last man, at the rear, can see both other men and their hats. None of the men can see the hat on his own head. They are asked to deduce its color. Some time goes by as the wise men ponder the puzzle in silence. Finally the first one, at the front of the line, makes an announcement: “My hat is white.” He is correct. How did he come to this conclusion?"

0xcafecafe 8y ago
This is also one of my favorites. Not too difficult to put you off but not too easy as well. Just needs detailed thought with process of elimination of cases.
Lewton 8y ago
Reminds me of the joke Three logicians walk into a pub, the bartender goes "3 pints?" First logician goes "Maybe", second goes "Maybe", third goes "Yes!"
- mimimihaha 8y ago
  Haha i love it

a008t 8y ago

For those of you that are interested, there is a formal logic that can be used to reason about such problems, called Dynamic Epistemic Logic: https://eprints.soton.ac.uk/261816/1/EUMAS2.pdf https://eprints.soton.ac.uk/261816/1/EUMAS2.pdf A book chapter on the topic is available here: http://www.vub.ac.be/CLWF/SS/DELhandbookarticle.pdf http://www.vub.ac.be/CLWF/SS/DELhandbookarticle.pdf Course slides and other information can be found here: https://sites.google.com/site/thealexandrubaltagsite/teaching/dynamic-epistemic-logic-2017-2018 https://sites.google.com/site/thealexandrubaltagsite/teachin... It is a fascinating topic. Equipped with DEL, you can approach similar problems dealing with knowledge, belief, private and public announcements systematically.

mcrowson 8y ago

Answer: 22. You're wrong so he prepares your graves bringing the count to 22.

heptathorp 8y ago

It'd be funny if the puzzle was to count graves. Then you would answer 20. Either there are 20 and you're right, or there are only 18 so the caretaker digs 2 more for you and your friend, so you become right.

yogascribble 8y ago

I think I have a solution at day 2. At the start: A sees 12. A knows B can see 6 or 8. If 6, B knows A sees 12 or 14. If 8, B knows A sees 10 or 12. A knows B knows A sees 10 or 12 or 14. B sees 8. B knows A can see 10 or 12. B knows if A sees 10, A would know B sees 8 or 10. B knows if A sees 12, A would know B sees 6 or 8. B knows that A knows B sees 6 or 8 or 10. Day 1: A passes. B thinks, since A sees 10 or 12 he knows I see 6 or 8 or 10. If I saw 6, I would think he saw 12 or 14. A knows I see 6 or 8 or 10, so if he actually saw 14 he would know I see 6 and the answer is 20. A just passed, which means A does not see 14. B passes. Day 2: A thinks, B sees 6 or 8. If he saw 6 and thought I saw 12 or 14, then when I passed he would know I did not see 14. That would mean if he saw 6, I would have had to see 12 and he would have known the answer was 18. B just passed, which means B does not see 6. That means B sees 8. The answer is 20.

skate22 8y ago

The answer is: 19 + 5 % -2 If he says you got it wrong, the answer is 18, then you tell him that you wrote the answer in python If he says you got it wrong, the answer is 20, then you tell him you wrote it in javascript Thanks modulo!