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".
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
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?
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 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.
"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?"
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 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…
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.
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.
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.
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
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.
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 |
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.
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.")
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.
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.
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.]
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.
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.
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.
[+] [-] ggambetta|7 years ago|reply
> 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".
[+] [-] Aardwolf|7 years ago|reply
[+] [-] skrebbel|7 years ago|reply
[+] [-] BoiledCabbage|7 years ago|reply
[+] [-] mhandley|7 years ago|reply
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?
[+] [-] mhandley|7 years ago|reply
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.
[+] [-] palotasb|7 years ago|reply
[+] [-] dooglius|7 years ago|reply
[+] [-] dmurray|7 years ago|reply
[+] [-] benmmurphy|7 years ago|reply
https://play.rust-lang.org/?gist=c56bd7d745ffcc90d59e4801e41...
[+] [-] mimimihaha|7 years ago|reply
"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?"
[+] [-] Lewton|7 years ago|reply
Three logicians walk into a pub, the bartender goes "3 pints?"
First logician goes "Maybe", second goes "Maybe", third goes "Yes!"
[+] [-] 0xcafecafe|7 years ago|reply
[+] [-] heptathorp|7 years ago|reply
[+] [-] sweezyjeezy|7 years ago|reply
So what knowledge have you actually learned after the first round, that you can take forward into the second round?
[+] [-] falsedan|7 years ago|reply
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…
[+] [-] CJefferson|7 years ago|reply
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.
[+] [-] OscarCunningham|7 years ago|reply
[+] [-] pjmorris|7 years ago|reply
[+] [-] talltimtom|7 years ago|reply
[+] [-] davweb|7 years ago|reply
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|7 years ago|reply
[+] [-] n4r9|7 years ago|reply
They should make it clearer in the introduction that there is no overlap between the visible statues from each side.
[+] [-] a008t|7 years ago|reply
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.
[+] [-] lucraft|7 years ago|reply
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|7 years ago|reply
> 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.
[+] [-] idrios|7 years ago|reply
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.
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.
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. So Day 5 I know I have 12 and he has 8.[+] [-] owenversteeg|7 years ago|reply
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.
[+] [-] palotasb|7 years ago|reply
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|7 years ago|reply
This, however isn't the quickest way so it would probably fail if your partner is optimizing.
[+] [-] StavrosK|7 years ago|reply
[+] [-] unknown|7 years ago|reply
[deleted]
[+] [-] palotasb|7 years ago|reply
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.]
[+] [-] yogascribble|7 years ago|reply
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|7 years ago|reply
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!
[+] [-] duke-from-prima|7 years ago|reply
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|7 years ago|reply
[+] [-] jonahrd|7 years ago|reply
[+] [-] rhplus|7 years ago|reply
[+] [-] laumars|7 years ago|reply
[edit]
ahhh, I missed the "get it wrong and you die" bit. Thanks for the clarification guys.
[+] [-] benmmurphy|7 years ago|reply
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.
[+] [-] JFFalcon|7 years ago|reply
[+] [-] palotasb|7 years ago|reply
[+] [-] unknown|7 years ago|reply
[deleted]