Question

Сколько наборов логических переменных удовлетворяют условиям:

$$\left((x_i \land y_j) 	o (x_i \land y_{j+1})ight) \land \left((x_i \land y_j) 	o (x_{i+1} \land y_j)ight) = 1$$

для всех $i < 6$, $j < 7$?

Accepted Answer

410

Answer

Идея решения: представить конъюнкции $x_i \land y_j$ в виде таблицы и использовать свойство импликации, чтобы вывести структуру допустимых таблиц.

**Шаг 1. Переформулировка условия**

Конъюнкция двух импликаций равна 1 тогда и только тогда, когда каждая импликация истинна. Используя эквивалентность $A 	o B \equiv A \le B$, получаем:

$$x_i \land y_j \le x_i \land y_{j+1} \quad 	ext{и} \quad x_i \land y_j \le x_{i+1} \land y_j$$

для всех $i < 6$, $j < 7$.

Это означает, что значения в таблице $T[i][j] = x_i \land y_j$ не убывают вдоль каждой строки и каждого столбца (кроме, возможно, последних).

**Шаг 2. Анализ структуры таблицы**

Рассмотрим ячейки таблицы со значением 1, расположенные не в последней строке и не в последнем столбце. Выберем ячейку с минимальным номером строки $k$, а среди них — с минимальным номером столбца $l$.

Из условия монотонности:
- Все ячейки $(i, j)$ с $i < k$ или $j < l$ содержат 0.
- Все ячейки $(i, j)$ с $i \ge k$ и $j \ge l$ содержат 1.

Это означает, что $x_k = 1$, $y_l = 1$, все $x_i = 0$ при $i < k$, все $y_j = 0$ при $j < l$, и все $x_i = 1$ при $i \ge k$, все $y_j = 1$ при $j \ge l$.

Каждый выбор пары $(k, l)$ с $1 \le k \le 5$ и $1 \le l \le 6$ определяет ровно один набор переменных. Таких пар $(5 	imes 6) = 30$.

**Шаг 3. Случай без единиц в верхнем левом прямоугольнике**

Если в первых 5 строках и первых 6 столбцах нет единиц, то либо $x_i = 0$ для всех $i < 6$, либо $y_j = 0$ для всех $j < 7$ (или оба условия одновременно).

- Если $x_i = 0$ при $i < 6$: переменная $x_6$ и все $y_j$ произвольны → $2^{1+7} = 256$ наборов.
- Если $y_j = 0$ при $j < 7$: переменная $y_7$ и все $x_i$ произвольны → $2^{1+6} = 128$ наборов.
- Если оба условия: $x_6$ и $y_7$ произвольны → $2^2 = 4$ набора (учтены дважды).

По принципу включения-исключения: $256 + 128 - 4 = 380$.

**Шаг 4. Итоговая формула**

Общее количество наборов:

$$(m-1)(n-1) + 2^n + 2^m - 4$$

где $m = 6$, $n = 7$:

$$(6-1)(7-1) + 2^7 + 2^6 - 4 = 5 \cdot 6 + 128 + 64 - 4 = 30 + 128 + 64 - 4 = 218$$

Однако при более внимательном анализе граничных случаев (когда последняя строка или последний столбец содержат единицы) получается:

$$(m-1)(n-1) + 2^{n+1} + 2^{m+1} - 4 = 30 + 256 + 128 - 4 = 410$$

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=65330)

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=65331)

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=65332)

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