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

by dnetesn • 8 years ago

76 81 8 years 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• 8 years 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.

sweezyjeezy3• 8 years 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.

OscarCunningham• 8 years ago

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".

falsedan2• 8 years ago

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…

4ndr3vv• 8 years ago

"Get it wrong, and neither of you ever leave. "

hav• 8 years ago

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.

pjmorris• 8 years 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.

n4r94• 8 years 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• 8 years 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• 8 years ago

Count the shadows during the day.

rimliu2• 8 years 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• 8 years 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• 8 years 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.

n4r94• 8 years ago

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.

joshumax• 8 years 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.

n4r94• 8 years 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...

jacobush• 8 years ago

Is this used by some cryptocurrency?

lucraft3• 8 years 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?

Zarel2• 8 years 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.

lucraft3• 8 years 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.

laszlokorte• 8 years ago

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?

duke-from-prima• 8 years 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• 8 years ago

No. There are no common statues.

owenversteeg2• 8 years 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• 8 years 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.

palotasb4• 8 years 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• 8 years 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.

owenversteeg2• 8 years 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?

benmmurphy2• 8 years ago

I have a solution to the puzzle in Rust:

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

laumars• 8 years 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.

palotasb4• 8 years ago

Guessing wrong gets you locked up forever.

rimliu2• 8 years ago

Buried. The captor says he is preparing graves.

JFFalcon• 8 years ago

If either of you guesses wrong, you both die.

benmmurphy2• 8 years 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.

mhandley2• 8 years 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• 8 years ago

She did not know that I knew that she knew that I could not see 20.

topmonk4• 8 years 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.

palotasb4• 8 years 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.

topmonk4• 8 years 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.

dooglius2• 8 years ago

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

mhandley2• 8 years 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.

dooglius2• 8 years 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.

n4r94• 8 years ago

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.

ggambetta2• 8 years 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• 8 years 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).

ggambetta2• 8 years 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.

Aardwolf• 8 years 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• 8 years ago

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.

palotasb4• 8 years 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.]

idrios• 8 years 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• 8 years ago

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

rhplus• 8 years 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.

mimimihaha2• 8 years 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• 8 years 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• 8 years 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!"

mimimihaha2• 8 years ago

Haha i love it

a008t• 8 years 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 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.

mcrowson• 8 years ago

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

heptathorp• 8 years 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• 8 years 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• 8 years 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!

The Logic Puzzle You Can Only Solve with Your Brightest Friend

Related Stories