Question

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

$$\begin{align}
(x_1 \land x_2) \lor (
eg x_1 \land 
eg x_2) \lor (x_1 \leftrightarrow x_3) &= 1 \
(x_2 \land x_3) \lor (
eg x_2 \land 
eg x_3) \lor (x_2 \leftrightarrow x_4) &= 1 \
&\vdots \
(x_7 \land x_8) \lor (
eg x_7 \land 
eg x_8) \lor (x_7 \leftrightarrow x_9) &= 1
\end{align}$$

Accepted Answer

18

Answer

Идея решения: каждое уравнение связывает три последовательные переменные; нужно найти все допустимые пары значений для соседних переменных, а затем применить динамическое программирование, отслеживая количество решений при переходе от одного уравнения к следующему.

**Анализ первого уравнения**

Рассмотрим уравнение $(x_1 \land x_2) \lor (
eg x_1 \land 
eg x_2) \lor (x_1 \leftrightarrow x_3) = 1$.

Построим дерево решений:
- При $x_1 = 0, x_2 = 0$: первые два члена дают $0 \lor 1 = 1$ (уравнение выполнено при любом $x_3$) — 2 решения.
- При $x_1 = 0, x_2 = 1$: первые два члена дают $0 \lor 0 = 0$, нужно $x_1 \leftrightarrow x_3 = 1$, откуда $x_3 = 0$ — 1 решение.
- При $x_1 = 1, x_2 = 0$: первые два члена дают $0 \lor 0 = 0$, нужно $x_1 \leftrightarrow x_3 = 1$, откуда $x_3 = 1$ — 1 решение.
- При $x_1 = 1, x_2 = 1$: первые два члена дают $1 \lor 0 = 1$ (уравнение выполнено при любом $x_3$) — 2 решения.

Итого 6 решений первого уравнения.

**Таблица пар $(x_2, x_3)$ из решений первого уравнения**

| Кратность | $x_2$ | $x_3$ |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 0 | 1 |
| 1 | 1 | 1 |
| 2 | 1 | 0 |

**Динамическое программирование**

Поскольку все уравнения имеют одинаковую структуру, таблица пар остаётся неизменной. Для каждого следующего уравнения применяем правило: если пара $(x_i, x_{i+1})$ из предыдущего уравнения совпадает с парой $(x_i, x_{i+1})$ в новом уравнении, то количество решений умножается.

Обозначим через $N_k$ количество решений системы из $k$ уравнений.

- $N_1 = 6$
- Для $N_2$: каждая из 4 пар из первого уравнения порождает решения второго:
  - $(0, 0)$ встречается 1 раз, порождает 2 решения: $1 	imes 2 = 2$
  - $(0, 1)$ встречается 2 раза, порождает 1 решение: $2 	imes 1 = 2$
  - $(1, 1)$ встречается 1 раз, порождает 2 решения: $1 	imes 2 = 2$
  - $(1, 0)$ встречается 2 раза, порождает 1 решение: $2 	imes 1 = 2$
  - $N_2 = 2 + 2 + 2 + 2 = 8$

- $N_3 = 10$
- $N_4 = 12$
- $N_5 = 14$
- $N_6 = 16$
- $N_7 = 18$

Система состоит из 7 уравнений (для пар $(x_1, x_2, x_3)$, $(x_2, x_3, x_4)$, …, $(x_7, x_8, x_9)$).

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=10599)

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