Question

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

$$
eg(x_1 \leftrightarrow x_2) \land (x_1 \lor x_3) \land (
eg x_1 \lor 
eg x_3) = 0$$
$$
eg(x_2 \leftrightarrow x_3) \land (x_2 \lor x_4) \land (
eg x_2 \lor 
eg x_4) = 0$$
$$\vdots$$
$$
eg(x_7 \leftrightarrow x_8) \land (x_7 \lor x_9) \land (
eg x_7 \lor 
eg x_9) = 0$$

В ответе укажите количество таких наборов.

Accepted Answer

18

Answer

Идея решения: каждое уравнение вида $
eg(x_i \leftrightarrow x_{i+1}) \land (x_i \lor x_{i+2}) \land (
eg x_i \lor 
eg x_{i+2}) = 0$ накладывает ограничения на три переменные; нужно найти количество допустимых наборов для одного уравнения, затем для системы из нескольких уравнений, отслеживая совместимость по общим переменным.

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

Уравнение равно нулю, если хотя бы один из трёх множителей равен нулю:
- $
eg(x_i \leftrightarrow x_{i+1}) = 0$ означает $x_i = x_{i+1}$;
- $(x_i \lor x_{i+2}) = 0$ означает $x_i = 0$ и $x_{i+2} = 0$;
- $(
eg x_i \lor 
eg x_{i+2}) = 0$ означает $x_i = 1$ и $x_{i+2} = 1$.

Перебирая все $2^3 = 8$ наборов $(x_i, x_{i+1}, x_{i+2})$, находим 6 решений:
- $(0, 0, 0)$, $(0, 0, 1)$, $(0, 1, 0)$, $(1, 0, 1)$, $(1, 1, 0)$, $(1, 1, 1)$.

**Система из двух уравнений**

Первое уравнение связывает $(x_1, x_2, x_3)$, второе — $(x_2, x_3, x_4)$. Переменные $x_2$ и $x_3$ общие. Для каждого решения первого уравнения подсчитываем совместимые решения второго:

- При $x_1 = 0, x_2 = 0, x_3 = 0$: возможны $(x_3, x_4) \in \{(0, 0), (0, 1)\}$ → 2 варианта.
- При $x_1 = 0, x_2 = 0, x_3 = 1$: возможен $(x_3, x_4) = (1, 0)$ → 1 вариант.
- При $x_1 = 0, x_2 = 1, x_3 = 0$: возможен $(x_3, x_4) = (0, 1)$ → 1 вариант.
- При $x_1 = 1, x_2 = 0, x_3 = 1$: возможен $(x_3, x_4) = (1, 0)$ → 1 вариант.
- При $x_1 = 1, x_2 = 1, x_3 = 0$: возможны $(x_3, x_4) \in \{(0, 0), (0, 1)\}$ → 2 варианта.
- При $x_1 = 1, x_2 = 1, x_3 = 1$: возможен $(x_3, x_4) = (1, 0)$ → 1 вариант.

Итого: $2 + 1 + 1 + 1 + 2 + 1 = 8$ решений.

**Система из трёх и более уравнений**

Применяя аналогичный метод динамического программирования (для каждого решения системы из $k$ уравнений подсчитываем совместимые решения $(k+1)$-го уравнения):

- 1 уравнение: 6 решений.
- 2 уравнения: 8 решений.
- 3 уравнения: 10 решений.
- 4 уравнения: 12 решений.
- 5 уравнений: 14 решений.
- 6 уравнений: 16 решений.
- 7 уравнений: 18 решений.

Система содержит 7 уравнений (для пар $(x_1, x_2), (x_2, x_3), \ldots, (x_7, x_8)$), поэтому ответ — 18.

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

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

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