# combinatorics on cyclic sequences

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.

• your definition of a good interval invokes that of a neutral one. – JMP Mar 17 '16 at 12:39
• The definition of good intervals includes at least two elements 2g before the first 1g1b, while the neutral intervals have only one element 2g and then 1g1b. – Darío G Mar 17 '16 at 15:50
• oh, okay then.. – JMP Mar 17 '16 at 15:52
• why don't bad intervals then end with 2b,...,2b? – JMP Mar 18 '16 at 14:37
• @JonMarkPerry If $k=1$, then a position $j$ is $2b$ iff $a_j=0$. Since an interval only has one zero at the end, then the element before is $1g1b$. for instance, if the interval ends with $(\ldots,1,0]$ and this 1 is $a_j$, then $U_{1,j}(1)=1$ and $U_{2,j}(1)=0$ (because you start the counting from the position $j$ until the next $0$, which is $a_{j+1}$. – Darío G Mar 18 '16 at 14:57

## 1 Answer

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$.
• counterexample checked! – Darío G Mar 26 '16 at 13:25