Proving after some minutes nobody will change her marker

Question

$2017$ people are sitting around a table each of them has a blue and a red marker but each of them like one of the colors of markers. in each moment all people put their favorite marker on the table at the same time. if the favorite color of somebody is not as like as two people who are sitting next to him or her that person will change the marker. prove after some minutes nobody will change her marker.

I apologize because not clarifying.@gandalf61 nicely mentioned rules, therefore, I just copy them:

1)In the initial state, everyone puts down their red or blue marker at random.

2)In each round of changes, a person will only change their displayed marker if the markers displayed by the people on either side of them are both the opposite color to their own displayed marker. Thus if a person displays Blue they will only change to Red if both people on either side of them are displaying Red. In all other cases, they continue to display Blue.

3)All changes in each round take place simultaneously.

I tried to solve it using induction. I assumed if there are $n$ person sitting around the table which $n$ is odd after some minutes they won't change any marker and I tried to prove it is also true for $n+2$ people but I cant prove $n+2$ person can change their marker in a way that they achieve the last situation of $n$ people which there won't be any more changes (if we don't care about two new people)

please share your ideas in comments and write an answer even if your solution isn't complete. thanks!

Answer 1

First, here is my interpretation of the rules:

1. In the initial state, everyone puts down their red or blue marker at random (I think the "favourite colour" thing is irrelevant and confusing).
2. In each round of changes, a person will only change their displayed marker if the markers displayed by the people on either side of them are both the opposite colour to their own displayed marker. Thus if a person displays Blue they will only change to Red if both people on either side of them are displaying Red. In all other cases they continue to display Blue.
3. All changes in each round take place simultaneously.

Then we can draw the following conclusions:

1. A person who is part of a contiguous block of 2 or more markers which are all the same colour will never change their marker. Let's call a block of 2 or more markers all the same colour a "static block" and a block of 1 a "singleton".
2. A sequence of singletons that is bordered on each side by a static block can only get shorter. For example

...BBRBRBRR... -> ...BBBRBRRR... -> ....BBBBRRRR...

3. So the number of singletons gets smaller in each round of changes until it reaches zero unless there are no static blocks around the table in the initial state. For example, in a table of 4 we could start with BRBR, which then changes to RBRB, which then changes back to BRBR etc.

The final step (not difficult !) is to show that there must be at least one static block in the initial state of a table with 2017 people.

Answer 2

I apologize in advance for my messy notation.

Ah, I understand the question. Consider a coloring the vertices of $C_n$ red and blue and call this coloring $\chi_0$. We now construct a sequence of colorings in the folowing way: at time $i$, for any $v\in C_n$, if $\chi_{i-1}(v-1)=\chi_{i-1}(v+1)=red$ yet $\chi_{i-1}(v)=blue$ (all addition is modulo $n$), then $\chi_i(v)=red$. Similarly, if $\chi_{i-1}(v-1)=\chi_{i-1}(v+1)=blue$ yet $\chi_{i-1}(v)=red$, then $\chi_i(v)=blue$. In other words, a vertex will flip it's color if it disagrees with both of its neighbors. Now, what you'd like to prove is that no matter what $\chi_0$ was, there is some time $t$ for which $\chi_t=\chi_{t+1}$.

Now, this is false in general, since if $n$ is even, $\chi_0$ could alternate around the cycle and the process won't ever stop. But the key is that $n$ is odd. In particular, there must be some vertex $v$ with $\chi_0(v)=\chi_0(v+1)$.

Now for just a bit of terminology: A cyclic interval $I\subseteq[n]$ is said to be

1. monochromatic if all vertices in $I$ have the same color,
2. non-trivial if $|I|\geq 2$,
3. maximal under a coloring $\chi$ if $I=\{v,v+1,\dots,v+r\}$ where $\chi(v)\neq\chi(v-1)$ and also $\chi(v+r)\neq\chi(v+r+1)$.

Now, let $\mathcal{I}_t$ denote the collection of all monochromatic, non-trivial, maximal intervals under $\chi_t$ and let $N_t=\sum_{I\in\mathcal{I}_t}|I|$. Notice that every pair of intervals in $\mathcal{I}_t$ are disjoint. Furthermore, if $v\in I$ for some $I\in\mathcal{I}_t$, then $v$'s color will never change after this step. In particular, no interval in $\mathcal{I}_t$ can every shrink when building $\mathcal{I}_{t+1}$. It suffices to show that there is some $t$ for which $N_t=n$; if this is the case, then then $\chi_t=\chi_{t+1}$, so the coloring has stabilized.

Now, suppose that $N_t\neq n$; I claim that $N_{t+1}\geq N_t+1$. If this is the case then we're done. By the earlier remark, we know that $\mathcal{I}_0\neq\varnothing$, so we also know that $\mathcal{I}_t\neq\varnothing$ and since $N_t\neq n$, there is some $v\in[n]$ which is not in any interval in $\mathcal{I}_t$. We can, in fact, find such a $v$ and an interval $I\in\mathcal{I}_t$ so that $v-1\in I$. Also, wlog, we may assume $\chi_t(v)=red$ and $\chi_{t}(v-1)=blue$. Now, consider $v+1$. We can't have $\chi_t(v+1)=red$ or else $v$ would be contained in some interval in $\mathcal{I}_t$. Thus, $\chi_t(v+1)=blue$, so we know that $\chi_{t+1}(v)=blue$. Since $\chi_{t+1}(v-1)=\chi_t(v-1)=blue$, we know that $v$ is part of an interval in $\mathcal{I}_{t+1}$, so we must have $N_{t+1}\geq N_t+1$.