Question

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

$$((x_1 \equiv x_2) \lor (x_3 \equiv x_4)) \land (
eg(x_1 \equiv x_2) \lor 
eg(x_3 \equiv x_4)) = 1$$
$$((x_3 \equiv x_4) \lor (x_5 \equiv x_6)) \land (
eg(x_3 \equiv x_4) \lor 
eg(x_5 \equiv x_6)) = 1$$
$$((x_5 \equiv x_6) \lor (x_7 \equiv x_8)) \land (
eg(x_5 \equiv x_6) \lor 
eg(x_7 \equiv x_8)) = 1$$
$$((x_7 \equiv x_8) \lor (x_9 \equiv x_{10})) \land (
eg(x_7 \equiv x_8) \lor 
eg(x_9 \equiv x_{10})) = 1$$

Accepted Answer

64

Answer

Идея решения: каждое уравнение имеет вид $(A \lor B) \land (
eg A \lor 
eg B)$, что эквивалентно исключающему ИЛИ ($A \oplus B = 1$), то есть ровно одно из выражений $A$ или $B$ должно быть истинно. Уравнения связаны через общие переменные, поэтому подсчитаем решения пошагово, отслеживая количество наборов для каждого значения связующего выражения.

**Первое уравнение:** $(x_1 \equiv x_2) \oplus (x_3 \equiv x_4) = 1$

Выражение $(x_1 \equiv x_2)$ принимает значение 1 при наборах $(0,0)$ и $(1,1)$ — 2 способа, и значение 0 при наборах $(0,1)$ и $(1,0)$ — 2 способа.

Аналогично для $(x_3 \equiv x_4)$.

Условие $A \oplus B = 1$ означает, что $A$ и $B$ имеют разные значения:
- Если $(x_1 \equiv x_2) = 0$ и $(x_3 \equiv x_4) = 1$: $2 	imes 2 = 4$ набора.
- Если $(x_1 \equiv x_2) = 1$ и $(x_3 \equiv x_4) = 0$: $2 	imes 2 = 4$ набора.

Итого: 8 решений первого уравнения. При этом $(x_3 \equiv x_4)$ принимает значение 1 в 4 наборах и значение 0 в 4 наборах.

**Второе уравнение:** $(x_3 \equiv x_4) \oplus (x_5 \equiv x_6) = 1$

Для каждого значения $(x_3 \equiv x_4)$ (0 или 1) нужно, чтобы $(x_5 \equiv x_6)$ имело противоположное значение:
- Если $(x_3 \equiv x_4) = 0$, то $(x_5 \equiv x_6) = 1$: 2 способа выбрать $x_5, x_6$.
- Если $(x_3 \equiv x_4) = 1$, то $(x_5 \equiv x_6) = 0$: 2 способа выбрать $x_5, x_6$.

Для каждого из 8 решений первого уравнения получаем 2 способа выбрать $x_5, x_6$. Итого: $8 	imes 2 = 16$ решений системы из двух уравнений.

При этом $(x_5 \equiv x_6)$ принимает значение 1 в 8 наборах и значение 0 в 8 наборах.

**Третье уравнение:** $(x_5 \equiv x_6) \oplus (x_7 \equiv x_8) = 1$

Для каждого значения $(x_5 \equiv x_6)$ (0 или 1) нужно, чтобы $(x_7 \equiv x_8)$ имело противоположное значение: 2 способа выбрать $x_7, x_8$.

Для каждого из 16 решений системы из двух уравнений получаем 2 способа выбрать $x_7, x_8$. Итого: $16 	imes 2 = 32$ решения.

При этом $(x_7 \equiv x_8)$ принимает значение 1 в 16 наборах и значение 0 в 16 наборах.

**Четвёртое уравнение:** $(x_7 \equiv x_8) \oplus (x_9 \equiv x_{10}) = 1$

Для каждого значения $(x_7 \equiv x_8)$ (0 или 1) нужно, чтобы $(x_9 \equiv x_{10})$ имело противоположное значение: 2 способа выбрать $x_9, x_{10}$.

Для каждого из 32 решений системы из трёх уравнений получаем 2 способа выбрать $x_9, x_{10}$. Итого: $32 	imes 2 = 64$ решения.

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

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

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

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