MathDB

A ternary sequence is one whose terms all lie in the set

\{0, 1, 2\}

. Let

w

be a length

n

ternary sequence

(a_1,\ldots,a_n)

. Prove that

w

can be extended leftwards and rightwards to a length

m=6n

ternary sequence (d_1,\ldots,d_m) = (b_1,\ldots,b_p,a_1,\ldots,a_n,c_1,\ldots,c_q), p,q\geqslant 0,containing no length

t > 2n

palindromic subsequence.
(A sequence is called palindromic if it reads the same rightwards and leftwards. A length

t

subsequence of

(d_1,\ldots,d_m)

is a sequence of the form

(d_{i_1},\ldots,d_{i_t})

, where

1\leqslant i_1<\cdots<i_t \leqslant m

C4