Question

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

$$
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_9 \leftrightarrow x_{10}) \land ((x_9 \land 
eg x_{11}) \lor (
eg x_9 \land x_{11})) = 0$$

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

Accepted Answer

22

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_1 \leftrightarrow x_2) \land ((x_1 \land 
eg x_3) \lor (
eg x_1 \land x_3)) = 0$$

Это произведение равно нулю, если хотя бы один множитель равен нулю:
- $
eg(x_1 \leftrightarrow x_2) = 0$ означает $x_1 = x_2$, или
- $((x_1 \land 
eg x_3) \lor (
eg x_1 \land x_3)) = 0$ означает $x_1 = x_3$.

Перебирая все 8 наборов $(x_1, x_2, x_3)$, находим 6 решений:
- $(0, 0, 0)$, $(0, 0, 1)$, $(0, 1, 0)$, $(1, 0, 1)$, $(1, 1, 0)$, $(1, 1, 1)$.

**Расширение на две переменные**

При добавлении второго уравнения (с переменными $x_2, x_3, x_4$) каждое из 6 решений первого уравнения расширяется на допустимые значения $x_4$. Анализируя все случаи, получаем 8 решений системы из двух уравнений.

**Динамическое расширение**

Обозначим через $f(k)$ количество решений системы из $k$ уравнений (с переменными $x_1, \ldots, x_{k+2}$):
- $f(1) = 6$
- $f(2) = 8$
- $f(3) = 10$
- $f(4) = 12$

Видна закономерность: $f(k) = 2k + 4$ для $k \geq 1$.

**Вычисление для девяти уравнений**

Система содержит 9 уравнений (с переменными $x_1, \ldots, x_{11}$):

$$f(9) = 2 \cdot 9 + 4 = 22$$

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

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

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