Question

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

$$
\begin{align}
(x_1 \land y_1) &\leftrightarrow (
eg x_2 \lor 
eg y_2) = 1 \
(x_2 \land y_2) &\leftrightarrow (
eg x_3 \lor 
eg y_3) = 1 \
&\vdots \
(x_7 \land y_7) &\leftrightarrow (
eg x_8 \lor 
eg y_8) = 1
\end{align}
$$

где $x_1, x_2, \ldots, x_8, y_1, y_2, \ldots, y_8$ — логические переменные?

Accepted Answer

162

Answer

Идея решения: применить метод отображений, отслеживая, какие пары значений $(x_i, y_i)$ могут переходить в пары $(x_{i+1}, y_{i+1})$ при выполнении каждого уравнения.

Проанализируем условие $(x_i \land y_i) \leftrightarrow (
eg x_{i+1} \lor 
eg y_{i+1}) = 1$. Эквиваленция истинна, когда обе части имеют одинаковое значение.

Обозначим пару $(x_i, y_i)$ как состояние. Возможны четыре состояния: $00, 01, 10, 11$.

Для каждого состояния пары $(x_i, y_i)$ определим, какие состояния $(x_{i+1}, y_{i+1})$ допустимы:

- Если $(x_i, y_i) = 00$: $x_i \land y_i = 0$, значит $
eg x_{i+1} \lor 
eg y_{i+1} = 0$, откуда $x_{i+1} = 1$ и $y_{i+1} = 1$. Переход только в $11$.
- Если $(x_i, y_i) = 01$: $x_i \land y_i = 0$, значит $
eg x_{i+1} \lor 
eg y_{i+1} = 0$, откуда переход только в $11$.
- Если $(x_i, y_i) = 10$: $x_i \land y_i = 0$, значит $
eg x_{i+1} \lor 
eg y_{i+1} = 0$, откуда переход только в $11$.
- Если $(x_i, y_i) = 11$: $x_i \land y_i = 1$, значит $
eg x_{i+1} \lor 
eg y_{i+1} = 1$, откуда $(x_{i+1}, y_{i+1}) \in \{00, 01, 10\}$.

Построим таблицу количества путей, заканчивающихся в каждом состоянии на шаге $i$:

| Состояние | Шаг 1 | Шаг 2 | Шаг 3 | Шаг 4 | Шаг 5 | Шаг 6 | Шаг 7 | Шаг 8 |
|-----------|-------|-------|-------|-------|-------|-------|-------|-------|
| 00        | 1     | 1     | 3     | 3     | 9     | 9     | 27    | 27    |
| 01        | 1     | 1     | 3     | 3     | 9     | 9     | 27    | 27    |
| 10        | 1     | 1     | 3     | 3     | 9     | 9     | 27    | 27    |
| 11        | 1     | 3     | 3     | 9     | 9     | 27    | 27    | 81    |

На шаге 1 каждое из четырёх состояний имеет по 1 пути (начальные значения).

На шаге 2:
- В состояния $00, 01, 10$ можно попасть только из $11$ (по 1 пути каждое).
- В состояние $11$ можно попасть из $00, 01, 10$ (по 1 пути каждое), итого 3 пути.

На шаге 3:
- В состояния $00, 01, 10$ можно попасть из $11$ (по 3 пути каждое).
- В состояние $11$ можно попасть из $00, 01, 10$ (по 1 пути каждое), итого 3 пути.

Закономерность: если на шаге $i$ в состояниях $00, 01, 10$ по $a$ путей, а в $11$ — $b$ путей, то на шаге $i+1$:
- В $00, 01, 10$ по $b$ путей.
- В $11$ — $3a$ путей.

Применяя эту рекуррентность до шага 8:

$$27 \cdot 3 + 81 = 81 + 81 = 162$$

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

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