9
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ your definition of a good interval invokes that of a neutral one. $\endgroup$ – JMP Mar 17 '16 at 12:39
  • $\begingroup$ 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. $\endgroup$ – Darío G Mar 17 '16 at 15:50
  • $\begingroup$ oh, okay then.. $\endgroup$ – JMP Mar 17 '16 at 15:52
  • $\begingroup$ why don't bad intervals then end with 2b,...,2b? $\endgroup$ – JMP Mar 18 '16 at 14:37
  • $\begingroup$ @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}$. $\endgroup$ – Darío G Mar 18 '16 at 14:57
6
+100
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.