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 < 5$, $j < 6$?

Accepted Answer

208

Answer

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

**Переформулировка условия**

Конъюнкция двух импликаций равна 1 тогда и только тогда, когда каждая импликация истинна. Используя эквивалентность $A 	o B \equiv A \le B$, получаем:
- $x_i \land y_j \le x_i \land y_{j+1}$ для всех $i < 5$, $j < 6$;
- $x_i \land y_j \le x_{i+1} \land y_j$ для всех $i < 5$, $j < 6$.

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

**Анализ структуры таблицы**

Рассмотрим две категории случаев.

*Случай 1: существует единица в первых 4 строках и первых 5 столбцах.*

Выберем ячейку $(k, l)$ с минимальным номером строки среди всех единиц в этой области, а среди них — с минимальным номером столбца. Тогда:
- $x_k \land y_l = 1$, откуда $x_k = 1$ и $y_l = 1$;
- все $x_i \land y_j = 0$ при $i < k$ или $j < l$, откуда $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 4$ и $1 \le l \le 5$ определяет ровно один набор переменных. Таких пар $(5-1) 	imes (6-1) = 4 	imes 5 = 20$.

*Случай 2: все единицы находятся только в последней строке или только в последнем столбце.*

Это означает, что $x_i = 0$ при $i < 5$ или $y_j = 0$ при $j < 6$ (или оба условия).

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

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

**Итоговый подсчёт**

Общее количество наборов:
$$20 + 188 = 208$$

![Рисунок](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Алгоритмы и исполнителиЕГЭ по информатике