XIV математическая олимпиада «Шелковый путь», 2015 год

Пусть $B_n$ — множество всех последовательностей длины $n$, состоящих из нулей и единиц. Для каждых двух последовательностей $a,b \in B_n$ (не обязательно различных) определим строки $\varepsilon_0\varepsilon_1\varepsilon_2 \dots \varepsilon_n$ и $\delta_0\delta_1\delta_2 \dots \delta_n$ соотношениями $\varepsilon_0=\delta_0=0$ и $$\varepsilon_{i+1}=(\delta_i-a_{i+1})(\delta_i-b_{i+1}), \quad \delta_{i+1}=\delta_i+(-1)^{\delta_i}\varepsilon_{i+1} \quad (0 \leq i \leq n-1).$$ Пусть $w(a,b)=\varepsilon_0+\varepsilon_1+\varepsilon_2+\dots +\varepsilon_n$. Найдите $f(n)=\sum\limits_{a,b \in {B_n}} {w(a,b)}$. ( Е. Байсалов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. $f(n) = n \cdot 4^{n-1}.$
Не трудно заметить, что для любых последовательностей $a,b\in {{B}_{n}}$ все элементы строк $\varepsilon _0 \varepsilon_1 \ldots \varepsilon_{n}$ и ${{\delta }_{0}}{{\delta }_{1}}\ldots {{\delta }_{n}}$ будут равны 0 или 1.
Для каждой последовательности $c\in {{B}_{n}}$ определим сопряженную ей последовательность $\bar{c}\in {{B}_{n}}$ так, чтобы каждый элемент сопряженной последовательности дополнял в сумме до 1 соответствующий ей элемент. Для каждой пары последовательностей $a,b\in {{B}_{n}}$ определим четверку пар: $(a,b)$, $(a,\bar{b})$, $(\bar{a},b)$ и $(\bar{a},\bar{b})$. Заметим, что для каждой такой четверки, для любого фиксированного $i$ ($1\le i\le n$), только одно из ${{\varepsilon }_{i}}=1$, а остальные три ${{\varepsilon }_{i}}=0$.
Всевозможных пар $a,b\in {{B}_{n}}$ равно ${{4}^{n}}$, которые разбиваются на ${{4}^{n-1}}$ четверок. Для каждой четверки $w(a,b)+w(\bar{a},b)+w(a,\bar{b})+w(\bar{a},\bar{b})=n$, так как для всех пар ${{\varepsilon }_{0}}=0$, а для каждого $i$ ($1\le i\le n$), только одно из ${{\varepsilon }_{i}}=1$. Следовательно, $f(n)=\sum\limits_{a,b\in {{B}_{n}}}{w(a,b)=}n\cdot {{4}^{n-1}}$.