Question

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

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

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

Accepted Answer

20

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\left[
eg(x_i \leftrightarrow x_{i+1}) \land (x_i \lor x_{i+2}) \land (
eg x_i \lor 
eg x_{i+2})ight] = 1$$

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

Последние два условия несовместимы одновременно, поэтому уравнение выполнено, если $x_i = x_{i+1}$ или $(x_i, x_{i+2}) \in \{(0,0), (1,1)\}$.

Перебирая все 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$ общие.

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

Итого: $2 + 2 + 1 + 1 + 2 + 2 = 10$ решений для двух уравнений.

**Закономерность**

Продолжая анализ:
- 1 уравнение: 6 решений.
- 2 уравнения: 8 решений.
- 3 уравнения: 10 решений.
- 4 уравнения: 12 решений.

Видна арифметическая прогрессия: количество решений = $4 + 2k$, где $k$ — число уравнений.

Для 8 уравнений: $4 + 2 \cdot 8 = 20$ решений.

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

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

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