Define a "ternary sequence" is a sequence that every number is $0,1$ or $2$. ternary sequence $(x_1,x_2,x_3,\cdots,x_n)$, define its difference to be $$(|x_1-x_2|,|x_2-x_3|,\cdots,|x_{n-1}-x_n|)$$A difference will make the length of the sequence decrease by $1$, so we define the "feature value" of a ternary sequence with length $n$ is the number left after $n-1$ differences. How many ternary sequences has length $2023$ and feature value $0$? Proposed by CSJL
Problem
Source: 2022 IMOC C5
Tags: combinatorics, IMOC
09.10.2022 17:17
Answer: $\dfrac{3^{2023}+3^{1959}}{2}-2^{2022}$. For a ternary sequence $S_0=(x_1,x_2,..,x_n)$ let $m(S)$ be its "feature value" and $L(S)$ be its difference. Call a ternary sequence $S$ good if $m(S)=0$. Claim: Suppose that $S_0$ contains no 1. Then $m(S_0) \neq 1$. Proof: This is simple since $|2-0|=2,|2-2|=0$ and $|0-0|=0$ so $L(S)$ also contains no 1 and eventually $m(S)=0$ or $2 \blacksquare$ Claim: Suppose that $S_0$ has at least one $1$. Then $m(S_0)\neq 2$. Proof: Let the sequence of the sequences be $S_0 \to S_1 \to ...\to S_k$ where $S_k=\left \{m(S_0) \right \}$ (so $S_1=L(S_0)$ etc). Let $x_l=1$. If $x_{l+1}\neq 1$ (or $x_{l-1}$ if needed) then $1=|x_l-x_{l+1}|\in S_1$ so we do the same algotithm for $S_1$ . If there is no point at which the algorithm fails then $m(S_0)=1$ since $S_k$ has to contains a 1. Otherwise there is some point where every neighbor of every 1 is also 1, so there is some $0\leq r<k-1$ such that $S_r$ contains only 1's. Thus $S_r=(1,1..,1) \to (0,0,..,0)\to..\to (0)$ i.e $m(S_0)=0$ and the claim is proved $\blacksquare$ First lets count the number of good ternary sequences $S=(x_1,..,x_{2023})$ of length $2023$ that no contains 1's. For every such sequence create an other sequence $W(S)=(y_1,..,y_{2023})$ where $y_i=-1$ if $x_i=2$ and $y_i=1$ if $x_i=0$ and a new operation $R(W(S))=(y_1y_2,y_2y_3,..,y_{2022}y_{2023})$. Since $|2-0|=2,|0-0|=0$ and $|2-2|=0$ we have that $W(L(S))=R(W(S))$ and now equivelantly we must have $R(R(..R(W(S)))..)=1$ where $R$ is applied $2022$ times. Observe that $R(R(x_1,x_2,x_3))=R(x_1x_2,x_2x_3)=x_1x_2^2x_3$ and we can prove by induction that the final value for $R(R..(W(S))..)$ is going to be $\prod_{i=1}^{2023} y_i^{\binom{2022}{i-1}}$. For every $i$ such that $\binom{2022}{i-1}$ is even $y_i$ can be $\pm 1$. Let $A=\left \{i | \binom{2022}{i-1}=1 \pmod 2 \right \}$. In order to make the product equal to $1$ we have to choose an even number of $y_i, i\in A$ equals to $-1$. Observe that $2022=11111100110_{(2)}$ and for $0\leq k\leq 2022$ if $k=a_0+2a_1+..2^{10}a_k$ Lucas's theorem gives $\binom{2022}{k}\equiv\binom{0}{a_0}\binom{1}{a_1}\binom{1}{a_2}\binom{0}{a_3}\binom{0}{a_4}\binom{1}{a_5}\binom{1}{a_6}\binom{1}{a_7}\binom{1}{a_8}\binom{1}{a_9}\binom{1}{a_{10}}\pmod 2$ and thus $|A|=2^8$ Thus the desired number of sequences is $\displaystyle 2^{2023-|A|}\cdot \left (\binom{|A|}{0}+\binom{|A|}{2}+..+\binom{|A|}{|A|} \right )=2^{2023-|A|}\cdot 2^{|A|-1}=2^{2022}$ Now lets count the number of good sequences $S$ that contains at least one 1. As we showed before $m(S)=0$ or $1$ so in orded to deside whether $m(S)=0$ or $m(S)=1$ it's enough to check it's parity. That means that 2's can be replaced by 0's and now we have to check only the sequences that contains only 0's and 1's. We do a similar work as before replacing zeros by 1's and ones by -1's. But now every $-1$ can be in fact either a 0 or a 2 in the initial sequence. With these observations it's easy to see that the desired value here is $\sum_{i\in \left \{0,..,1959 \right \}} \sum_{j\in \left \{0,2,4,..,64 \right \}} 2^{i+j}\binom{1959}{i}\binom{64}{j}-2^{2023}$ where $2^{2023}$ is reduced since we want the initial sequence to contains at least one 1. Observe that $\sum_{i\in \left \{0,..,1959 \right \}} \sum_{j\in \left \{0,2,4,..,64 \right \}} 2^{i+j}\binom{1959}{i}\binom{64}{j}-2^{2023}= \sum_{i\in \left \{0,..,1959 \right \}}2^{i}\binom{1959}{i}\sum_{j\in \left \{0,2,4,..,64 \right \}} 2^{j}\binom{64}{j}-2^{2023}=3^{1959}\cdot \dfrac{3^{64}+1}{2}-2^{2023}$. Finally the number of good sequences is $3^{1959}\cdot \dfrac{3^{64}+1}{2}-2^{2023}+2^{2022}=\boxed {\dfrac{3^{2023}+3^{1959}}{2}-2^{2022}}$.