The Logic Puzzle You Can Only Solve with Your Brightest Friend(nautil.us)
nautil.us
The Logic Puzzle You Can Only Solve with Your Brightest Friend
http://nautil.us/blog/-the-logic-puzzle-you-can-only-solve-with-your-brightest-friend
84 comments
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
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).
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.
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.
> 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.
That doesn't break the puzzle at all. Odd days you take the option to answer while your friend agrees to always pass. Even days vice versa. By that interpretation it doubles the days to answer, but the process is identical.
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?
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?
Replying to myself, I think we can take this further.
I know she can see 6 or 8. She knows I can see 10 or 12. She knows that I know she can see 6, 8 or 10.
Given this information, we both know that the minimum number she can see that the other knows is 6. This allows us to both shortcut the process. We can both discard the first rounds that eliminate that she can see 2 or 4. The first round we need to play is the one where she can see 6.
So, in my first round, I'd give an answer if I could see 14. I don't give an answer, so she knows I don't see 14. We both already knew that, but it was the first round we could agree on, so that's where we synchronize.
After that, you just play out the rounds as in the proposed solution.
Edit: doesn't work: if she had actually seen 6 rather than 8, she'd have known I'd see 12 or 14, so she'd know I knew she would see 4 , 6 or 8. So you can't synchronize on 6 after all.
I know she can see 6 or 8. She knows I can see 10 or 12. She knows that I know she can see 6, 8 or 10.
Given this information, we both know that the minimum number she can see that the other knows is 6. This allows us to both shortcut the process. We can both discard the first rounds that eliminate that she can see 2 or 4. The first round we need to play is the one where she can see 6.
So, in my first round, I'd give an answer if I could see 14. I don't give an answer, so she knows I don't see 14. We both already knew that, but it was the first round we could agree on, so that's where we synchronize.
After that, you just play out the rounds as in the proposed solution.
Edit: doesn't work: if she had actually seen 6 rather than 8, she'd have known I'd see 12 or 14, so she'd know I knew she would see 4 , 6 or 8. So you can't synchronize on 6 after all.
I think your idea is pretty much the same as lucraft's below: https://news.ycombinator.com/item?id=17548391 and fails for the same reason.
But you wouldn't give an answer if you could see 14, would you? You wouldn't know whether she sees 4 or 6.
I don't think too much knowledge can be a problem, only applying the wrong algorithm to that data. I think the thing you're missing is that you can independently reduce the set of numbers of statues possibly seen by the other guy based on the number of passes and based on knowing the total and what you see. The first can be expanded gradually and it finally intersects at only one number by with the second set.
Say there was 1 million statues or 1 million + 2 statues, and you saw 456,892. Would it really be clear to her that you would pass 200,000+ times, even though you both know that you each had over 400,000 statues, respectively?
The answer given should work in this case, since the number of statues doesn't affect the principle of the problem. But obviously it doesn't work. Therefore, I don't see how it should work for the original problem either.
Edit: Or lets put it another way.
Let's say I saw 1,000,012 statues, and the total was 2,000,018, or 2,000,020. Wouldn't you be able to reduce this problem to the original? The number of possible statues that she/I see doesn't change, after all.
The answer given should work in this case, since the number of statues doesn't affect the principle of the problem. But obviously it doesn't work. Therefore, I don't see how it should work for the original problem either.
Edit: Or lets put it another way.
Let's say I saw 1,000,012 statues, and the total was 2,000,018, or 2,000,020. Wouldn't you be able to reduce this problem to the original? The number of possible statues that she/I see doesn't change, after all.
[deleted]
Or even another way.
Let's say instead of seeing statues, each prisoner was given a piece of paper that had an integer on it (ranging from -infinity to +infinity) and on your paper was written 12.
Would the problem be unsolvable? If so, what has materially changed?
Let's say instead of seeing statues, each prisoner was given a piece of paper that had an integer on it (ranging from -infinity to +infinity) and on your paper was written 12.
Would the problem be unsolvable? If so, what has materially changed?
What has materially changed is that there no longer are any situations where someone knows the answer instantly. The original puzzle only works because everyone has a non-negative integer and their sum is constrained to a finite number of possibilities. So someone who sees a number larger than the second-highest possible total knows that the value of the total is the highest possibility.
The key to understanding the puzzle is that knowing, knowing they know, knowing they know you know, etc. are increasing strengths of knowledge. You can always remove "knows" from the stack, but you can't easily add them (because how do you know they know?). Passing on a given day is the mechanism that introduces knowledge of infinite depth (because everyone knows they are neither freed nor dead and they all know they know they know ...) Because knowing the answer implies that they don't pass, observing a pass eliminates all possibilities where the answer is known (more precisely, it adds one depth of "knows" to the knowledge that that possibility isn't the case.)
The key to understanding the puzzle is that knowing, knowing they know, knowing they know you know, etc. are increasing strengths of knowledge. You can always remove "knows" from the stack, but you can't easily add them (because how do you know they know?). Passing on a given day is the mechanism that introduces knowledge of infinite depth (because everyone knows they are neither freed nor dead and they all know they know they know ...) Because knowing the answer implies that they don't pass, observing a pass eliminates all possibilities where the answer is known (more precisely, it adds one depth of "knows" to the knowledge that that possibility isn't the case.)
You learn that she knows that you don't have 19 or 20 statues, and she learns that you know that, etc.
She did not know that I knew that she knew that I could not see 20.
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.Yes, but there is some level of meta-knowledge that you're eliminating.
She sees there are 8 statues.
She knows that you see either 10 or 12.
She knows that you know that she sees either 8 or 6.
She knows that you know that she knows that you see either 10, 12 or 14.
She knows that you know that she knows that you know that she sees either 8, 6 or 4.
...etc.
That's why the solution takes 5 days, each day eliminates another level of meta-knowledge until you get to a point where you know how many statues the other must be seeing based on how many times they passed.
She sees there are 8 statues.
She knows that you see either 10 or 12.
She knows that you know that she sees either 8 or 6.
She knows that you know that she knows that you see either 10, 12 or 14.
She knows that you know that she knows that you know that she sees either 8, 6 or 4.
...etc.
That's why the solution takes 5 days, each day eliminates another level of meta-knowledge until you get to a point where you know how many statues the other must be seeing based on how many times they passed.
I don't care to figure out if this complicates any solution schema, but your Lemma 1 is wrong. If I can see 8 statues, then my friend can see anywhere from 12 to 20 statues --- at no point does the riddle say that we see 18 or 20 unique statues.
It's the imprecision in these sorts of riddles when told, but which expect extraordinary precision in the solver, that generally turns me off from the problem.
It's the imprecision in these sorts of riddles when told, but which expect extraordinary precision in the solver, that generally turns me off from the problem.
The problem is confusing. You are looking out on different sides of the graveyard, so you know there is no overlap in statues, and the caretaker informs you that the total number of statues is either 18 or 20. So you know your friend can only see either 6 or 8.
I agree it's not super well-phrased though.
I agree it's not super well-phrased though.
"Out of your friend’s window, which overlooks the opposite side of the graveyard, she can see eight."
The unique is (poorly) implied, imo.
The unique is (poorly) implied, imo.
Just to play the devil’s advocate: I imagined looking at the left side, and my friend was looking at the opposite side, ie, the right side.
If my Lemma 1 is wrong, then the solution proposed by the article is also incorrect, because it also assumes this.
I have a solution to the puzzle in Rust:
https://play.rust-lang.org/?gist=c56bd7d745ffcc90d59e4801e41...
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: 20This 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?"
"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?"
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!"
Three logicians walk into a pub, the bartender goes "3 pints?"
First logician goes "Maybe", second goes "Maybe", third goes "Yes!"
Haha i love it
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.
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.
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?
So what knowledge have you actually learned after the first round, that you can take forward into the second round?
> So what knowledge have you actually learned after the first round?
That your friend sees 2 or more, and your friend knows you see 18 or less. By itself, this is trivially deducable; but each day walks the limits closer to revela a fact that isn't trivial. You start the puzzle knowning that your friend can see either 6 or 8 statues, and each day you add a new fact about how many statues she can't see.
I'm more concerned that the problem as stated can be solved in 2 days: you say 18 on day one, then 20 on day two…
That your friend sees 2 or more, and your friend knows you see 18 or less. By itself, this is trivially deducable; but each day walks the limits closer to revela a fact that isn't trivial. You start the puzzle knowning that your friend can see either 6 or 8 statues, and each day you add a new fact about how many statues she can't see.
I'm more concerned that the problem as stated can be solved in 2 days: you say 18 on day one, then 20 on day two…
Judging from:
> [...] and so on, until you get it right or wrong. The caretaker cackles, “If you need me, I’ll be out preparing your graves.”
My impression is that once you have the wrong answer, you're not going to have another day.
My impression is that once you have the wrong answer, you're not going to have another day.
"Get it wrong, and neither of you ever leave. "
Therefore you say I see more than (y - 2) statues while he says morethan (x + 2) until you both repeat the same value.
You know you cannot lie so a simple iteration on inequalities is enough to find the right value.
This relies on your friend figuring out the linear addition scheme.
You know you cannot lie so a simple iteration on inequalities is enough to find the right value.
This relies on your friend figuring out the linear addition scheme.
Oh thanks, I missed this crucial caveat.
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.
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.
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.
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.
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.
Ah, nice. This is the answer I was looking for.
This bugged me too, the process works but they’re throwing away a lot of information at the start, which should mean it can be done faster.
I made another answer that works the same way but doesn’t throw that away, and it seems it’s possible to finish on Day 2.
I made another answer that works the same way but doesn’t throw that away, and it seems it’s possible to finish on Day 2.
Good question. I suspect the answer is something like "that they know that you know that they know that you know that they see at least one statue".
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.
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.
> 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.
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.
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.
> Out of your friend’s window, which overlooks
> the opposite side of the graveyard
Count the shadows during the day.
I took this statement:
'The caretaker tells you each, individually, that together you can see either 18 or 20 statues. '
as being:
'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
size(see_A union see_B) = 18 or 20
Very similar to the "Blue-Eyed Islanders" riddle: 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.
They should make it clearer in the introduction that there is no overlap between the visible statues from each side.
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.
Is this used by some cryptocurrency?
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...
I think this one is a lot harder: http://olivernash.org/2009/10/31/yet-another-prisoner-puzzle...
Much better explanation by Nick Berry: http://datagenetics.com/blog/december12014/index.html
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
A book chapter on the topic is available here: http://www.vub.ac.be/CLWF/SS/DELhandbookarticle.pdf
Course slides and other information can be found here: 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.
Course slides and other information can be found here: 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.
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?
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?
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.
> 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.
But by knowing that the total number is even in either case and by each one knowing that their own number is even, the odd numbers can be discarded anyway, right?
Yes, I only brought up the odd-number cases because lucraft did.
> 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.
The common knowledge at this point is that B sees between 6 and 10, so A knows B doesn’t see 5 or 4.
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.
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.
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.
-----------
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.
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 |
-----------
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 |
| Me Them || Them Me | Them Me |
--------------------------------------------------------------------------------------------
I have | 12 .. 8 || | 8 10 .. 12 |
They have | 8 ..10 12 || | 10,12 8 10 .. 6 8 |
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.
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.
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.")
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.")
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.
This, however isn't the quickest way so it would probably fail if your partner is optimizing.
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?
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?
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.
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.)
(Then unless you know who has the lower number, you're out of luck.)
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.
[deleted]
Can it still be solved if I generalize the question like this?
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.]
* 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.
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.]
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.
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.
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!
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!
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?
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?
No. There are no common statues.
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.
[edit]
ahhh, I missed the "get it wrong and you die" bit. Thanks for the clarification guys.
'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.
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.
If either of you guesses wrong, you both die.
[deleted]
Answer: 22. You're wrong so he prepares your graves bringing the count to 22.
> 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".