Question

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

- $x_1 	o y_1 = 1$
- $(x_2 	o (x_1 \land y_2)) \land (y_2 	o y_1) = 1$
- $(x_3 	o (x_2 \land y_3)) \land (y_3 	o y_2) = 1$
- $\ldots$
- $(x_7 	o (x_6 \land y_7)) \land (y_7 	o y_6) = 1$

Accepted Answer

36

Answer

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

Каждую пару переменных $(x_i, y_i)$ можно представить как состояние, принимающее одно из четырёх значений: $00, 01, 10, 11$.

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

Импликация $a 	o b$ истинна при всех комбинациях, кроме $a = 1, b = 0$. Проанализируем каждое состояние:

- **Состояние $00$** (т. е. $x_i = 0, y_i = 0$): условие $y_{i+1} 	o y_i$ требует $y_{i+1} = 0$; условие $x_{i+1} 	o (x_i \land y_{i+1})$ требует $x_{i+1} 	o 0$, что истинно при любом $x_{i+1}$. Допустимые переходы: $00, 10$.

- **Состояние $01$** (т. е. $x_i = 0, y_i = 1$): условие $y_{i+1} 	o y_i$ требует $y_{i+1} 	o 1$, что истинно при любом $y_{i+1}$; условие $x_{i+1} 	o (x_i \land y_{i+1})$ требует $x_{i+1} 	o 0$, что истинно при любом $x_{i+1}$. Допустимые переходы: $00, 01, 10, 11$.

- **Состояние $10$** (т. е. $x_i = 1, y_i = 0$): условие $y_{i+1} 	o y_i$ требует $y_{i+1} = 0$; условие $x_{i+1} 	o (x_i \land y_{i+1})$ требует $x_{i+1} 	o 0$, что истинно при любом $x_{i+1}$. Допустимые переходы: $00, 10$.

- **Состояние $11$** (т. е. $x_i = 1, y_i = 1$): условие $y_{i+1} 	o y_i$ требует $y_{i+1} 	o 1$, что истинно при любом $y_{i+1}$; условие $x_{i+1} 	o (x_i \land y_{i+1})$ требует $x_{i+1} 	o y_{i+1}$. Допустимые переходы: $00, 01, 11$.

Из первого условия $x_1 	o y_1 = 1$ исключаем состояние $10$ для первой пары.

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

| Состояние | Шаг 1 | Шаг 2 | Шаг 3 | Шаг 4 | Шаг 5 | Шаг 6 | Шаг 7 |
|-----------|-------|-------|-------|-------|-------|-------|-------|
| $00$      | 1     | 3     | 6     | 10    | 15    | 21    | 28    |
| $01$      | 1     | 2     | 3     | 4     | 5     | 6     | 7     |
| $10$      | 0     | 0     | 0     | 0     | 0     | 0     | 0     |
| $11$      | 1     | 1     | 1     | 1     | 1     | 1     | 1     |

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

Итоговое количество решений: $28 + 7 + 0 + 1 = 36$.

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

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