The task of the gnomes and colorful hats

Hello, hello. I will offer you a problem that a friend of mine showed me yesterday.
Each gnome from the endless line is wearing either a blue or a red cap. Each gnome looks in the back in front of him, so 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 getting the caps.
On command, all dwarves should simultaneously name the color. Those who did not guess what kind of cap on them, in general, they do not guess.
Question: how can they come to an agreement so that only a finite number of gnomes cannot be guessed?

Those who are interested and who at the moment do not want to make an attempt to solve, please welcome under cat. The article will be a discussion of the problem and its “solution”. (I advise lovers of mathematics to try to solve).

Part 1/4. Reflections.

At first glance it seems that there is no solution and there can be no. In fact, the gnomes cannot exchange any information in any way. Moreover, since they are infinite, all gnomes are absolutely equivalent. Each of them sees an absolutely identical in essence picture - an endless line of his friends. Nobody can make any calculations, because 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 sacred properties of the sequence seen by the dwarf. The representation of blue caps with the number 1, and with the red with -1, the summation of a series in private sense in attempts to find a property that cannot change too many times in a sequence of partial sums. But it turned out to be absolutely useless.
Nothing helped, everything came up against the fact that all the gnomes were equal first in their turn, and at some point I boldly said: there can not be. I was absolutely sure.

Part 2/4. Author's solution.

I found it in the network. 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 relationship is obviously transitive, reflexive, and symmetric, so you can use it to break all possible sequences into classes. Differently: 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 the axiom of choice) - some specific sequence. These representatives of the gnome must know.
Things are easy: standing in a queue, any gnome can determine in which class the current (the one that is taking place) sequence lies. In fact, each gnome does NOT see only a finite number of caps, and therefore they have no effect on the belonging of a sequence to any class. In other words, the gnome can assume that all caps behind him (and him) are red, and recall the class to which the sequence belongs. It will be equivalent to the current one. Now the gnome will remember a 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 chosen representative (all dwarfs are the same) 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 imperfection in reasoning in order to defend my statement 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 it knows the same reason why many people criticize it - non-constructivity.
In short: the axiom of choice says that on any set of non-empty sets it is possible to 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 suggest such a function. Although the axiom says that it exists.
Maybe the point is this? Perhaps the gnomes cannot, in principle, equally choose a representative of each class? After all, there are many classes, as many as points on a straight line. That is, the function of choice exists, as it were, but it is impossible to agree on it.
But no, this assumption turned out to be useless. The fact is that in solving a choice axiom is not needed at all. Each class has the smallest sequence in the lexicographical order, for example, it can be taken as a representative.

Then I began to think about how the dwarfs can understand which class the current sequence belongs to. Will they need to go through all the classes for this and compare what the problem may arise with, because there will not be enough time to search through the continuum of classes, assuming that the thought takes non-zero time ...
But I will not confuse you too much, and already heaped it up. The fact is, I just deceived you. Who got caught? You cannot select the smallest class element in lexicographical order.
Take, for example, a class containing a sequence of all blue caps 1, 1, 1, 1, 1, 1 ... There will also be sequences in it:
-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 about any class - whatever sequence is the smallest, you can find the first unit in it and replace it with -1, getting even less. It turns out that such a minimum exists only in one of the classes - containing -1, -1, ... a sequence of all red caps.
Let's go back.

Part 4. Axiom of choice.

The question is: can we still do without it in this decision? Now we analyze.
What are our classes like? Let's represent all sequences by numbers from the segment [0; one]. We assume that the caps are the digits 0 and 1, and the sequence is the number 0, abcd ... in the binary number system. We will lose some of the sequences, because, for example, there are two:
0,011111 ... and 0,100000 ... set the same fraction 1/2. But it is not too scary, there are very few such collisions (only countable). But each number will correspond to some sequence, so this is an almost one-to-one correspondence between all the sequences from 0/1 and all the numbers in the interval [0; one].
What do our classes look like? Awful, every 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, the distance from which to x is less epsilon.
Moreover, if we choose representatives of each class, then they form a typical set that is not Lebesgue measurable. Proof of this fact I propose to read in a short article on Wikipedia. The Vitali set is constructed in a very similar way, and when proving the immeasurability of the word “for all rational numbers” (about shifts) should be replaced “for all fractions with denominators of the form 2 ^ n” (in the Vitali set, the numbers of one class differ by rational number, and for the final sum of negative powers of two, that is, for a fraction of the specified type).
At this point, the problem with collisions in the bijection, which I ignored a little higher, is jammed, since a countable set to add and subtract here and there on Lebesgue measurability does not affect.
Well, someone knows, and someone can read in the same article on Wikipedia that the construction of bounded sets without Lebesgue measure is always based on the axiom of choice. Consequently, the author’s decision is essentially based on this axiom, and without it is not true.
It turns out that our poor gnomes know that there is a choice function for class representatives (if they agree with the ZFC theory, of course), but they will not be able to choose these representatives, because it is impossible to describe this function.

Afterword.

Did I prove the infidelity of the author's decision? I think yes. The formulation of the task is how the gnomes agree. The necessity of the axiom of choice unequivocally says that there is no answer to the “how” in the decision and cannot be.
Is there a solution to the problem? To prove his absence is too difficult a task, and one can hardly think of something better than the equivalence of the gnomes and the lack of their ability to exchange information. For me, this is convincing enough. If someone comes up with something strict - please share.
Why is this all about? As I said, the readers of this hub, in my opinion, can be interesting. And in my turn, it is extremely interesting to discuss the task with the community. And yet, you can consider the article as practical (as far as it can be practical) and an accessible mini-review of the last letter in the abbreviation ZFC and related problems.
Have a nice day!