Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

HosseinYousefi's blog

Infinity Hats Problem
By HosseinYousefi, 8 years ago, In English

There are infinite number of people, each one has a whether red or blue hat. Everyone can see everyone's hat but can't see their own. Is it possible that with a strategy, only a finite number of people guess their hat color wrong?

  • Vote: I like it
  • +48
  • Vote: I do not like it

Comments Comments (35)
| Write comment?
»
8 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Yes. The first person says "WHITE" if he sees even no of "WHITE" hats, otherwise he guesses "BLACK". This tells the other people exactly the color of their hats.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    First of all they guess simultaneously so they can't wait for the first person to guess his own. Second of all, how can someone say if there is even number of something when there are infinity of them.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -28 Vote: I do not like it

      My bad! Didn't pay attention to "infinite" and I tend to make mistakes understanding the question.

      → Reply
»
8 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Just use the axiom of choice! Too Simple!

→ Reply
»
8 years ago, # |
  Vote: I like it +79 Vote: I do not like it

Consider 2 color assignments. We can say they are equivalent if the assignments differ by a finite number of elements, since this relation is symmetrical, reflexive, and transitive. For each equivalence class, choose a representative assignment and have each person memorize their color from the representative assignment. When each person looks at the hats of everyone else, he will be able to determine the equivalence class. Each person will guess the color he memorized for the representative assignment. The set of guessed colors is in the same equivalence class as the actual assignment of colors, and by definition they differ by a finite number of elements i.e. a finite number of people guessed their hat color wrong.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

Other interesting variation of that problem. Now people are arranged in a line, so that i-th person sees (i+1)-th, (i+2)-th ... etc. (there is still an infinite number of people!). They guess in turns. Firstly, first guy tells a color, then second guy etc. Design a strategy so that at most one guy will tell incorrect color.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    obviously if there's someone who will tell incorrectly it is the first person, because he doesn't have any information/hints about his hat, so the first person should try to give hint for the other people to help them. so the strategy is that first person will say "Red" if the number of "Red" hats that he can see is odd, otherwise he will say "Blue" (just as if "Red" was 1 and "Blue" was 0 and the first person is telling the XOR of all hats)

    now, if the parity of the number of "Red" hats which the second person can see is different from parity of the number of "Red" hats which the first person can see then second person will know he is wearing "Red" hat, otherwise he is wearing "Blue" hat. the third person heard what the first person said and knows what is the color of second person's hat, using similar way he can tell the color of his own hat and so on for the following people.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Is here anybody who reads statements correctly :P? You're not the first person to miss the fact that there is an infinite number of guys, so you can't tell whether there is an even or odd number of red hats. However your solution works for a finite case, that's something.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it -18 Vote: I do not like it

        I didn't miss the fact that they are infinity, but I assumed a person can tell whether it's even or odd number of red hats even if the number of people is infinity, because I couldn't imagine the situation where a person is seeing infinite number of hats but not knowing the parity :D

        I will try to think of something else

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +20 Vote: I do not like it

          So, is there an even or odd number of natural numbers? What about natural numbers without without one (we remove one number, so parity should change, right?)? Is there even or odd number of prime numbers :P?

          Btw being familiar with tricks about axiom of choice is rather a prerequisite to solve that problem.

          → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -26 Vote: I do not like it
    Solution
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That only deals with the finite case.

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think I have a proof that this strategy doesn't exist O_o, It should be wrong but let me say it :)...

    Consider two different ways of coloring that the first person has white hat in them but our strategy says it's black...Now for the others our algorithm should say the same thing for both states of coloring, but these states have at least one difference and our strategy won't work in one of the states.(cause the algorithm said the same thing for all the persons behind this person and we don't have any information to recognize these states from each other).

    Also we know that we don't have anything to talk about the first persons' hat so we can consider that we always say it's white, now if we consider two states with black hat for the first person we can't do anything as said in the previous paragraph...

    Maybe I had some little mistakes but tell if there is some mistake that can't be fixed in my proof...

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        That was in your problem...

        He didn't say anything about colors in his statement :)

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I didn't kinda get your point, but it is true that there's no way we can tell anything about first person's hat, so our strategy needs to correctly determine colors of all guys except first. But no counterargument about some switching colors arises from that.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I took two ways of coloring hats and the first place they differs, with this condition that this person(their first difference) isn't the 1st person in the line...

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          If you change color of a hat of a person that is not the first person in a line that can change what first person is saying.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I took two states that the first person of both of them said the same guess and they were both wrong...so all the person behind the first difference had the same guess in the states...

            → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Why not tell us the solution since it's been 2 days without anyone solving it yet?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Too soon :)

              I first want to find my proof's bug and then think about the strategy...

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                so all the person behind the first difference had the same guess in the states

                No, because those people can see hats of people in front of them so every person will use information from hats in front of them and information from answers of people behind them and mix them in some strategy to get their answer.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  The first persons of both states guessed wrong so all of the others should guess their color right...

                  And they have all same colors behind the first difference so they have to say just their color...

                  So the first difference that have different colors can't say both right by using the others' information cause their were all the same.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  You just repeated your idea and I already replied to this :)

                  anyway, if your disproof is correct then it should be correct on finite number people case, but the finite variation has already solution which is described here

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Found my bug ;)

                  → Reply
»
8 years ago, # |
  Vote: I like it -15 Vote: I do not like it

There are infinite number of people

There aren't. Solved.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +61 Vote: I do not like it

Spoilers — revert changes to see the solution to variation I mentioned.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's not correct

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I am pretty sure it is :f

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Aah, I read it again, and it is! Sorry :) brilliant btw

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          is this magic or what? first when you wrote "It's not correct" Swistakk's comment suddenly had -10 votes, now after you wrote "it is correct" Swistakk's comment suddenly had 0 votes again!!

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            LOl! They trusted me too much maybe! I misread it somehow, sorry again Swistakk

            → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            ← Rev. 2   Vote: I like it +30 Vote: I do not like it

            There are already existing conspiracy theories about some "quickly downvoting cf mafia" ;)

            → Reply