For a positive integer $n$ I would like to construct long sequences consisting of 0, 1 and 2's such that for any two subsequences consisting of $n$ consecutive elements the number of 0's , 1's or 2's are different. Since there are $\binom{n+2}{2}$ different triples of nonnegative integers summing up to $n$ such a sequence has length at most $\binom{n+2}{2}+n-1$. For $n\leq 3$ it is possible to construct such sequences of this length: $$\begin{eqnarray} n=1&:& 012\\ n=2&:& 0112200\\ n=3&:& 011122200012 \end{eqnarray}$$ For $n\geq 4$ however I am unable to construct such sequences nor proving that there does not exist one. For given $n$ what is the maximal length of such a sequence? How can we construct it? I would be grateful for both the cases where $n$ is small as well as the asymptotics $n\rightarrow \infty $.
-
4$\begingroup$ An exhaustive search shows that for $n = 4$ there is no such sequence of length 18. There are almost optimal sequences of length 17, for example 00111122220000121, which is missing only a 'one 0, one 1, two 2' pattern. $\endgroup$– Mateusz KwaśnickiCommented Apr 27, 2017 at 20:29
-
2$\begingroup$ I'd like to call this The Lawrence Welk Problem ("a one and a two..."). $\endgroup$– Gerry MyersonCommented Apr 27, 2017 at 23:05
-
2$\begingroup$ An SMT solver quickly finds the best possible for $n=4$ is length 17, the best possible for $n=5$ is length $22$, an example being $2022101000222221111100$. $\endgroup$– Robert IsraelCommented Apr 28, 2017 at 0:58
-
2$\begingroup$ No, for $n=6$ the maximal length is $30$, an example being $112122220200001011112120201011$. $\endgroup$– Robert IsraelCommented Apr 28, 2017 at 1:08
-
2$\begingroup$ Doesn't seem to be any known sequence: oeis.org/search?q=3%2C7%2C12%2C17%2C22%2C30 $\endgroup$– Mateusz KwaśnickiCommented Apr 28, 2017 at 7:19
2 Answers
Here is a sketch of a proof that there are no such complete sequences for $n>4$.
Consider the graph where the vertices are the triples of nonnegative integers that sum to $n$ and construct an edge between two vertices when one can get from one to the other by incrementing one element and decrementing another. This graph looks like a triangle tiled by smaller triangles, in particular it is planar, so two paths cannot cross without intersecting. A solution of the original problem induces a hamiltonian path on this graph.
Now look at the extreme vertices of the triangle $(0,0,n)$, $(0,n,0)$, and $(n,0,0)$. In the original problem, a path of length n that starts or ends at one of these points must end or start at the opposite edge. As the induced path cannot cross itself, if the three vertices are all on a path, they must occur adjacent to each other, so the path looks like wlog $*0^n1^n2^n*$. This means that two sides of the triangle are occupied so neither the prefix nor the suffix can be longer than $(n-1)$, and if $n>4$ there are more than $2n-2$ elements that don't lie on the two edges.
ADDED: I have translated this problem into a somewhat annoying javascript toy. This makes it somewhat easier to see the structure in Robert Israel's solutions. I am fairly convinced (but still cannot prove) that the size of the optimal solution grows quadratically, and I would not be surprised if the optimal solution covered all but a linear in $n$ number of combinations.
It is perhaps equally natural to consider sequences wrapping around cyclically, like a de Bruijn sequence. In that case there is a simple reason why it won't work for $n=3$.
Clearly 000111222, or cyclically $$\begin{eqnarray*} 0 & \,0\,0 & 1\\ 2&&1\\ 2&2&1\end{eqnarray*}$$
must be a homomorphic image of our cycle.
The patterns we need are (considered as multi-sets): $$000, 001, 011, 111, 112, 122, 222, 220, 200$$ which are all present in the cycle. The one that is missing is 012. There is nowhere to insert one digit to achieve the pattern 012 without losing other patterns.
(On the other hand, in a binary alphabet you could just do $0^n1^n$ and it works.)
