Question

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

$(x_1 \land y_1) \equiv (\neg x_2 \lor \neg y_2)$

$(x_2 \land y_2) \equiv (\neg x_3 \lor \neg y_3)$

$\ldots$

$(x_7 \land y_7) \equiv (\neg x_8 \lor \neg y_8)$

$(x_1 \land y_1) \equiv (
eg x_2 \lor 
eg y_2)$

$(x_2 \land y_2) \equiv (
eg x_3 \lor 
eg y_3)$

$\ldots$

$(x_7 \land y_7) \equiv (
eg x_8 \lor 
eg y_8)$

Accepted Answer

162

Answer

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

Рассмотрим, какие пары $(x_i, y_i)$ могут переходить в какие пары $(x_{i+1}, y_{i+1})$ согласно условию $(x_i \land y_i) \equiv (
eg x_{i+1} \lor 
eg y_{i+1})$.

Левая часть $(x_i \land y_i)$ принимает значение 1 только при $(x_i, y_i) = (1, 1)$, во всех остальных случаях равна 0.

Правая часть $(
eg x_{i+1} \lor 
eg y_{i+1})$ равна 0 только при $(x_{i+1}, y_{i+1}) = (1, 1)$, во всех остальных случаях равна 1.

Таким образом, эквивалентность верна в следующих случаях:
- Если $(x_i, y_i) \in \{(0,0), (0,1), (1,0)\}$, то $(x_i \land y_i) = 0$, поэтому $(
eg x_{i+1} \lor 
eg y_{i+1}) = 0$, откуда $(x_{i+1}, y_{i+1}) = (1, 1)$.
- Если $(x_i, y_i) = (1, 1)$, то $(x_i \land y_i) = 1$, поэтому $(
eg x_{i+1} \lor 
eg y_{i+1}) = 1$, откуда $(x_{i+1}, y_{i+1}) \in \{(0,0), (0,1), (1,0)\}$.

Построим таблицу количества способов достичь каждого состояния на шаге $i$:

| Состояние | Шаг 1 | Шаг 2 | Шаг 3 | Шаг 4 | Шаг 5 | Шаг 6 | Шаг 7 | Шаг 8 |
|---|---|---|---|---|---|---|---|---|
| $(0,0)$ | 1 | 1 | 3 | 3 | 9 | 9 | 27 | 27 |
| $(0,1)$ | 1 | 1 | 3 | 3 | 9 | 9 | 27 | 27 |
| $(1,0)$ | 1 | 1 | 3 | 3 | 9 | 9 | 27 | 27 |
| $(1,1)$ | 1 | 3 | 3 | 9 | 9 | 27 | 27 | 81 |

На шаге 1 каждое из четырёх состояний может быть выбрано один раз.

На шаге 2:
- Состояния $(0,0), (0,1), (1,0)$ могут быть достигнуты только из $(1,1)$ шага 1, поэтому каждое имеет 1 способ.
- Состояние $(1,1)$ может быть достигнуто из любого из трёх состояний $(0,0), (0,1), (1,0)$ шага 1, поэтому имеет 3 способа.

На шаге 3:
- Состояния $(0,0), (0,1), (1,0)$ могут быть достигнуты только из $(1,1)$ шага 2, поэтому каждое имеет 3 способа.
- Состояние $(1,1)$ может быть достигнуто из трёх состояний шага 2, поэтому имеет $1 + 1 + 1 = 3$ способа.

Закономерность: на нечётных шагах $(0,0), (0,1), (1,0)$ имеют одинаковое количество способов, на чётных шагах $(1,1)$ имеет в 3 раза больше способов, чем каждое из остальных.

Продолжая вычисления до шага 8:
- На шаге 8 состояния $(0,0), (0,1), (1,0)$ имеют по 27 способов.
- На шаге 8 состояние $(1,1)$ имеет 81 способ.

Общее количество решений: $27 + 27 + 27 + 81 = 162$.

![Рисунок](https://ege.sdamgia.ru/formula/svg/7c/7c6ffdd9acb22e256a7f1ca275dc6fd3.svg)

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