Республиканская олимпиада по математике, 2004 год, 10 класс

Пусть $n$ — фиксированное натуральное число. Найдите количество всех последовательностей $(a_1 ,a_2 , \ldots ,a_{2n} )$, где $a_i = \pm 1$ для любого $1 \leq i \leq 2n$, удовлетворяющих условию: для любых $1 \leq k \leq l \leq n$ верно $$ \left|{\sum\limits_{i = 2k - 1}^{2l} {a_i } }\right|\leq 2. $$

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

Заменим $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$$