EPTwe assume they can see all the the other ppl at once
This assumption completely breaks the game. I can get down to 0-1 mistakes if you assume this. really hard puzzle - Page 2
| Blogs > drift0ut |
|
L
Canada4732 Posts
| ||
micronesia
United States24554 Posts
On May 10 2009 12:54 igotmyown wrote: 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. Hm... maybe it would be clearer if you could tell me what instructions you would give to a random person who needs to make a decision about what color to pick? | ||
|
igotmyown
United States4291 Posts
Example: the chosen member of the equivalence relation is all odd representatives have white hats. The equivalence class is subsets that differ from the odd numbers in finitely many ways. He is 5. He observes that the people wearing white hats are persons # 101, 103, 105, 107, ... No matter what he is wearing, this differs finitely many ways from the set odd people wear white hats. He chooses white since he's #5 and odd. And it's clearly an equivalence relation due to the finitely many differences criteria: Definition Let A be a set and ~ be a binary relation on A. ~ is called an equivalence relation if and only if for all a,b,c\in A, all the following holds true: * Reflexivity: a ~ a * Symmetry: if a ~ b then b ~ a * Transitivity: if a ~ b and b ~ c then a ~ c. | ||
|
odave
United Kingdom4 Posts
First person gets white hat Second person gets black hat ... We consider two assignments to be "equivalent" if there are only a finite number of people whose hat colour changes from assignment 1 to assignment 2. Using this equivalence test, we can split up all the possible assignments into "equivalence classes". An assignment is equivalent to every other assignment in its equivalence class, but is not equivalent to any assignment in any other equivalence class. We can do this because our equivalence test passes for an "equivalence relation" (see wikipedia for details). Using the axiom of choice (see wikipedia for details), we now pick one assignment from each of these equivalence classes, and everyone remembers which one we picked from each equivalence class (quite a lot to remember, as there will be an infinite number of these equivalence classes  ).That's the preparation stage. Now, to decide which colour to report... First, we decide which equivalence class the current assignment of hats to people is in. This is possible because there are only 2 possible assignments -- the one where we have a white hat and the one where we have a black hat -- and they are equivalent (and so will be in the same equivalence class). Now, using our infinite memory, we recall the particular assignment we picked out for this equivalence class (which we did in the last stage of preparation). The key here is that everyone will recall the same assignment. We then report the colour assigned to us in this assignment. Because everyone recalled the same assignment, the reported assignment is the same as the assignment we recalled. And the assignment we recalled was in the same equivalence class as the current assignment, which means that only a finite number of people reported the wrong hat colour. Tada! (Still don't buy it though) | ||
|
evanthebouncy!
United States12796 Posts
On May 10 2009 12:50 drift0ut wrote: 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 This makes sense, that's quite interesting problem haha. Let me explain it in a more basic terms so maybe non-math majors can comprehend it. | ||
|
numLoCK
Canada1416 Posts
| ||
|
Muirhead
United States556 Posts
Obviously you should fill your own math blog problems with more jargon evanthebouncy  . Then I might get a chance to answer them before tons of other people do. It would be nice if you occasionally posted some more difficult, technical, or less well-known problems given how quickly people are answering. | ||
|
evanthebouncy!
United States12796 Posts
First we'd like to understand what is equivalent class Equivalent class is a way that you can use partitioning a set. It is useful because it let us look at a big, maybe confusing set, in smaller pieces called partitions by separating the big set into equivalent classes. That's probably a lot of stuff so we start small: What is a partition? Say your set is a pizza, we can cut it into 4 slices, and that makes a "partition". In a more precise term, a partition is an action, or a result of that action, on a set such that you divide the set into subsets, and when you concatenate all the subsets, you get the whole set back, and yet no subsets intersects each other. Example: Set A = {1 2 3 4 5 6} A partition for set A can be: {1 2 3} {4} {5 6} {1 2 3 4 5 6} A partition for set A cannot be: {1 2 3} {4 6} (because concatenation does not reproduce the whole set back) {1 2 3} {3 4 5 6} (because 3 is shared among 2 subsets) More example: A partition on all natural numbers N can be: {1, 2, 3, 4, 5} {everything else} {1 3 5 7 ... odd numbers} {2 4 6 8 ... even numbers} Now let's move on to equivalence relation. Remember in partition we're trying to divide a set into subsets? An equivalence relation helps us do that by saying: element x and y are both in subset A if and only if x ~ y. The subset A is called an "Equivalent Class". "~" means "equivalent relation", and "x~y" reads "x is equivalent of y" Let's understand it. The definition for ~ include 3 of the following properties: reflexive: x~x is true symmetric: if x~y, then y~x is true transitive: if x~y, y~z, then x~z is true Examples of equivalent relations: 1) x~y if they have the same age. To check that 1) describe an equivalent relation, we'll check it against our 3 criterias: -reflexive, is x~x true? yes, x has the same age as x. -symmetric, is x~y implies y~x? yes, x has same age as y, then y has same age as x. -transitive, is x~y, y~z implies x~z? yes, x has same age as y, y has same age as z, then x has same age as z. Therefore 1) describes a valid equivalent relation. How do we use equivalent relation to form partitions? By construction. This is how: Say our set is A, and we wish to form a partition on A. We first pick an element a in A. Now we find all elements x such that a~x Think of it as finding all the x that are related to a. Put the a and all the x into a set, call it H_a We then pick an element b in A, but not in H_a Now we find all elements x such that b~x Put everything in H_b repeat the process until A becomes empty. Now I claim that H_a, H_b, .... H_n is a partition of A. Do you trust me? Probably not, so let's prove it: To satisfy the partition requirement, we must show 2 things, that concatenating all the subsets reproduce A, and no 2 subsets have intersections. Since we repeat the process until A becomes empty, then our H_a, H_b... must contains ALL the elements from A, therefore concactenating them back will give us all of A. To show that no 2 subsets have intersections though, that might take some work. Let's prove that by contradiction: Suppose some 2 subsets have an intersection, then pick an element x from that intersection. Now x is in both H_j and H_k (that's what it means by living in the intersection). By our definition, x is related to everything in H_j since x in H_j by our construction means x is related to j, and j related to everything. Then similarly, x is related to everything in H_k. It follows that everything in H_k is related to everything in H_j, meaning that H_k and H_j would've been in the same subset to begin with, forming a contradiction. So if you read through all that... let's try an example of forming such partitions by using equivalent classes: Let the room be full of people {a, b, c, d, e, f, g, h} Let a = 10 by age, and b = 11, c = 10, d = 11, e = 12, f = 10, g = 12, h = 11; We let our equivalent relation be x~y if x y same age. We pick an element from these people, let's say we picked b. We now find everybody that are related to b, namely all people of age 11, so b, d, h. We put all that into a subset H_b, and H_b = {b, d, h} Now we find an element that's not in H_b, but still in our set, we settled with a. Then find everybody related to a, {a, c, f} Name our set H_a = {a, c, f} Then find element e, and H_e = {e, g} So we've exhausted set A, and now we formed a partition: H_a, H_b, H_e or {a, c, f}, {b, d, h}, {e, g} Where H_a is an equivalent class, H_b is an equivalent class, H_e is an equivalent class. You should varify that this does indeed forms a valid partition. If you followed everything in this post you should get some idea what is a partition and what is an equivalent relation, and what is an equivalent class, and how they are used to construct each other. | ||
|
DeathSpank
United States1029 Posts
On May 10 2009 12:54 igotmyown wrote: 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 dont agree with the bold if there are infinitely many than there are an infinite number of errors. Just because you try to break up the infinite into chunks doesn't make it finite. | ||
|
drift0ut
United Kingdom691 Posts
then suppose i handed out hats with the pattern black white black white ... all the way up to infinity (so black hats on odd numbers white hats on even numbers), apart from finitely many places where i brake the pattern and give a white where it should be black (or visa verse). then you should shout black if in the pattern you'd have a black hat (in an odd number) or white if in the pattern you'd have a white hat. eg: bw bw bB bw bw in this case the guy in the middle with a capital B would shout white and be wrong, but there would be only finitely many of these. if that doesn't fit try a different pattern eg bbw bbw etc until you find a "pattern" that fits. I say "pattern" as it's not necessarily going to repeat its self it might be bw bbw bbbw bbbbw bbbbbw or something even more random. now eventually you'll find a pattern where only finitely many are wrong (after all you'll eventually find the exact pattern that i handed them out in, altho that won't know you which colour you've got on) and that's what you shout out. This is where i used the axiom of choice because we need to agree which order you are going to check the patterns in. | ||
|
Hamster1800
United States175 Posts
What's happening is that first the prisoners look at the equivalence classes mentioned before, where two sequences are equivalent if they differ in a finite number of places. The only axiom of an equivalence relation that isn't obvious is the transitive property, which you can see that if a differs from b in some set of locations, and b differs from c in some other set of locations, a can only differ from c in a location where either a differs from b or b differs from c, which is still a finite number. So then the axiom of choice guarantees the existence a choice function, that is if we have an equivalence class, we can plug it into the function and get a single element that is in that class. So the prisoners need to agree on a choice function beforehand. The key observation here is that seeing all but one hat determines the equivalence class of hats. So then what each prisoner does is he determines the equivalence class that the sequence of hats is in and plugs that class into the choice function. Then every prisoner will get the same sequence of hats out, since they agreed on a choice function beforehand, call it g(i). Then person i will guess g(i) for their hat color. Now if a(i) is the actual sequence of hats, we know that a(i) and g(i) are in the same equivalence class, so they differ in only a finite number of locations, which means that only a finite number of people got it wrong. | ||
|
DeathSpank
United States1029 Posts
On May 11 2009 00:23 drift0ut wrote: the way i got it was if i handed out all black hats apart from finitely many white hats it would be easy as everyone would shout black and only finitely many would be wrong. Or if i handed out all white apart from finitely many black it would be easy again as you'd shout out white and only that finite number with black hats would be wrong. then suppose i handed out hats with the pattern black white black white ... all the way up to infinity (so black hats on odd numbers white hats on even numbers), apart from finitely many places where i brake the pattern and give a white where it should be black (or visa verse). then you should shout black if in the pattern you'd have a black hat (in an odd number) or white if in the pattern you'd have a white hat. eg: bw bw bB bw bw in this case the guy in the middle with a capital B would shout white and be wrong, but there would be only finitely many of these. if that doesn't fit try a different pattern eg bbw bbw etc until you find a "pattern" that fits. I say "pattern" as it's not necessarily going to repeat its self it might be bw bbw bbbw bbbbw bbbbbw or something even more random. now eventually you'll find a pattern where only finitely many are wrong (after all you'll eventually find the exact pattern that i handed them out in, altho that won't know you which colour you've got on) and that's what you shout out. This is where i used the axiom of choice because we need to agree which order you are going to check the patterns in. thats not finite you're going to break the pattern an infinite number of times. | ||
|
Jonoman92
United States9101 Posts
I read some of the posts explaining the answer... but I'm not that intelligent I guess... I mean assuming there is no pattern to the way the hats are distributed, and they can't hear the answer of the other prisoners then there is no way there can only be a finite number of incorrect answers. | ||
|
Blyf
Denmark408 Posts
Edit: By the way, big thanks to EvanTheBouncy for explaining the math | ||
|
flag
United States228 Posts
if each prisoner is randomly given either a black hat or a white hat, then the types of hats other's wear has no effect on their own, and since they can not communicate, they can do no better than guess randomly at their own hat. clearly on average half the prisoners would be wrong, and half of an infinite amount is still infinite. i assume the problem meant worst case, and if so that is even worse since there is no strategy that would GUARANTEE that even one prisoner is correct, even if it is infinitely likely. this problem just shows that if you bury yourself in jargon that you don't understand you can prove anything you want and no one will be able to find a fault in your logic because it is nonsensical. | ||
|
Muirhead
United States556 Posts
| ||
|
georgir
Bulgaria253 Posts
especially the second part of this "solution" seems absolutely impossible. they can't have "pre-arranged" which member to chose for infinitely many equivalence classes - it would have required infinitely long time. they can't possibly go with a general rule like "chose the blackest set" or something, because this would not be defined for all equivalence classes. also there is this interesting paradox - assuming that they do have a "winning" strategy, does it matter if any specific person decides to alter that strategy by always saying "white" for himself? their strategy would've resulted in a finite number of differences before this alteration, so the new strategy would clearly also result in a finite number of differences. so it is still "winning". so any person can just say "white", and it wouldn't matter at all. yet clearly, if infinitely many people do this, they break their strategy. all in all, i don't think this kind of math makes any sense :p | ||
|
gondolin
France332 Posts
On May 13 2009 15:03 Muirhead wrote: Haha... the funny thing is that while you are right that each prisoner has 1/2 probability of surviving, still only finitely many will die. Infinity is strange... this problem is basically the probability-theory version of the existence of non-measurable sets (look up Banach-Tarski paradox). Another way to state this is that if you look at a finite subset of people, then only half of them will survive. However when you look at an infinite number, only finitely many will not survive. That only means that the function Cardinal is not continuous on P(N)=2^N (with the tychonoff topology). But this is very easy to see, if you have a sequence (X_n) where X_i \subset N, then you can define the inferior limit X_inf=\cup_{k >= 0} \cap_{l >= k} X_l and the superior limit X_sup=\cap_{k >= 0} \cup_{l >= k} X_l then X_inf is a subset of X_sup, and we say that X_n -> X if X_inf=X_sup=X. Now if X_n=[0,n], X_n->N, but if X_n=[n,2n], X_n-> \emptyset. So you have two exemples of sets with n elements converging to completely different things. | ||
|
gondolin
France332 Posts
On May 13 2009 16:42 georgir wrote: especially the second part of this "solution" seems absolutely impossible. they can't have "pre-arranged" which member to chose for infinitely many equivalence classes - it would have required infinitely long time. Well if we suppose that the function choosing the hats is constructive (ie in the constructible Godel universe), there is an explicit axiom of choice (because there is an explicit well ordering), so the choice of a representative is constructive (ie given by an explicit formula). Of course in practise you can't look at an infinite number of hats, much less find a decreasing sequence for this well ordering... | ||
|
flag
United States228 Posts
On May 13 2009 15:03 Muirhead wrote: Haha... the funny thing is that while you are right that each prisoner has 1/2 probability of surviving, still only finitely many will die. Infinity is strange... this problem is basically the probability-theory version of the existence of non-measurable sets (look up Banach-Tarski paradox). shouldn't the banach-tarski paradox, which assumes the axiom of choice, disprove the axiom of choice? if you reach a contradiction then one of your assumptions is false. the B-T paradox is a contradiction because after each transformation the volume remains constant, yet after all transformations the volume has doubled. | ||
| ||
