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$ накладывает ограничение на три переменные; нужно найти количество допустимых наборов для одного уравнения, затем для системы из двух, трёх и так далее, выявив закономерность.

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

Рассмотрим первое уравнение с переменными $x_1, x_2, x_3$.

Условие $
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 допустимых наборов.

**Анализ двух уравнений**

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

Итого: $1 + 2 + 1 + 2 = 4$ варианта для каждого значения $x_1$, всего $4 + 4 = 8$ наборов.

**Выявление закономерности**

Продолжая анализ для трёх, четырёх и далее уравнений, получаем последовательность:
- 1 уравнение: 6 решений
- 2 уравнения: 8 решений
- 3 уравнения: 10 решений
- 4 уравнения: 12 решений
- $\ldots$
- 8 уравнений: $6 + 2 \cdot 7 = 20$ решений

Закономерность: для $n$ уравнений количество решений равно $2n + 4$.

При $n = 8$ получаем $2 \cdot 8 + 4 = 20$.

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

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

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