4 ms·

My first idea is to think of this as the following game. Initially we consider all words uncolored and I start by picking an initial set of red words that can c

My first idea is to think of this as the following game. Initially we consider all words uncolored and I start by picking an initial set of red words that can color any infinite binary sequence in red. Then you get to take away one of my words and make it blue. After that I get to pick replacement words from the remaining uncolored words to fix my set. Rinse and repeat. I start with { 0, 1 } which will obviously do. You take - I guess without loss of generality - my 0. I pick 00 and 01 as replacements and end up with { 00, 01, 1 } which will work again. You take away my 01, I replace it with 010 and 011 and { 00, 010, 011, 1 } will still work, I guess, but it is certainly becoming less obvious. In general I will pick x0 and x1 as replacements if you take x away which will allow me to still color x, I just have to choose between x0 and x1 depending on the following bit. If I am not mistaken, you will have to take away an infinite set of words from me in order to prevent me from being able to color any infinite binary sequence in red, if you take only finitely many, I will be left with a set of red words that still works. My guess is now that if you take away that infinite set in order to stop me, you will accidentally assemble a set of blue words that will be able to color any infinite binary sequence blue. Unfortunately I do not have the time right now to properly think this through. I am also not too confident because I do not clearly see how being allowed to have the first word in the wrong color comes into play. On the other hand, maybe, maybe you need my 1 for sequences starting with one or something like that. EDIT: Just had an additional thought, this might actually work. If you take my 0, then you can not also take my 1 later on or you will end up with { 0, 1 }. If you take 01, then you can not also take 10 later. So you always have to take one of my two latest replacements and leave the other one to me forever. We will build complementary sets, you have 0, I have 1, you have 01, I have 10, you maybe 011, I 010, ... Now it seems quite plausible that this will work out and we end up with two complementary set that both can color all infinite binary sequences in [mostly] a single color.

marblebot 3y ago
The flaw with the final conclusion is this counterexample: 0, 00, 000, 0000, … are all mapped to red 1, 11, 111, … are all mapped to blue Neither set can construct all infinite binary sequences because red cannot construct infinite 1s, blue cannot construct infinite 0s.
- danbruc 3y ago
  I have thought a bit more about this since. Arrange all words in a rooted binary tree with the empty word Ɛ at the root and each vertex w having color χ(w) and children w0 and w1. Each cut [1] through the tree yields a set of words that can be used to cover all infinite binary sequences. Therefore, if there is a monochromatic cut, then we are done. To obstruct a monochromatic cut of color A, there must be a monochromatic obstructing path of color B from the root all the way down to infinity. To obstruct red and blue cuts, we need a red and a blue obstructing path, and you gave an example. So additional work is required to show that the task is also possible if the coloring contains a red and a blue cut-obstructing path. [1] With cut I mean a set of vertices where no vertex in the cut is a descendant of any other vertex in the cut. Informally, repeatedly pick a vertex in the tree and remove the subtrees rooted at its children, the leaves of the remaining tree are the cut.

marblebot 3y ago

The flaw with the final conclusion is this counterexample: 0, 00, 000, 0000, … are all mapped to red 1, 11, 111, … are all mapped to blue Neither set can construct all infinite binary sequences because red cannot construct infinite 1s, blue cannot construct infinite 0s.

danbruc 3y ago
I have thought a bit more about this since. Arrange all words in a rooted binary tree with the empty word Ɛ at the root and each vertex w having color χ(w) and children w0 and w1. Each cut [1] through the tree yields a set of words that can be used to cover all infinite binary sequences. Therefore, if there is a monochromatic cut, then we are done. To obstruct a monochromatic cut of color A, there must be a monochromatic obstructing path of color B from the root all the way down to infinity. To obstruct red and blue cuts, we need a red and a blue obstructing path, and you gave an example. So additional work is required to show that the task is also possible if the coloring contains a red and a blue cut-obstructing path. [1] With cut I mean a set of vertices where no vertex in the cut is a descendant of any other vertex in the cut. Informally, repeatedly pick a vertex in the tree and remove the subtrees rooted at its children, the leaves of the remaining tree are the cut.