Математикадан республикалық олимпиада, 2003-2004 оқу жылы, 10 сынып

Бізге белгілі бір $n$ натурал саны берілсін. Әрбір $1\le k\le l\le n$ үшін $\left| \sum\limits_{i=2k-1}^{2l}{{{\varepsilon }_{i}}} \right|\le 2$ болатындай барлық $\left( {{\varepsilon }_{1}},{{\varepsilon }_{2}},\ldots ,{{\varepsilon }_{2n}} \right)$ тізбектер санын тап, мұнда әрбір $1\le i\le 2n$ үшін ${{\varepsilon }_{i}}=\pm 1$.

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

Заменим $x_{i}=a_{2i-1}+a_{2i}$ тогда эта переменная, может принимать три значения $x_{i}=0;-2;2$

Опишем некоторые свойства:

1) Так как $|2+2|=|-2-2| = 4>2$ тогда непрерывная частичная сумма будет всегда знакочередующаяся.

2) Если:

$x_{i}=2$ тогда решением будет только пара $(a_{2i-1},a_{2i})=(1,1)$

$x_{i}=-2$ тогда решением будет только пара $(a_{2i-1},a_{2i})=(-1,-1)$

$x_{i}=0$ тогда решением будет только две пары пара $(a_{2i-1},a_{2i})=(-1,1) ; \ (1;-1)$

3) Если ряд $(x_{1},x_{2},...,x_{n})$ является решением последовательности, то и $(-x_{1},-x_{2}, ..., -x_{n})$ так же является решением.

Решение: Разобьём задачу исходя из свойства 1, на случаи когда в ряде : $(x_{1}, x_{2}, x_{3}, ... \ x_{i})$

Нет нулей, 1 нуль, 2 нуля, 3 нуля ..., и т.д

1. Когда нет нулей решения всего очевидно два, исходя из свойств $1$ и $3$, это просто знакочередующийся ряд $(\pm 2,\mp2, \pm 2,\mp 2...) = 2$

2. Когда один нуль, это число способов расставить $0$ в $n$ ячеек из решения в пункте $1$ за место какого то $\pm 2$ это $C_{n}^{1}$ и учитывая пункт 2 получается количество решения $C_{n}^1 \cdot 1^{n-1} \cdot 2^1 $ потому что 1 нуль порождает 2 решения и $n-1$ штук $\pm2$ порождает по 1 решению и учитывая пункт $3$ всего решений для $(a_{1},a_{2},...,a_{2n})$ будет $2 \cdot C_{n}^1 \cdot 1^{n-1} \cdot 2^1$

Аналогично и для остальных, кроме последнего случая где все $0$ , так как в этом случае всего очевидно одно решение, по итогу получаем сумму

$$2 + 2 \cdot C_{n}^1 \cdot 1^{n-1} \cdot 2^1 + 2 \cdot C_{n}^2 \cdot 1^{n-2} \cdot 2^2+ ...+ C_{n}^n \cdot 1^{n-n} \cdot 2^n$$ преобразуем

$$2(1+C_{n}^1 \cdot 1^{n-1} \cdot 2^1 + C_{n}^2 \cdot 1^{n-2} \cdot 2^2+ ...+ C_{n}^n \cdot 1^{n-n} \cdot 2^n) - C_{n}^n \cdot 1^{n-n} \cdot 2^n$$

По биному Ньютона первая скобка это $(1+2)^n = 3^n$ тогда количество последовательностей будет равно $$2 \cdot 3^n - 2^n$$