Given $m\geq 1$, let $I=(a_1,\ldots,a_{3m})$ be a sequence such that $I$ contains exactly $m$ zeros, $m$ ones, and $m$ twos.
Given $i=1,2$ and $j\leq 3m,k\leq m$ we can define $$U_{i,j}(k)=\text{number of $i$'s before finding $k$ zeros, starting from position $j$}.$$
(moving to the right, in a cyclic way)
For instance, for the sequence $(0,2,1,1,0,2)$, we would have $U_{1,2}(1)=2,U_{1,6}(2)=2$ (here is necessary to move to the beginning to continue counting) and, in total (using a matrix notation),
$$U(1)=\begin{bmatrix}U_{i,j}(1)\end{bmatrix}=\begin{bmatrix}0 & 2 & 2 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 1\end{bmatrix}$$
$$U(2)=\begin{bmatrix}U_{i,j}(2)\end{bmatrix}=\begin{bmatrix}2 & 2 & 2 & 1 & 0 & 2\\ 1 & 2 & 1 & 1 & 1 & 2\end{bmatrix}$$
Question: Is it true that for all such sequence there is $k\leq m$ such that at least $3m$ of the coefficients $U_{i,j}(k)$ satisfy $U_{i,j}(k)\geq k$?
At first, I thought that it was enough to take either $k=1$ or $k=m$, which are cases that I understand very well, but the sequence $(0,0,1,2,2,0,2,1,1)$ only works when $k=2$.
My first atempt was that for a fixed $k$, the position $j$ was $2g$ (too good) if both $U_{1,j}(k)\geq k$ and $U_{2,j}(k)\geq k$, $2b$ (too bad) if both where $<k$, and $1g1b$ otherwise. Then, if we define an "interval" to be a subsequence starting immediately after a zero and ending with the next zero, one can measure the "goodness" of the sequence by measuring how good or bad is each interval.
It turns out that for $k=1$ we have:
- Bad intervals have the form: $(1g1b,1g1b,\ldots,1g1b,2b)$ and the "sum" will be $-2$
- Good intervals have the form: $(2g,\ldots,2g,1g1b,\ldots,1g1b,2b)$ and the sum is at least $+2$ and depends on the number of elements that are $2g$ at the beginning.
- neutral intervals: $(2g,1g1b,\ldots,1g1b,2b)$ and the sum is zero.
However, I do not know how to extend this idea, or how to solve the general question.
