Infinity Hats Problem

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.

→ Ответить

rachitiitr

8 лет назад, # ^ |

-28

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

→ Ответить

RedNextCentury

8 лет назад, # ^ |

+99

And the hats are red and blue :D

→ Ответить

please_delete_account

8 лет назад, # |

+38

Just use the axiom of choice! Too Simple!

→ Ответить

King

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 лет назад, # ^ |

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.

→ Ответить

SuperMegaUltraEpicHacker

8 лет назад, # ^ |

-26

Solution

→ Ответить

zscoder

8 лет назад, # ^ |

That only deals with the finite case.

→ Ответить

8 лет назад, # ^ |

← Rev. 2 →

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 лет назад, # ^ |

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 →

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 лет назад, # ^ |

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 лет назад, # ^ |

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 лет назад, # ^ |

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

→ Ответить

8 лет назад, # ^ |

Too soon :)

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

→ Ответить

8 лет назад, # ^ |

← Rev. 2 →

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 →

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 лет назад, # ^ |

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 лет назад, # ^ |

Found my bug ;)

→ Ответить

Huyum_nik

8 лет назад, # |

-15

There are infinite number of people

There aren't. Solved.

→ Ответить

8 лет назад, # ^ |

→ Ответить

8 лет назад, # |

← Rev. 2 →

+61

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

→ Ответить

8 лет назад, # ^ |

It's not correct

→ Ответить

8 лет назад, # ^ |

+10

I am pretty sure it is :f

→ Ответить

8 лет назад, # ^ |

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

→ Ответить

8 лет назад, # ^ |

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

→ Ответить

8 лет назад, # ^ |

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

→ Ответить