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.



combinatorics on cyclic sequences

> 
> ***Answer:*** *No this is not true.*
> 
> 
> 


For $m=5$, a counter example is: $(0, 2, 0, 2, 0, 2, 1, 2, 1, 1, 1, 0, 1, 2, 0)$. In this case we have:
$$\begin{align}
U(1) &= \left(\begin{array}{rrrrrrrrrrrrrrr}
0 & 0 & 0 & 0 & 0 & 4 & 4 & 3 & 3 & 2 & 1 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0
\end{array}\right) \\
U(2) &= \left(\begin{array}{rrrrrrrrrrrrrrr}
0 & 0 & 0 & 4 & 4 & 5 & 5 & 4 & 4 & 3 & 2 & 1 & 1 & 0 & 0 \\
1 & 2 & 1 & 3 & 2 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 0
\end{array}\right) \\
U(3) &= \left(\begin{array}{rrrrrrrrrrrrrrr}
0 & 4 & 4 & 5 & 5 & 5 & 5 & 4 & 4 & 3 & 2 & 1 & 1 & 0 & 0 \\
2 & 4 & 3 & 4 & 3 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 2 & 2 & 1
\end{array}\right) \\
U(4) &= \left(\begin{array}{rrrrrrrrrrrrrrr}
4 & 5 & 5 & 5 & 5 & 5 & 5 & 4 & 4 & 3 & 2 & 1 & 1 & 0 & 0 \\
4 & 5 & 4 & 4 & 3 & 4 & 3 & 3 & 2 & 2 & 2 & 2 & 3 & 3 & 2
\end{array}\right) \\
U(5) &= \left(\begin{array}{rrrrrrrrrrrrrrr}
5 & 5 & 5 & 5 & 5 & 5 & 5 & 4 & 4 & 3 & 2 & 1 & 5 & 4 & 4 \\
5 & 5 & 4 & 5 & 4 & 5 & 4 & 4 & 3 & 3 & 3 & 3 & 5 & 5 & 4
\end{array}\right) 
\end{align}$$


Each $U(k)$ has only $14$ entries $\geq k$. 


To elaborate a bit: 


* For $m\leq4$ the statement in your question is true, as can be checked by complete enumeration of all cases.
* For $m=5$ if you mod out cyclic permutations there are precisely 20 counter examples:
$$\{(1, 1, 1, 1, 0, 2, 0, 2, 0, 0, 2, 0, 2, 1, 2), (1, 1, 1, 1, 0, 2, 0, 2,
0, 0, 0, 2, 2, 1, 2), (1, 1, 1, 1, 0, 2, 0, 0, 2, 0, 2, 0, 2, 1, 2), (1,
1, 1, 0, 1, 2, 0, 0, 2, 0, 2, 0, 2, 1, 2), (1, 1, 1, 0, 2, 1, 0, 2, 0,
0, 2, 0, 2, 1, 2), (1, 1, 1, 0, 2, 1, 0, 0, 2, 0, 2, 0, 2, 1, 2), (1, 1,
1, 0, 0, 2, 0, 2, 0, 2, 1, 2, 0, 1, 2), (1, 1, 1, 0, 0, 2, 0, 2, 0, 2,
1, 0, 2, 1, 2), (1, 1, 1, 0, 0, 2, 0, 2, 0, 2, 0, 2, 1, 1, 2), (1, 1, 1,
0, 0, 2, 0, 0, 2, 2, 0, 2, 1, 1, 2), (1, 1, 0, 1, 2, 2, 1, 2, 2, 2, 0,
0, 1, 0, 0), (1, 1, 2, 1, 2, 2, 2, 2, 0, 1, 0, 1, 0, 0, 0), (1, 0, 1, 0,
1, 2, 1, 0, 2, 1, 2, 2, 2, 0, 0), (1, 0, 1, 0, 1, 0, 1, 2, 2, 1, 2, 2,
2, 0, 0), (1, 0, 1, 0, 1, 2, 1, 2, 2, 2, 0, 1, 2, 0, 0), (1, 0, 1, 0, 1,
2, 1, 2, 2, 2, 2, 0, 1, 0, 0), (1, 0, 1, 0, 1, 2, 1, 2, 2, 2, 0, 2, 1,
0, 0), (1, 0, 1, 0, 1, 2, 0, 1, 2, 1, 2, 2, 2, 0, 0), (1, 0, 1, 2, 1, 2,
2, 2, 0, 1, 2, 0, 1, 0, 0), (1, 0, 1, 2, 1, 2, 2, 2, 2, 0, 1, 0, 1, 0,
0)\}$$
* I would expect that there counter examples for all $m\geq5$.


