Question

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

$$
eg(x_1 \leftrightarrow x_2) \land ((x_1 \land 
eg x_3) \lor (
eg x_1 \land x_3)) = 0$$
$$
eg(x_2 \leftrightarrow x_3) \land ((x_2 \land 
eg x_4) \lor (
eg x_2 \land x_4)) = 0$$
$$\vdots$$
$$
eg(x_8 \leftrightarrow x_9) \land ((x_8 \land 
eg x_{10}) \lor (
eg x_8 \land x_{10})) = 0$$

Accepted Answer

20

Answer

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

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

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

Для первого уравнения ($x_1, x_2, x_3$):
- При $x_1 = 0$: если $x_2 = 0$, то $x_3 \in \{0, 1\}$ (2 варианта); если $x_2 = 1$, то $x_3 = 0$ (1 вариант). Итого 3 варианта.
- При $x_1 = 1$: если $x_2 = 1$, то $x_3 \in \{0, 1\}$ (2 варианта); если $x_2 = 0$, то $x_3 = 1$ (1 вариант). Итого 3 варианта.

Первое уравнение имеет **6 решений**.

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

Добавляем второе уравнение на переменные $x_2, x_3, x_4$. Для каждого из 6 решений первого уравнения определяем, сколько значений $x_4$ допустимо:
- При $x_1 = 0, x_2 = 0, x_3 = 0$: второе уравнение требует $x_3 = x_4$ или $x_2 = x_3$. Выполнено $x_2 = x_3$, поэтому $x_4 \in \{0, 1\}$ (2 варианта).
- При $x_1 = 0, x_2 = 0, x_3 = 1$: требуется $x_2 = x_3$ или $x_3 = x_4$. Не выполнено первое, поэтому $x_4 = 1$ (1 вариант).
- При $x_1 = 0, x_2 = 1, x_3 = 0$: требуется $x_2 = x_3$ или $x_3 = x_4$. Не выполнено первое, поэтому $x_4 = 0$ (1 вариант).
- При $x_1 = 1, x_2 = 1, x_3 = 0$: требуется $x_2 = x_3$ или $x_3 = x_4$. Не выполнено первое, поэтому $x_4 = 0$ (1 вариант).
- При $x_1 = 1, x_2 = 1, x_3 = 1$: требуется $x_2 = x_3$ или $x_3 = x_4$. Выполнено первое, поэтому $x_4 \in \{0, 1\}$ (2 варианта).
- При $x_1 = 1, x_2 = 0, x_3 = 1$: требуется $x_2 = x_3$ или $x_3 = x_4$. Не выполнено первое, поэтому $x_4 = 1$ (1 вариант).

Система из двух уравнений имеет $2 + 1 + 1 + 1 + 2 + 1 = \mathbf{8}$ решений.

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

Применяя аналогичный метод динамического подсчёта:
- Система из трёх уравнений: **10 решений**.
- Система из четырёх уравнений: **12 решений**.
- Система из восьми уравнений: **20 решений**.

Закономерность: при добавлении каждого нового уравнения количество решений увеличивается на 2.

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

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

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

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