17
$\begingroup$

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 $.

$\endgroup$
  • 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śnicki Apr 27 '17 at 20:29
  • 2
    $\begingroup$ I'd like to call this The Lawrence Welk Problem ("a one and a two..."). $\endgroup$ – Gerry Myerson Apr 27 '17 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 Israel Apr 28 '17 at 0:58
  • 2
    $\begingroup$ No, for $n=6$ the maximal length is $30$, an example being $112122220200001011112120201011$. $\endgroup$ – Robert Israel Apr 28 '17 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śnicki Apr 28 '17 at 7:19
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

It is perhaps more 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 the following picture must be a homomorphic image of our cycle: enter image description here

The patterns we need are (considered as multi-sets): 000, 001, 011, 111, 112, 122, 222, 220, 200 which are all present in the picture, but the one that is missing is 012 and there is nowhere to insert one digit to achieve the pattern 012 without losing other patterns.

In a binary alphabet of course you could just do $0^n1^n$ and it works.

$\endgroup$

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.