Question

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

$$((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$$
$$\vdots$$
$$((x_9 \equiv x_{10}) \lor (x_{11} \equiv x_{12})) \land (
eg(x_9 \equiv x_{10}) \lor 
eg(x_{11} \equiv x_{12})) = 1$$

Accepted Answer

128

Answer

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

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

Выражение $(A \lor B) \land (
eg A \lor 
eg B)$ истинно тогда и только тогда, когда $A$ и $B$ имеют разные значения (т. е. $A \oplus B = 1$).

Для первого уравнения $((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_1 \equiv x_2)$ и $(x_3 \equiv x_4)$ имели разные значения.

Обозначим $A = (x_1 \equiv x_2)$ и $B = (x_3 \equiv x_4)$.

- Если $A = 0$, то $B = 1$: пара $(x_1, x_2)$ принимает 2 значения (01, 10), пара $(x_3, x_4)$ принимает 2 значения (00, 11). Итого: $2 	imes 2 = 4$ набора.
- Если $A = 1$, то $B = 0$: пара $(x_1, x_2)$ принимает 2 значения (00, 11), пара $(x_3, x_4)$ принимает 2 значения (01, 10). Итого: $2 	imes 2 = 4$ набора.

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

**Второе уравнение**

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

- Если $(x_3 \equiv x_4) = 0$ (4 набора из первого уравнения), то $(x_5 \equiv x_6) = 1$: пара $(x_5, x_6)$ имеет 2 значения. Итого: $4 	imes 2 = 8$ наборов.
- Если $(x_3 \equiv x_4) = 1$ (4 набора из первого уравнения), то $(x_5 \equiv x_6) = 0$: пара $(x_5, x_6)$ имеет 2 значения. Итого: $4 	imes 2 = 8$ наборов.

Система из двух уравнений имеет $8 + 8 = 16$ решений. При этом $(x_5 \equiv x_6)$ принимает значение 0 в 8 наборах и значение 1 в 8 наборах.

**Третье уравнение**

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

- Если $(x_5 \equiv x_6) = 0$ (8 наборов), то $(x_7 \equiv x_8) = 1$: пара $(x_7, x_8)$ имеет 2 значения. Итого: $8 	imes 2 = 16$ наборов.
- Если $(x_5 \equiv x_6) = 1$ (8 наборов), то $(x_7 \equiv x_8) = 0$: пара $(x_7, x_8)$ имеет 2 значения. Итого: $8 	imes 2 = 16$ наборов.

Система из трёх уравнений имеет $16 + 16 = 32$ решения.

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

На каждом шаге количество решений удваивается:
- 1 уравнение: 8 решений
- 2 уравнения: $8 	imes 2 = 16$ решений
- 3 уравнения: $16 	imes 2 = 32$ решения
- 4 уравнения: $32 	imes 2 = 64$ решения
- 5 уравнений: $64 	imes 2 = 128$ решений

Система содержит 5 уравнений (пары переменных: $(x_1, x_2)$, $(x_3, x_4)$, $(x_5, x_6)$, $(x_7, x_8)$, $(x_9, x_{10})$, $(x_{11}, x_{12})$ — всего 6 пар, 5 уравнений связи).

Итоговое количество решений: **128**.

![Рисунок](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Алгоритмы и исполнителиЕГЭ по информатике