Question

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

$(\neg(x_1 \equiv y_1)) \equiv (x_2 \equiv y_2)$ $(\neg(x_2 \equiv y_2)) \equiv (x_3 \equiv y_3)$ $\ldots$ $(\neg(x_7 \equiv y_7)) \equiv (x_8 \equiv y_8)$

$$(
eg(x_1 \equiv y_1)) \equiv (x_2 \equiv y_2)$$
$$(
eg(x_2 \equiv y_2)) \equiv (x_3 \equiv y_3)$$
$$\ldots$$
$$(
eg(x_7 \equiv y_7)) \equiv (x_8 \equiv y_8)$$

Accepted Answer

512

Answer

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

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

Проанализируем переходы. Условие $(
eg(x_i \equiv y_i)) \equiv (x_{i+1} \equiv y_{i+1})$ означает:
- Если $x_i \equiv y_i$ истинна (пара $00$ или $11$), то $x_{i+1} \equiv y_{i+1}$ должна быть ложна (пара $01$ или $10$).
- Если $x_i \equiv y_i$ ложна (пара $01$ или $10$), то $x_{i+1} \equiv y_{i+1}$ должна быть истинна (пара $00$ или $11$).

Построим таблицу переходов:

| Состояние $(x_i, y_i)$ | Возможные следующие состояния |
|---|---|
| $00$ | $01, 10$ |
| $01$ | $00, 11$ |
| $10$ | $00, 11$ |
| $11$ | $01, 10$ |

Видно, что из каждого состояния ровно 2 перехода. Обозначим через $f_i(s)$ количество путей длины $i$, заканчивающихся в состоянии $s$.

Начальное условие: $f_1(00) = f_1(01) = f_1(10) = f_1(11) = 1$ (первая пара может быть любой).

Рекуррентное соотношение:
- $f_{i+1}(00) = f_i(01) + f_i(10)$
- $f_{i+1}(01) = f_i(00) + f_i(11)$
- $f_{i+1}(10) = f_i(00) + f_i(11)$
- $f_{i+1}(11) = f_i(01) + f_i(10)$

Заметим, что $f_{i+1}(00) = f_{i+1}(11)$ и $f_{i+1}(01) = f_{i+1}(10)$ для всех $i \geq 1$.

Обозначим $a_i = f_i(00) = f_i(11)$ и $b_i = f_i(01) = f_i(10)$.

Тогда:
- $a_{i+1} = 2b_i$
- $b_{i+1} = 2a_i$

С начальными условиями $a_1 = 1, b_1 = 1$.

Вычислим последовательность:

| $i$ | $a_i$ | $b_i$ |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 4 | 4 |
| 4 | 8 | 8 |
| 5 | 16 | 16 |
| 6 | 32 | 32 |
| 7 | 64 | 64 |
| 8 | 128 | 128 |

Общее количество решений:
$$f_8(00) + f_8(01) + f_8(10) + f_8(11) = a_8 + b_8 + b_8 + a_8 = 2a_8 + 2b_8 = 2 \cdot 128 + 2 \cdot 128 = 512$$

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

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