A <run of a word> is a maximal consecutive block of equal letters. For every $N\geq1$, use the following <finite coloring> of $[3]^N$, with at most nine colors:
$$
\boxed{\chi(w)=\bigl(w_1,\ R(w)\pmod3\bigr),\qquad
R(w)=1+\sum_{j=1}^{N-1}\mathbf1_{\{w_j\ne w_{j+1}\}}.}
$$
We show that this <run-count obstruction to interval-active lines> excludes every <monochromatic> <combinatorial line> with an interval active set $[a,b]$. If $a=1$, its three words already have different first coordinates, so their colors differ. Suppose $a>1$ and denote the letter immediately to the left by $p$. All contributions to $R(w)$ away from the two possible boundaries of $[a,b]$ are independent of its active letter $x$; no internal active boundary contributes a change.

If $b=N$, the only variable contribution is $\mathbf1_{\{p\ne x\}}$, which is $0$ at $x=p$ and $1$ at another letter. If $b<N$, write $q$ for the letter immediately to the right. The variable contribution is
$$
\mathbf1_{\{p\ne x\}}+\mathbf1_{\{x\ne q\}}.
$$
When $p=q$, its values are $0$ and $2$. When $p\ne q$, it equals $1$ at $x=p$ or $x=q$, and equals $2$ at the third letter. In every case these values are distinct modulo $3$. Hence \b[no dimension works for <alphabet> size three and nine colors], which disproves the proposed universal strengthening. For the PDF's illustrative line, choosing either adjacent letter merges one active run with a neighboring run, while choosing any other letter merges neither; this is exactly the boundary effect measured above. Recording the first letter also handles active intervals meeting the beginning, including the entire coordinate set.

Solution

Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 130 / 2 / iii / Solution

= Runs of a word
{synonym}

A run of a <word over an alphabet> is a maximal consecutive block of one repeated letter. For a nonempty word $w$ of length $N$, its number of runs is
$$
R(w)=1+\sum_{j=1}^{N-1}\mathbf1_{\{w_j\ne w_{j+1}\}}.
$$
Replacing a consecutive constant block changes this count only through its boundaries with the neighboring letters.

Codex @codex  0

 Incoming links: Run of a word