Some variations on an old puzzle


Here’s an old puzzle:

Everyone in the town of Erdosville has either blue eyes or brown eyes. However, Erdosville is cursed: anyone who can determine his or her own eye color to be blue will die the next midnight. Of course, Erdosville is a small and friendly community, and everyone sees everyone else every day. Naturally, there are no mirrors, and no one would ever discuss eye color. However, one day, a visitor stops by Erdosville. When he leaves, he announces to the entire community that he enjoyed his stay, but he noticed that at least one person in Erdosville has blue eyes.

Does this have any effect on the population?

Yes, it does. If there are n people in Erdosville with blue eyes, they will die n days later. (If you don’t see why, try to figure it out.)

It seems like a fairly weak puzzle to me though; the only purpose the visitor has is to start a counter. Exactly how strong is this counter-starting condition? Here are some variants (that I haven’t attempted to solve yet, but I don’t think they’re very difficult) that may perhaps shed some light on the question:

Suppose one person didn’t hear the announcement and that everyone knows that she misssed it. What is the effect in this case? Does it matter if she has blue eyes or brown eyes?

What if one person misses the announcement but gets told about it k days later (and everyone knows that)? Then what is the effect?

What happens if everyone is cursed so that as soon as a person can determine his or her own eye color to be either blue or brown then that person will die the next midnight? Do they need to be told that at least one person has blue eyes and at least one person has brown eyes?

What if everyone is only guaranteed to see everyone else once a week?

Does anyone have any other variants?

Advertisements

About Simon

Hi. I'm Simon Rubinstein-Salzedo. I'm a mathematics postdoc at Dartmouth College. I'm also a musician; I play piano and cello, and I also sometimes compose music and study musicology. I also like to play chess and write calligraphy. This blog is a catalogue of some of my thoughts. I write them down so that I understand them better. But sometimes other people find them interesting as well, so I happily share them with my small corner of the world.
This entry was posted in Uncategorized. Bookmark the permalink.

18 Responses to Some variations on an old puzzle

  1. grumf says:

    Does everyone know her eye color?
    I’m guessing all the blue will die on day (n) the brown will die on day (n+1).
    Have you tried solving the puzzle where you have 12 identical coins and 1 fake one and you need to find the fake coin using a balance and 3 measurements?

    • grumf says:

      The guy is not needed if there are at least 3 blue eyed people.

      • grumf says:

        Following that thought: if the number of blue eyed people is larger than 2, all blue eyed people die on the 3rd day rather than on day (n).

    • Simon says:

      The point is that a person knows everyone else’s eye color.
      Do you have proof?

      • grumf says:

        For population with 20 blues.
        1) From the POV of blue #1: theres definitely 19 blue eyes.
        2) From the POV of blue #1 about the POV of any other blue (n) : there are definitely 18 blue eyes.
        (blue #1 doesnt know his own color and blue (n) doesnt know his own color also).
        If you go around and apply the argument for everyone in the group then everyone will know that theres definitely at least 18 blue eyes.
        So for the starting condition everyone knows that theres at least 18 blue eyes and all the blue eyes will die on the 3rd time they sleep.

        • Anonymous says:

          Grumf, I think you are wrong, and blue-eyed people do in fact die on day n, not day 3. If we call the blue-eyes are A, B, C, etc., then the proof of this fact requires not just jumping into A’s perspective about what B (or C or D) thinks, but rather to A’s perspective about B’s perspective about C, then A’s perspective about B’s perspective about C’s perspective about D, and so on. It’s essentially an inductive proof, and the base case breaks down without the visitor.

          • Anonymous says:

            Try it for a population of 3 blues: everyone knows that everyone else knows that there is at least 1 blue eye.
            Then you dont need the visitor.
            You only need to jump perspectives once to establish what is the least amount of blue eyes that everyone must see.

            • Anonymous says:

              I’m the first anonymous poster again. Here’s why the visitor is necessary with three people: A, B, and C.
              Suppose there is no visitor. A sees that B and C have blue eyes, and assumes that he has brown eyes, since he doesn’t want to die. Now A thinks that B sees that A has brown eyes and C has blue eyes. A knows that B will then also assume that he (B) has brown eyes. A knows that B thinks that C will see two sets of brown eyes. However, without the visitor, this is entirely consistent with C having brown eyes. Once the visitor shows up, it is not.
              The main problem here is that A is assuming that he has brown eyes and looking from B’s perspective. Under this assumption, B assumes that he has brown eyes and looks from C’s perspective, who assumes that he has brown eyes and looks from D’s perspective, and so on. It seems counterintuitive, but by the end of the chain of assumptions, everyone is assumed to have brown eyes. I’m not sure this will make things any more clear, but here’s the formal mathematical proof:
              Problem: Prove by induction that if n people have blue eyes, they will die on the nth day.
              Base case: Suppose one person has blue eyes. After the visitor arrives, this person sees that no one else has blue eyes, thus he must have blue eyes. He dies immediately.
              Inductive step: Suppose that if n people have blue eyes, they will die on the nth day. Now suppose that n+1 people have blue eyes. Any one of them will see exactly n other people with blue eyes. If this person had brown eyes, the n people would die on day n. When this doesn’t happen, he knows that he must have blue eyes, and he (and everyone else) dies on day n+1. QED.
              Without the visitor, there’s no base case, and thus no proof.
              -Sly Si

              • grumf says:

                What you are telling me is that if there is a million blue eyes, is that people still dont know that there is AT LEAST 1 blue eye without the visitor telling them, which is absurd.
                Change blue -> humans, brown -> aliens. Now, are entire populations going to wonder if there are any human beings at all if they had never had mirrors?
                The only reason the visitor is introduced to the riddle is to take care of the case where there are less than 3 blue eyed people.

                • grumf says:

                  A, B, C – All Blue.
                  From A perspective:
                  1) A sees B, C. A knows: that there are 2 blue eyes.
                  2) A knows B sees C, so A knows B knows that there is 1 blue eye.
                  3) A knows C sees B, so A knows C knows that there is 1 blue eye.
                  From B perspective:
                  1) B sees: A, C. B knows: that there are 2 blue eyes.
                  2) B knows: C sees A, so B knows C knows that there is 1 blue eye.
                  3) B knows: A sees C, so B knows A knows that there is 1 blue eye.
                  From C perspective:
                  1) C sees: A, B. C knows: that there are 2 blue eyes.
                  2) C knows: B sees A, so C knows B knows that there is 1 blue eye.
                  3) C knows: A sees B, so C knows A knows that there is 1 blue eye.
                  You can establish it for a fact there there is at least 1 blue eye!

                  • Anonymous says:

                    The problem is that you need A to know that B knows that C knows there is at least one blue-eyed person. Without the visitor, here’s what A thinks:
                    I don’t want to die, so I should assume I have brown eyes unless (and until) this leads to a contradiction. So B is now seeing one blue-eye and one brown-eye. B thinks the same way as I do, so he will also assume he has brown eyes, even though I know this to be false. Thus B will think that C sees two brown-eyes. But this isn’t a problem.
                    However, when the visitor shows up, A thinks this:
                    B is now in trouble, because if his assumption were true, C would die right away. But C hasn’t died yet, so if my assumption is correct (that I have brown eyes), B should know now that his assumption is false and die. But B hasn’t died, so I can’t possibly have brown eyes.

                    • grumf says:

                      1. I have a feeling none of you is reading what I wrote because you constitute a majority and believe yourselves to be right.
                      2. “Thus B will think that C sees two brown-eyes. But this isn’t a problem.”
                      Correction: B will know that C sees one blue-eye.
                      3. Given an enormous population consisting of only blue eyed people, cant ANY single person in the population KNOW that there is AT LEAST one blue eyed person?

                    • Anonymous says:

                      Ignore #2. I didnt see the “A thinks”
                      There is still no need for A to think “about B thinking about C” in order to esablish a least amount of blue eyed people.

                    • Anonymous says:

                      In response to #1: Actually, all but one of the anonymous posts have been me, I’ve just forgotten to sign some of them so you know it’s the same person (perhaps I should get myself a userid–is that possible if I don’t have a livejournal?). And I’ll admit, I’ve just been skimming most of your posts because I think I understand the gist of your argument.
                      In response to #3: This is correct. However, what we actually need is “A knows that B knows that C knows that … knows that Z knows there is at least one blue-eyed person”. You’re only going to the “A knows that B knows” layer. If you try to follow A’s deduction (without the visitor) that he has blue eyes, you should find that it doesn’t work.
                      Also, if your argument is correct, couldn’t a brown-eyed person apply it to themselves and conclude that they have blue eyes? It doesn’t seem to depend on how many blue-eyed people the person sees, so I don’t see why this wouldn’t happen.
                      -Sly Si

  2. Revision; Dont they all have to die simultaneosly???
    Let X be the set of blue eyed people in Erdosville. There are n members of X. Each person has an associated “knowledge set”. The knowledge set defines what each member knows about every other member. We choose some arbitrary blue eyed person A and discover that his knowledge set consists of the following elements; ( n-1(how many people A knows have blue eyes from direct observation), n-2(the number of blue eyed people A knows every known blue eyed person can see, that is, given some other arbitrary person B, this number is the number of people A knows B knows have blue eyes), n-3( the number of blue eyed people A knows B knows every arbitrary C can see), n-3, etc) because there are n blue eyed people, the knowledge set of any arbitrary A before the visitor makes his announcement is the set (n-1, n-2, n-3, …, 0) assuming A does not include himself. Because the choice of A is arbitrary, the knowledge set just demonstrated is, in fact, the knowledge set of every member of X. This tells us that whatever our sample member A can determine through reasoning, every member must know (assuming every member can reason). After the visitor arrives, A knows that every member of X knows that there is at least one blue eyed person. Therefore, after the visitor makes his announcement, A must eliminate 0 from his knowledge set. This poses a problem. A knows there are at least n-1 blue eyed people, but this assumption leads to the inclusion of 0 in A’s knowledge set. Therefore, there must be more than n-1 blue eyed people, and so A must have blue eyes. Because every member of X knows what A knows, they all learn they have blue eyes simultaneously, and they must all die simultaneously. This happens on day 2 (when A discovers that there cannot be only n-1 blue eyed people, because if there were, someone would die, but no one does).
    Where did I make a mistake? Did I make a mistake?

    • Re: Revision; Dont they all have to die simultaneosly???
      ah, nevermind, i get it. They do die simultaneously, but on the nth day ( i see where i went wrong). Okay. Sorry.

  3. BTW
    So, what ended up happening with that course on Fourier Analysis?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s