5 ms·

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, s

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.
  - thechao 8y ago
    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.
    - another_one_off 8y ago
      "Out of your friend’s window, which overlooks the opposite side of the graveyard, she can see eight." The unique is (poorly) implied, imo.
      - thechao 8y ago
        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.
    - topmonk 8y ago
      If my Lemma 1 is wrong, then the solution proposed by the article is also incorrect, because it also assumes this.
    - mfoy_ 8y ago
      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.
  - grraaaaahhh 8y ago
    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.
palotasb 8y ago
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.
- topmonk 8y ago
  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.
  - deleted 8y ago
    [deleted]
  - topmonk 8y ago
    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?
    - yorwba 8y ago
      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.)
dooglius 8y ago
You learn that she knows that you don't have 19 or 20 statues, and she learns that you know that, etc.
mhandley 8y ago
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.
- dooglius 8y ago
  But you wouldn't give an answer if you could see 14, would you? You wouldn't know whether she sees 4 or 6.
- n4r9 8y ago
  I think your idea is pretty much the same as lucraft's below: https://news.ycombinator.com/item?id=17548391 https://news.ycombinator.com/item?id=17548391 and fails for the same reason.

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.
- thechao 8y ago
  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.
  - another_one_off 8y ago
    "Out of your friend’s window, which overlooks the opposite side of the graveyard, she can see eight." The unique is (poorly) implied, imo.
    - thechao 8y ago
      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.
  - topmonk 8y ago
    If my Lemma 1 is wrong, then the solution proposed by the article is also incorrect, because it also assumes this.
  - mfoy_ 8y ago
    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.
- grraaaaahhh 8y ago
  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.

palotasb 8y ago

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.

topmonk 8y ago
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.
- deleted 8y ago
  [deleted]
- topmonk 8y ago
  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?
  - yorwba 8y ago
    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.)

dooglius 8y ago

You learn that she knows that you don't have 19 or 20 statues, and she learns that you know that, etc.

mhandley 8y ago

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.

dooglius 8y ago
But you wouldn't give an answer if you could see 14, would you? You wouldn't know whether she sees 4 or 6.
n4r9 8y ago
I think your idea is pretty much the same as lucraft's below: https://news.ycombinator.com/item?id=17548391 https://news.ycombinator.com/item?id=17548391 and fails for the same reason.