Блог пользователя HosseinYousefi

Автор HosseinYousefi, 8 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +48
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

Just use the axiom of choice! Too Simple!

»
8 лет назад, # |
  Проголосовать: нравится +79 Проголосовать: не нравится

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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +30 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится -18 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +20 Проголосовать: не нравится

          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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -26 Проголосовать: не нравится
  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +30 Проголосовать: не нравится

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        That was in your problem...

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Too soon :)

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

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Found my bug ;)

»
8 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

There are infinite number of people

There aren't. Solved.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +61 Проголосовать: не нравится

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