Question

Найти количество различных наборов значений логических переменных $x_1, x_2, \ldots, x_9, y_1, y_2, \ldots, y_9$, удовлетворяющих системе уравнений:

$$
\begin{align}
(x_1 \lor y_1) \leftrightarrow 
eg(x_2 \lor y_2) &= 1 \
(x_2 \lor y_2) \leftrightarrow 
eg(x_3 \lor y_3) &= 1 \
&\vdots \
(x_8 \lor y_8) \leftrightarrow 
eg(x_9 \lor y_9) &= 1
\end{align}
$$

Accepted Answer

324

Answer

Идея решения: применить метод отображений, отслеживая, как каждая пара переменных $(x_i, y_i)$ переходит в следующую пару $(x_{i+1}, y_{i+1})$ в соответствии с условиями эквиваленции.

Обозначим состояние пары как двоичное число: $00, 01, 10, 11$ (соответствующие значениям $(x_i, y_i)$).

Проанализируем условие $(x_i \lor y_i) \leftrightarrow 
eg(x_{i+1} \lor y_{i+1}) = 1$. Эквиваленция истинна, когда обе части имеют одинаковое значение истинности.

Построим таблицу переходов. Обозначим $a_i = x_i \lor y_i$. Тогда условие: $a_i \leftrightarrow 
eg a_{i+1} = 1$, то есть $a_i = 
eg a_{i+1}$.

Для каждого состояния пары $(x_i, y_i)$ определим, какие состояния $(x_{i+1}, y_{i+1})$ допустимы:

- Если $(x_i, y_i) = 00$, то $x_i \lor y_i = 0$, значит $x_{i+1} \lor y_{i+1} = 1$. Возможные пары: $01, 10, 11$ (3 варианта).
- Если $(x_i, y_i) = 01$, то $x_i \lor y_i = 1$, значит $x_{i+1} \lor y_{i+1} = 0$. Возможная пара: $00$ (1 вариант).
- Если $(x_i, y_i) = 10$, то $x_i \lor y_i = 1$, значит $x_{i+1} \lor y_{i+1} = 0$. Возможная пара: $00$ (1 вариант).
- Если $(x_i, y_i) = 11$, то $x_i \lor y_i = 1$, значит $x_{i+1} \lor y_{i+1} = 0$. Возможная пара: $00$ (1 вариант).

Применим динамическое программирование. Пусть $dp[i][s]$ — количество способов достичь состояния $s$ на позиции $i$.

| Состояние | $i=1$ | $i=2$ | $i=3$ | $i=4$ | $i=5$ | $i=6$ | $i=7$ | $i=8$ | $i=9$ |
|-----------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| $00$ | 1 | 3 | 3 | 9 | 9 | 27 | 27 | 81 | 81 |
| $01$ | 1 | 1 | 3 | 3 | 9 | 9 | 27 | 27 | 81 |
| $10$ | 1 | 1 | 3 | 3 | 9 | 9 | 27 | 27 | 81 |
| $11$ | 1 | 1 | 3 | 3 | 9 | 9 | 27 | 27 | 81 |

На первой позиции каждое из 4 состояний может быть выбрано один раз.

На каждой следующей позиции:
- Состояние $00$ может быть достигнуто из состояний $01, 10, 11$ (по 1 способу из каждого).
- Состояния $01, 10, 11$ могут быть достигнуты только из состояния $00$ (по 1 способу).

Итоговое количество решений:
$$81 + 81 + 81 + 81 = 324$$

![Рисунок](https://ege.sdamgia.ru/formula/svg/a8/a879334c8cacfab6311c20aa197dc6b4.svg)

Задание №23Алгоритмы и исполнителиЕГЭ по информатике