|
This is probably the hardest puzzle that i've solved myself:
An infinite number of ppl are given either a black or a white hat. They can't see what colour hat they have on but they can see everyone elses. They cannot communicate with each other in anyway once they've been given the hats but they can devise a strategy before the game starts. Then, at a predetermined time, they all have to shout out the colour hat they think they have on [at the same time]. They win if only finitely many get it wrong.
There are no pissy tricks like "looking in a mirror" or sneaking round the "no communication" rule and we assume they can see all the the other ppl at once and perform any computations they might need to instantly.
right so if you don't know/believe the axiom of choice you'll have to come up with a solution i haven't thought of yet. You might have come across the axiom in one of it's many forms (Zorn's lemma, Well-ordering principle) at some point in a maths degree but otherwise, even if you look it up on wiki, you'll struggle to know how to use it. It (roughly) says that if you have any collection of sets, you can pick an element in each of them, equivalently it says you can "well order" any set (ie you can say x<y or y<x for any x not equal to y).
I was told this puzzle a while ago, but it's solution actually came up the other day in some proper maths i was doing in a really natural way. One thing that's pretty weird is that i don't think it's possible to come up with a strategy that works if we replace "only finitely many" with "less than n" for an arbitrarily large n
|
People don't have to shout out their hat color at the same time, right?
|
yes they do [have to shout at the same time]
|
How about everybody yells one color
|
what if i handed out the hats black white black white ... all the way up? then which ever you shout you're wrong. In fact what if you all shout one colour and i handed out all of them the other colour?
oh and you need a plan that works all the time, not just one that gives you a good chance of winning
|
I think what I'm proposing might count as a method of communication, but here's my first idea.
Arrange all the people in a line in any arbitrary order. First two people stand out in a separate line. The next person will look at the first two, and if there is a change of color in the line, he will stand right in between the two colors. If there is not, he will stand at the end of the line. In either case, the line will now be split between black and white, or is all of one color.
IE
If the line is WW, the guy will stand at the end, so the line is now WWB or WWW
If the line is WB, the guy will stand in between, so the line is now WWB or WBB.
Therefore there is always a clear division between the black hats and white hats.
Once the infinitely many people have gone into place (plausible because they can compute instantly?). Then the last person to go into the line will define the division between the two colors, and everyone else can just look at the other side of that division to find out what color their side is.
The only person that would not know what color his hat is would be the last guy.
|
this is what i said the first time i saw the puzzle but this comes under the (rather too vague) heading of not communicating at all.
imagine everyone's in a prison cell and all they can see is one little light for every person apart from you which is either on or off depending on the colour hat they have on.
by the well ordering principle you can assign everyone a number (or element of an indexing set if you want to go cardinals on it, the solution i know works for any cardinal)
|
Call two ways of matching hats to people equivalent if only finitely many people are assigned different colored hats.
This is an equivalence relation. Beforehand, the prisoners agree on a single element from each equivalence class using Choice.
QED ^^
|
well done, i'd hoped it'd take longer than that
places you might have seen it: a basis of any infinite dim'l vector space
|
Muirhead: i don't suppose you'd know any places i could read up on the algebraic geometry approach to ramification do you? all i can find is number theory books
|
Hm... I don't know quite what level of book you want. You might check out some sections of Liu's book on Algebraic Geometry and Arithmetic Curves as a start?
|
so it's for a postgrad reading group on galois thy that's sort of branched out a bit. That book looks pretty good. i don't really know a lot of alge geo but when ever i talk to my supervisor about what's going on in these rings i'm looking at he always starts drawing pictures and makes me feel i should get on it.
|
United States24758 Posts
On May 10 2009 11:25 Muirhead wrote:
Call two ways of matching hats to people equivalent if only finitely many people are assigned different colored hats.
This is an equivalence relation. Beforehand, the prisoners agree on a single element from each equivalence class using Choice.
QED ^^
Can you explain what that means.
|
|
|
for convenience label each of the ppl 1,2,3,... Now let a(i) be a sequence of 0's and 1's and we'll say that a(i)=0 if person i's hat is white, a(i)=1 if the persons hat is black.
For example a(i) is one way of giving out the hats a(1)=1 a(2)=0 a(3)=0 would be BWW
Let b(i) be the same as a(i) for a different way of handing out hats, so b(1)=1 b(2)=1 b(3)=1 would be BBB.
then we say a(i) "=" b(i) if and only if only finitely many of the ( a(i) - b(i) ) are not equal to 0.
(the collection of the x(i) which are "=" are the equivalence classes)
Now pick a list a(i), b(i), c(i),... so that a(i) is not "=" to b(i) or c(i) or d(i) etc and b(i) is not "=" to c(i) or ...
(forgive me for the implied countableness, (countable is a technical maths term))
now how ever i hand out the hats there will be a x(i) in the list such that x(i) is "=" to the way i hand out the hats. everybody shouts out the colour of hat they should have in x(i), and only finitly many will be wrong
|
United States24758 Posts
Forgive me for pointing out how inaccessible that explanation was, but I have no idea how that jargon results in people knowing what color to yell out.
|
On May 10 2009 12:29 micronesia wrote:Show nested quote +On May 10 2009 11:25 Muirhead wrote:
Call two ways of matching hats to people equivalent if only finitely many people are assigned different colored hats.
This is an equivalence relation. Beforehand, the prisoners agree on a single element from each equivalence class using Choice.
QED ^^ Can you explain what that means.
Think of the people with white hats as a subset of the people. If two subsets only differ by finitely many elements, then we group those two sets together (into a set of subsets of the people). This is our equivalence relation. There's some conditions you have to prove about equivalence classes, but in this case it's easy enough not to be worth mentioning.
In algebra, you can reduce a group with an equivalence class to the unique equivalence classes, for example, the integers by 0 mod p, 1 mod p, ..., p-1 mod p (or odds or evens if that's simpler) into p elements, hence the OP's solution motivated by n-dimensional vector spaces (where dividing the space by the equivalence class of lines is common).
edit: oops solution is simpler than i thought.
anyway, you have your equivalence classes of subsets. There are infinitely many, but that doesn't matter, and from each equivalence class, you choose one element, that is, one specific way of handing out hats. Since you've covered every equivalence class, any subset of the people will match to all but finitely many of one of the chosen elements.
When the hats are handed out, you can see everybody else's hat, and your own hat can only increase the number of possible wrong matches by 1, so you know equivalence class that particular hat distribution is in. Everyone now votes their according to what their representative element would have as a hat.
|
I'm not understanding this...if you hand out the hats to an infinite number of people... then the number wrong will be infinite... simply because the whole set is infinite. You would also never reach the time when everyone would call out what color they think there hat is...because you'd still be handing out hats..
and even if you did...even if you came up with a plan before hand that weeded out 99% of errors 1% of infinite is well infinite.... the continuum hypothesis be damned.
|
(Disclaimer: I'm not a mathematician)
I don't buy the equivalence relation thing. If we're allowed to apply "a = b if a(i) != b(i) for only a finite # of i" an infinite number of times (why not? everything else in this problem seems to be infinite  ), then everything breaks.
Also, if we just coin-flip for each hat, 50% of the guesses are going to be wrong no matter how they were derived?
|
i think I know how to do it by moving into lines going right or left based on the 2 hats in front of u
but it's too hard to explain lol and i can't put it into math terms cuz i dont know how
|
|
|
|
|
|
EPT
