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?
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?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
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.
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.
My bad! Didn't pay attention to "infinite" and I tend to make mistakes understanding the question.
And the hats are red and blue :D
Just use the axiom of choice! Too Simple!
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.
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.
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.
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.
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
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.
Video on TED-ed
That only deals with the finite case.
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...
That was in your problem...
He didn't say anything about colors in his statement :)
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.
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...
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.
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...
Why not tell us the solution since it's been 2 days without anyone solving it yet?
Too soon :)
I first want to find my proof's bug and then think about the strategy...
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.
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.
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
Found my bug ;)
There aren't. Solved.
:)
Spoilers — revert changes to see the solution to variation I mentioned.
It's not correct
I am pretty sure it is :f
Aah, I read it again, and it is! Sorry :) brilliant btw
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!!
LOl! They trusted me too much maybe! I misread it somehow, sorry again Swistakk
There are already existing conspiracy theories about some "quickly downvoting cf mafia" ;)