November 16th, 2008
Hint: think AC (axiom of choice).
Pages: 1 2
This entry was posted
on Sunday, November 16th, 2008 at 3:02 am and is filed under Math, Riddles.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
November 16th, 2008 at 2:12 pm
I’ve never studied AC formally (only read about it on wikipedia and mathworld), but my proposed solution made me think of it even before seeing your hint so I’m hoping I’m on the right track
—– SPOILER – possible solution below —–
We’ve solved the riddle if we can find two sets of infinite bit-vectors, called “Zero” and “One”, such that:
1. Zero and One are disjoint and their union contains all possible infinite bit-vectors.
2. For each vector in Zero, flipping one bit produces a vector in One.
3. For each vector in One, flipping one bit produces a vector in Zero.
If we can find two such sets, then the infinite men will agree on these sets before the task begins.
When it begins, the first guy sees the vector of all the hats ahead of him in line. He yells “white” if the vector is in Zero, or “black” if the vector is in One.
Every other guy knows all the bits in the vector except his own (the previous by hearing, the next by seeing). Also, he knows whether the vector is in Zero or in One. Due to properties 2 and 3 of the sets Zero and One, this is enough to determine the missing bit.
Now, to prove the existence of these 2 sets:
At first this seemed grim to me because both sets are of the same cardinality as R: infinite bit vectors are isomorphic to real numbers between 0 and 1, and both sets contain infinite vectors that are isomorphic to irrational numbers.
However, maybe the axiom of choice saves us.
For each infinite bit vector v, define Bubble(v) as the set of all vectors reachable from v by flipping a finite number of bits.
Obviously there are infinite disjoint bubbles. Using AC, we choose one vector to represent each bubble, and define Zero_0 to be the set of all representatives chosen.
Then we continue in the following manner:
One_0 = {all vectors one bit away from vectors in Zero_0}
Zero_1 = {all vectors one bit away from vectors in One_0}
One_1 = {all vectors one bit away from vectors in Zero_1}
…
Zero_k = {all vectors one bit away from vectors in One_k-1}
One_k = {all vectors one bit away from vectors in Zero_k}
…
And finally:
Zero = union Zero_0, Zero_1, …
One = union One_0, One_1, …
Unless I’m wrong, I think it can be shown (though I don’t feel like formulating a proof right now) that these sets fulfill the requirements I set above.
December 23rd, 2008 at 9:04 pm
A more simple way of saying it is as follows:
once the set of all representatives is chosen, and given the real vector v, v is different from its representative by a finite number of bits. the man can say Zero or One depending on the parity of the number of flipping.
And another little comment (about the original riddle and the new one): the number of possible hat colors could be even more than Aleph0. The hats could be organized in any set with a “+” and a “-” operations (any group + some more). Once a man knows the “Sum” of all the hats in front of him B, and the “Sum” of all the hats in front him including him A, he can calculate the “Difference” (A – B) giving his hat color. The algorithm will still work. Ofcourse you would like the men to be able to say-out-loud the color, so that’s quite reduces the options to Aleph0 or finie sets.
December 24th, 2008 at 12:24 am
Nadav,
I don’t understand your phrase “any group + some more”.
For each cardinal A, if you have a group G of cardinality A, then the solution works. I mean that you don’t need anything more than a group. Disagree?
On another note, it remains to show that for each cardinal A, there is a group of cardinality A.
December 24th, 2008 at 12:32 am
“Some More” = There are sets, which aren’t groups, that will do too (for example, the the set of naturals with operations + and -).
It refered your comment in the “Some Trivial Extensions” where it seemed to me that you meant that only a cardinality of Aleph 0 will work, which is wrong (take for example the group of reals)
December 24th, 2008 at 1:47 am
Oh, I see. I thought you meant that you put an extra condition on a group for it to work.
Of course you are right then (I used the aleph 0 example in the post to avoid cluttering the riddle with too many extra side-notes, I did not mean it is the only example).
What about the second part? Given a cardinal A, is there a group of cardinality A?
More specifically, I wonder if there is a subgroup of R of cardinality aleph 1.
Any thoughts?
December 24th, 2008 at 2:00 am
Actually, there is a group of every cardinality A:
The Free Group, over the set A.
its cardinality is sup(A^n | n
December 24th, 2008 at 2:16 am
Actually, there is a group of every cardinality A:
The Free Group, over the set A.
its cardinality is sup(A^n | n smaller than omega) = A
Now, take a subset of R of cardinality aleph1.
The free group generated by it (with the regular addition or multiplication in R) is a subgroup of R with cardinality aleph 1.
December 24th, 2008 at 2:43 am
Nadav – Cool answer!
April 20th, 2010 at 12:54 pm
Impressive blog, many thanks for discussing this post