Question

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

$(x_1 	o (x_2 \land y_2)) \land (y_1 	o y_2) = 1$

$(x_2 	o (x_3 \land y_3)) \land (y_2 	o y_3) = 1$

$\ldots$

$(x_8 	o (x_9 \land y_9)) \land (y_8 	o y_9) = 1$

В ответе укажите количество таких наборов.

Accepted Answer

64

Answer

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

Каждое условие имеет вид $(x_i 	o (x_{i+1} \land y_{i+1})) \land (y_i 	o y_{i+1}) = 1$. Это означает, что обе импликации должны быть истинны одновременно.

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

| $(x_i, y_i)$ | Допустимые $(x_{i+1}, y_{i+1})$ |
|---|---|
| $(0, 0)$ | $(0, 0), (0, 1), (1, 0), (1, 1)$ |
| $(0, 1)$ | $(0, 1), (1, 1)$ |
| $(1, 0)$ | $(1, 1)$ |
| $(1, 1)$ | $(1, 1)$ |

Применим динамическое программирование. Обозначим через $dp[i][s]$ количество способов достичь состояния $s$ на позиции $i$, где $s \in \{(0,0), (0,1), (1,0), (1,1)\}$.

Инициализация: $dp[1][(0,0)] = 1$, $dp[1][(0,1)] = 1$, $dp[1][(1,0)] = 1$, $dp[1][(1,1)] = 1$.

Переходы для $i = 2, 3, \ldots, 9$:

| Состояние | $x_1y_1 = 00$ | $x_1y_1 = 01$ | $x_1y_1 = 10$ | $x_1y_1 = 11$ |
|---|---|---|---|---|
| $x_2y_2 = 00$ | 1 | 1 | 1 | 1 |
| $x_2y_2 = 01$ | 1 | 2 | 3 | 4 |
| $x_2y_2 = 10$ | 1 | 1 | 1 | 1 |
| $x_2y_2 = 11$ | 1 | 4 | 8 | 13 |

Продолжаем заполнение таблицы для позиций $3, 4, \ldots, 9$:

| Позиция | $(0,0)$ | $(0,1)$ | $(1,0)$ | $(1,1)$ |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 2 | 1 | 4 |
| 3 | 1 | 3 | 1 | 8 |
| 4 | 1 | 4 | 1 | 13 |
| 5 | 1 | 5 | 1 | 19 |
| 6 | 1 | 6 | 1 | 26 |
| 7 | 1 | 7 | 1 | 34 |
| 8 | 1 | 8 | 1 | 43 |
| 9 | 1 | 9 | 1 | 53 |

Общее количество решений равно сумме всех значений на позиции 9:

$$1 + 9 + 1 + 53 = 64$$

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

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