Ok that makes sense in a situation where there is a finite number, but with an infinite number of hats, can't you have an infinite number of mismatches (say you define rbrb alternating as your class. If the actual hat order is brbr alternating consistently, then that's an infinite number of mismatches. Aside from that, how can he first dwarf count the number of mismatches when the line of hats goes on forever? (Not taking into account range of vision...) My initial thought was something more like the pitch solution another person presented.

@EFrog "brbr" will be in another "class". Notice that sequences in the class differ by a finite number of elements. That is, you can count the differences and the first dwarf does exactly that. All dwarves can deduce the sequence and the representative of the sequence. Infinite mismatches within a class are not allowed by definition.

How do the other dwarfs know which class and which representative the first dwarf is using?

@AE There is one representative for a class. Remember, the members of each class differ from the representative by only a finite number of elements and each possible sequence belongs to a single class. The dwarves deduce the class because each one sees an infinite part of the infinite sequence. The only thing, a dwarf cannot do on their own is to deduce the difference between the current sequence and the representative.

The classes are constructed such that each possible sequence can only belong to a single class, have I got that right? What if sequence X differs from class-representative Y in one way and differs from class-representative Z in another way? How do we deduce which class to put it in?

@AE It is not possible by definition. Since each sequence belongs to a single class and each class contains only sequences that differ from the representative by a finite number of elements. If X differs from Y and Z by a finite number of elements, then Y and Z differ from each other by a finite number of elements, thus Y and Z are in the same class.

I need more coffee. ;) youtube.com/watch?v=MqBNSMbEzI0 So each class must differ from every other class by an infinite number of elements? Any two sequences which differ from one another by a finite number of elements are in the same class? Is that right?

@AE Exactly. By definition this is the main constraint when building the classes.

aaaargh! If I'm ever in this situation I'm going to go with the high-versus-low-voices as per Habeeb's answer. :)

@AE :D I must appreciate your infinity profile pic, though. Careful when working with infinity. A lot of mathematicians have gone mad after studying infinity.

So there are an infinite number of classes as well? Each of which differs from every other class by an infinite number of differences? That's a lot of infinity right there.

@AE As differences between classes are of infinite length, there is an infinite number of possible distances, which means there is an infinite number of classes.

I guess in the spirit of contrariness I'd like to know how a dwarf processes the infinite sequence (finding the classes and mismatches) in a finite amount of time :-) . Good thing there was no time limit in the stated question.

How do we know a collection of classes exists that satisfies the criteria you suggest?

@CarlWitthoft Why in the same way a dwarven population reaches infinite numbers. Guess they've had a lot of time to evolve their brains into. They've also developed infinite sewing machines.

(It occurs to me that even the single class you proposed does not satisfy your criteria: there are not a finite number of elements in the class "alternating red and blue with finitely many mistakes".)

@dmg If the partition is through a prefix of fixed size (say, 20) then the first dwarf's announcement doesn't contain any information about dwarves after the 20th. Something about your answer is fishy!

@DanielWagner You realize, that giving a full example, when talking about infinity is not quite possible?

The dwarfs have to agree a choice function for the set of equivalence classes, don't they? I'm not certain, but I suspect that since it's consistent with ZF that the reals have no well-order, then this is really difficult to do. The Axiom of Choice, loosely speaking, says that there exists a choice function, but that doesn't help all the dwarfs agree in advance which one they're going to use. This is also ignoring the infinite amount of "looking at hats and thinking" each would have to perform before answering, but I like the answer despite the practical difficulty.

@SteveJessop Assuming dwarves can work with infinite data, they technically can choose a member of the infinite set of sequences within a class.

@SteveJessop The possible sequences have a well defined order.

@dmg: well, different orders of infinity. The set of equivalence classes is uncountable, while the set of dwarfs is countable. But sure, if they have the means for one dwarf to select a choice function and communicate it to the others then they're good to go. I suspect (haven't proved) that communication needs to be by some means other than ZF-based mathematics.

Btw, note that "infinitely alternating red and blue, with a finite number of non-alternating hats in the first 20 elements" is not a class of the equivalence relation you originally defined.

@dmg I'm not asking for a full example. Just a reason to believe there is one.

@DanielWagner Take a look at the end of the answer.

@SteveJessop Take a look at the end of the answer.

@dmg Okay, I get it now. Just one mistake left, I believe: you say, "There are an infinite number of classes, each containing a finite number of elements.", but this is not true of the equivalence classes you define at the end. Each class has infinitely many elements. And I'm not so sure about your "choice of representative" comment, but I'm okay with having a choice function that the dwarves can agree on.

@DanielWagner Yeah, you are right. Fixed.

Consider the binary digits of pi: 0 is red and 1 is blue. Now, consider the equivalence class of this sequence in your scheme. It contains in particular members of the form, "N zeroes followed by the remaining digits of pi". There are infinitely many distinct such sequences, because pi has infinitely many 1 digits (otherwise it would be rational). Which of these members is lexicographically smallest? There isn't one: each is less than or equal to the previous. This is the difficulty with making the choice.

... now, you might be about to say, "just choose pi as the representative". But why pi? Why not pi+1/2? Why not p+1/4? Why not pi-1/8? They're all in the same class since they all differ from pi at only one position. How do the dwarfs agree, for all possible classes of real numbers, which representative to use?

@SteveJessop Within a class, there is an ordering. And that is it. I don't know why you are trying to put real numbers in the problem, as each sequence maps to an integer, not a real number.

@dmg: this may be where you're mistaken. There are uncountably many possible sequences of hats on the dwarfs, not countably many. So each sequence does not map to an integer.

So, just like Daniel I'm happy for the dwarfs to have a choice function, I enjoy the answer. I just think it's worth acknowledging that this is what they need to do, since there's no very simple such choice function.

Also, " the sequence is infinite, and differences are finite, there exists an infinite subsequence, that can uniquely define the class of the sequence." -- nope. For any sequence A, consider the set of sequences a(n), each defined as equal to A except at position n, where it differs. There is no infinite subsequence that all these sequences have in common, and yet they're all in the same equivalence class as A.