Question

Сколько различных решений имеет система уравнений:

$$
eg x_1 \lor x_2 = 1$$
$$
eg x_2 \lor x_3 = 1$$
$$\ldots$$
$$
eg x_9 \lor x_{10} = 1$$

где $x_1, x_2, \ldots, x_{10}$ — логические переменные?

В ответе укажите количество наборов значений переменных, удовлетворяющих системе.

Accepted Answer

11

Answer

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

**Первое уравнение** ($
eg x_1 \lor x_2 = 1$):
- При $x_1 = 0$: $x_2$ может быть 0 или 1 (два варианта).
- При $x_1 = 1$: $x_2$ должен быть 1 (один вариант).

Итого: 3 набора для $(x_1, x_2)$.

**Первые два уравнения** ($
eg x_1 \lor x_2 = 1$ и $
eg x_2 \lor x_3 = 1$):

Применим второе уравнение к каждому из трёх наборов:
- $(x_1, x_2) = (0, 0)$: $x_3$ может быть 0 или 1 → 2 варианта.
- $(x_1, x_2) = (0, 1)$: $x_3$ должен быть 1 → 1 вариант.
- $(x_1, x_2) = (1, 1)$: $x_3$ должен быть 1 → 1 вариант.

Итого: 4 набора для $(x_1, x_2, x_3)$.

**Первые три уравнения**:

Применим третье уравнение:
- Наборы с $x_3 = 0$: $x_4$ может быть 0 или 1 → 2 варианта.
- Наборы с $x_3 = 1$: $x_4$ должен быть 1 → 1 вариант.

Из 4 наборов: 1 имеет $x_3 = 0$, остальные 3 имеют $x_3 = 1$.

Итого: $1 \cdot 2 + 3 \cdot 1 = 5$ наборов.

**Закономерность**: если на шаге $i$ имеется $k_i$ наборов, то на шаге $i+1$ получаем $k_{i+1} = k_i + 1$ (так как ровно один из текущих наборов имеет последнюю переменную равной 0, и он даёт два продолжения; остальные $k_i - 1$ наборов имеют последнюю переменную равной 1 и дают по одному продолжению).

Последовательность: $k_1 = 3$, $k_2 = 4$, $k_3 = 5$, $\ldots$, $k_9 = 11$.

Для системы из 9 уравнений (с 10 переменными) получаем **11 наборов**.

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

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

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