Question

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

$(x_1 \lor x_2) \land (
eg x_1 \lor 
eg x_2) \land (
eg x_1 \lor y_1) = 1$

$(x_2 \lor x_3) \land (
eg x_2 \lor 
eg x_3) \land (
eg x_2 \lor y_2) = 1$

$\ldots$

$(x_6 \lor x_7) \land (
eg x_6 \lor 
eg x_7) \land (
eg x_6 \lor y_6) = 1$

$(
eg x_7 \lor y_7) = 1$

Accepted Answer

24

Answer

Идея решения: проанализировать структуру каждого уравнения, найти допустимые наборы для переменных $x_i$ и $y_i$, затем применить динамическое программирование для подсчёта всех согласованных решений.

**Анализ первых шести уравнений**

Рассмотрим уравнение вида $(x_i \lor x_{i+1}) \land (
eg x_i \lor 
eg x_{i+1}) \land (
eg x_i \lor y_i) = 1$.

Первые два множителя $(x_i \lor x_{i+1}) \land (
eg x_i \lor 
eg x_{i+1})$ означают, что ровно одна из переменных $x_i$ и $x_{i+1}$ равна 1 (исключающее ИЛИ).

Таблица допустимых значений:

| $x_i$ | $x_{i+1}$ | $y_i$ |
|---|---|---|
| 0 | 1 | 0 или 1 |
| 1 | 0 | 1 |

Таким образом, для каждого уравнения:
- если $x_i = 0$, то $x_{i+1} = 1$ и $y_i \in \{0, 1\}$ (2 варианта);
- если $x_i = 1$, то $x_{i+1} = 0$ и $y_i = 1$ (1 вариант).

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

Уравнение $(
eg x_7 \lor y_7) = 1$ означает:
- если $x_7 = 0$, то $y_7 \in \{0, 1\}$ (2 варианта);
- если $x_7 = 1$, то $y_7 = 1$ (1 вариант).

**Динамическое программирование**

Обозначим через $f(i, x_i)$ количество способов выбрать значения переменных $x_1, \ldots, x_i, y_1, \ldots, y_i$ так, чтобы все уравнения с индексами $1, \ldots, i-1$ были удовлетворены и переменная $x_i$ имела значение $x_i$.

Начальное условие: $f(1, 0) = 1$, $f(1, 1) = 1$ (переменная $x_1$ может быть 0 или 1).

Переход: для каждого $i$ от 1 до 6:
- $f(i+1, 1) = f(i, 0) \cdot 2$ (если $x_i = 0$, то $x_{i+1} = 1$, и $y_i$ может быть 0 или 1);
- $f(i+1, 0) = f(i, 1) \cdot 1$ (если $x_i = 1$, то $x_{i+1} = 0$, и $y_i = 1$).

Вычисления:

| $i$ | $f(i, 0)$ | $f(i, 1)$ |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 2 |
| 3 | 2 | 2 |
| 4 | 2 | 4 |
| 5 | 4 | 4 |
| 6 | 4 | 8 |
| 7 | 8 | 8 |

Для последнего уравнения:
- если $x_7 = 0$, то $y_7$ может быть 0 или 1: $f(7, 0) \cdot 2 = 8 \cdot 2 = 16$;
- если $x_7 = 1$, то $y_7 = 1$: $f(7, 1) \cdot 1 = 8 \cdot 1 = 8$.

Общее количество наборов: $16 + 8 = 24$.

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

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