The task of the gnomes and colorful hats
Hello, habralyudi. I will offer you a puzzle that a friend of mine showed me yesterday.
For each gnome from an endless line, either a blue or red cap is worn. Each gnome looks in the back in front of the one standing in such a way that the first sees the caps of everyone except his own, the second sees everyone except himself and the first, and so on. Each dwarf knows only what he sees, his position in the queue, and what they all agreed on together before receiving the caps.
On command, all gnomes must simultaneously name the color. Those who have not guessed what kind of cap they have on them, in general, they do not guess thefrustration .
The question is: how do they agree so that only a finite number of gnomes are guessed?
Those who are interested and who at the moment do not want to try to solve, please welcome under cat. The article will be a discussion of the problem and its "solution". (For math lovers, I advise you to try and solve).
At first glance, it seems that there is no solution and cannot be. In fact, gnomes cannot exchange any information at all. Moreover, since they are infinite, all gnomes are absolutely equal. Each of them sees an absolutely identical picture in essence - an endless line of friends. No one will be able to make any conclusions or calculations, since the color of the cap on this particular gnome does not depend on what he sees.
The first thing I thought about was counting all the sticky properties of a sequence that a gnome sees. Representation of blue caps with the number 1, and red caps with the number -1, summing up the series in private senses in an attempt to find a property that cannot change too many times in the sequence of partial sums. But it turned out to be absolutely useless.
Nothing helped, everything rested on the fact that all the gnomes were equally the first in their turn, and at some point I boldly said: it cannot be. I was absolutely sure.
I found it on the net. The author says that he will use the axiom of choice.
Consider all possible sequences of caps. We call two sequences equivalent if they differ only in a finite number of positions. This relation is obviously transitive, reflexive and symmetrical, therefore, it is possible to break all possible sequences into classes with it. In another way: two sequences will belong to the same class if they differ only in a finite number of caps. Now, from each class we choose a representative (this can be done by virtue of the axiom of choice) - a specific sequence. Gnomes should know these representatives.
The thing is small: standing in line, any gnome can determine in which class the current (the one that has the place to be) sequence lies. In fact, each gnome does NOT see only a finite number of caps, and therefore they do not affect the belonging of a sequence to any class. In other words, the gnome can assume that all the caps behind him (and his) are red, and remember the class to which such a sequence belongs. It will be equivalent to the current one. Now the gnome will remember the representative of this class and name the color of the cap that would be on his head, if the current sequence coincides with the representative.
Voila. The selected representative (the same for all gnomes) and the current sequence belong to the same class, and therefore differ only in a finite number of positions.
Yes, such a turn of events upset me, and I had to look for an imperfection in my reasoning in order to defend my claim that there was no solution.
Of course, the first thing that attracts attention is the axiom of choice. The author emphasized it, and everyone who knows about her also knows the reason why many criticize her - unconstructiveness.
In short: the axiom of choice suggests that on any set of nonempty sets one can define a function that, for each set, will return some element belonging to it. The problem is that such a function may not be possible to build / describe. For example, considering all subsets of a line (the so-called hypercontinuum), it is impossible to offer such a function. Although the axiom suggests that it exists.
Maybe this is the case? Perhaps the gnomes cannot, in principle, equally choose the representative of each class? After all, there are many classes, as many as points on the line. That is, the selection function seems to exist, but it is impossible to agree on it.
But no, this assumption was useless. The fact is that in the solution the axiom of choice is not needed at all. In each class there is the smallest sequence in the lexicographic order, for example, it can be taken by a representative.
Then I began to think about how gnomes can understand which class the current sequence belongs to. Would they need to sort through all the classes and compare what the problem might arise with, because the continuum of time is not enough to sort through the continuum of classes, under the assumption that thought takes non-zero time ...
But I won’t confuse you too much, and already he has piled up. The fact is that I just deceived you. Who got it? You cannot select the smallest lexicographic element of a class.
Take, for example, a class containing a sequence of all the blue caps 1, 1, 1, 1, 1, 1 ... It will also contain the sequences:
-1, 1, 1, 1, 1, 1, 1, ...
-1, -1 , 1, 1, 1, 1, ...
-1, -1, -1, 1, 1, 1, ... which one to take, there is a lexicographically smaller sequence. Moreover, the same can be said of any class - no matter which sequence is the smallest, you can find the first unit in it and replace it with -1, getting an even smaller one. It turns out that such a minimum exists in only one of the classes - containing -1, -1, ... the sequence of all red caps.
Come back.
The question arises: is it possible to do without it in this decision? Now let's analyze.
What are our classes like? Let's represent all sequences by numbers from the segment [0; 1]. We assume that the caps are the numbers 0 and 1, and the sequence is the number 0, abcd ... in the binary system. We will lose part of the sequences, because, for example, these two:
0.011111 ... and 0.100000 ... define the same fraction 1/2. But this is not too scary, there are very few such collisions (only countable). But some sequence will correspond to each number, so this is almost a one-to-one correspondence between all sequences from 0/1 and all numbers of the segment [0; 1].
What do our classes look like on a segment? Horribly, each class is a countable dense set. This means that for any class A and numbers x from [0; 1], epsilon> 0 in class A will be a number whose distance from x is less than epsilon.
At this point, the problem of collisions in the bijection, which I ignored a little higher, is jammed, because the countable set back and forth add-to-take does not affect Lebesgue measurability.
Well, someone knows, but someone can read in the same Wikipedia article that the construction of bounded sets without Lebesgue measure is always based on the axiom of choice. Therefore, the author’s decision is essentially based on this axiom, and without it it is not true.
It turns out that our poor gnomes know that there is a choice function for representatives of classes (if they agree with the ZFC theorem, of course), but they will not be able to choose these representatives equally, since it is impossible to describe this function.
Did I prove the author’s infidelity? I think yes. The statement of the problem is how the gnomes agree. The need for the axiom of choice unequivocally says that the answer to the “how” in the solution is not and cannot be.
Is there a solution to the problem? To prove its absence is too complicated a task, and it is hardly possible to come up with something better than the equivalence of gnomes and their lack of the ability to exchange information. For me it is quite convincing. If someone comes up with something strict - please share.
Why is this all? As I said, the readers of this hub, in my opinion, can be interesting. And I, in turn, am extremely interested in discussing the problem with the community. And yet, you can consider the article as practical (as far as it can be practical) and an affordable mini-review of the last letter in the abbreviation ZFC and related problems.
Have a nice day!
For each gnome from an endless line, either a blue or red cap is worn. Each gnome looks in the back in front of the one standing in such a way that the first sees the caps of everyone except his own, the second sees everyone except himself and the first, and so on. Each dwarf knows only what he sees, his position in the queue, and what they all agreed on together before receiving the caps.
On command, all gnomes must simultaneously name the color. Those who have not guessed what kind of cap they have on them, in general, they do not guess the
The question is: how do they agree so that only a finite number of gnomes are guessed?
Those who are interested and who at the moment do not want to try to solve, please welcome under cat. The article will be a discussion of the problem and its "solution". (For math lovers, I advise you to try and solve).
Part 1/4. Reflections
At first glance, it seems that there is no solution and cannot be. In fact, gnomes cannot exchange any information at all. Moreover, since they are infinite, all gnomes are absolutely equal. Each of them sees an absolutely identical picture in essence - an endless line of friends. No one will be able to make any conclusions or calculations, since the color of the cap on this particular gnome does not depend on what he sees.
The first thing I thought about was counting all the sticky properties of a sequence that a gnome sees. Representation of blue caps with the number 1, and red caps with the number -1, summing up the series in private senses in an attempt to find a property that cannot change too many times in the sequence of partial sums. But it turned out to be absolutely useless.
Nothing helped, everything rested on the fact that all the gnomes were equally the first in their turn, and at some point I boldly said: it cannot be. I was absolutely sure.
Part 2/4. Author's solution.
I found it on the net. The author says that he will use the axiom of choice.
Consider all possible sequences of caps. We call two sequences equivalent if they differ only in a finite number of positions. This relation is obviously transitive, reflexive and symmetrical, therefore, it is possible to break all possible sequences into classes with it. In another way: two sequences will belong to the same class if they differ only in a finite number of caps. Now, from each class we choose a representative (this can be done by virtue of the axiom of choice) - a specific sequence. Gnomes should know these representatives.
The thing is small: standing in line, any gnome can determine in which class the current (the one that has the place to be) sequence lies. In fact, each gnome does NOT see only a finite number of caps, and therefore they do not affect the belonging of a sequence to any class. In other words, the gnome can assume that all the caps behind him (and his) are red, and remember the class to which such a sequence belongs. It will be equivalent to the current one. Now the gnome will remember the representative of this class and name the color of the cap that would be on his head, if the current sequence coincides with the representative.
Voila. The selected representative (the same for all gnomes) and the current sequence belong to the same class, and therefore differ only in a finite number of positions.
Yes, such a turn of events upset me, and I had to look for an imperfection in my reasoning in order to defend my claim that there was no solution.
Part 3/4. What's wrong.
Of course, the first thing that attracts attention is the axiom of choice. The author emphasized it, and everyone who knows about her also knows the reason why many criticize her - unconstructiveness.
In short: the axiom of choice suggests that on any set of nonempty sets one can define a function that, for each set, will return some element belonging to it. The problem is that such a function may not be possible to build / describe. For example, considering all subsets of a line (the so-called hypercontinuum), it is impossible to offer such a function. Although the axiom suggests that it exists.
Maybe this is the case? Perhaps the gnomes cannot, in principle, equally choose the representative of each class? After all, there are many classes, as many as points on the line. That is, the selection function seems to exist, but it is impossible to agree on it.
But no, this assumption was useless. The fact is that in the solution the axiom of choice is not needed at all. In each class there is the smallest sequence in the lexicographic order, for example, it can be taken by a representative.
Then I began to think about how gnomes can understand which class the current sequence belongs to. Would they need to sort through all the classes and compare what the problem might arise with, because the continuum of time is not enough to sort through the continuum of classes, under the assumption that thought takes non-zero time ...
But I won’t confuse you too much, and already he has piled up. The fact is that I just deceived you. Who got it? You cannot select the smallest lexicographic element of a class.
Take, for example, a class containing a sequence of all the blue caps 1, 1, 1, 1, 1, 1 ... It will also contain the sequences:
-1, 1, 1, 1, 1, 1, 1, ...
-1, -1 , 1, 1, 1, 1, ...
-1, -1, -1, 1, 1, 1, ... which one to take, there is a lexicographically smaller sequence. Moreover, the same can be said of any class - no matter which sequence is the smallest, you can find the first unit in it and replace it with -1, getting an even smaller one. It turns out that such a minimum exists in only one of the classes - containing -1, -1, ... the sequence of all red caps.
Come back.
Part 4. The axiom of choice.
The question arises: is it possible to do without it in this decision? Now let's analyze.
What are our classes like? Let's represent all sequences by numbers from the segment [0; 1]. We assume that the caps are the numbers 0 and 1, and the sequence is the number 0, abcd ... in the binary system. We will lose part of the sequences, because, for example, these two:
0.011111 ... and 0.100000 ... define the same fraction 1/2. But this is not too scary, there are very few such collisions (only countable). But some sequence will correspond to each number, so this is almost a one-to-one correspondence between all sequences from 0/1 and all numbers of the segment [0; 1].
What do our classes look like on a segment? Horribly, each class is a countable dense set. This means that for any class A and numbers x from [0; 1], epsilon> 0 in class A will be a number whose distance from x is less than epsilon.
It's easy to prove
Moreover, if we choose representatives of each class, then they form a typical set that is not Lebesgue measurable. I propose to read the proof of this fact in a short Wikipedia article. The Vitali set is constructed in a very similar way, and when proving the immeasurability of the word “for all rational numbers” (about shifts), you should replace “with all fractions with denominators of the form 2 ^ n” (in the Vitali set, numbers of one class differ by a rational number, but I have on a finite sum of negative powers of two, that is, on a fraction of the specified type). It is enough to take any number z from A, take its tail, starting with a digit corresponding to the power of two n such that 2 ^ n <epsilon / 10. And with this tail replace the tail of x. The resulting number and the number z belong to the same class and differ no more than by epsilon / 5.
At this point, the problem of collisions in the bijection, which I ignored a little higher, is jammed, because the countable set back and forth add-to-take does not affect Lebesgue measurability.
Well, someone knows, but someone can read in the same Wikipedia article that the construction of bounded sets without Lebesgue measure is always based on the axiom of choice. Therefore, the author’s decision is essentially based on this axiom, and without it it is not true.
It turns out that our poor gnomes know that there is a choice function for representatives of classes (if they agree with the ZFC theorem, of course), but they will not be able to choose these representatives equally, since it is impossible to describe this function.
Afterword.
Did I prove the author’s infidelity? I think yes. The statement of the problem is how the gnomes agree. The need for the axiom of choice unequivocally says that the answer to the “how” in the solution is not and cannot be.
Is there a solution to the problem? To prove its absence is too complicated a task, and it is hardly possible to come up with something better than the equivalence of gnomes and their lack of the ability to exchange information. For me it is quite convincing. If someone comes up with something strict - please share.
Why is this all? As I said, the readers of this hub, in my opinion, can be interesting. And I, in turn, am extremely interested in discussing the problem with the community. And yet, you can consider the article as practical (as far as it can be practical) and an affordable mini-review of the last letter in the abbreviation ZFC and related problems.
Have a nice day!