Задание №61683 ЕГЭ Информатике

Пусть есть m переменных x₁, x₂, x₃, …, x_m-1, x_m и n переменных y₁, y₂, y₃, … y_n-1, y_n.

И пусть есть (m−1)*(n−1) уравнений вида (x_i∧y_j→x_i+1∧y_j)∧(x_i∧y_j→x_i∧y_j+1)=1 для всех i<m и j<n. Конъюнкция двух выражений равна 1 тогда и только тогда, когда каждое из двух выражений равно 1. Следовательно, каждая из импликаций истинна.

Воспользуемся тем, что выражение A→B равносильно A≤B. Это значит, что x_i∧y_j≤x_i+1∧y_j и x_i∧y_j≤x_i∧y_j+1 для всех i<m и j<n. Исходя из этого, запишем значения всевозможных конъюнкций в таблицу, в которой значения в каждой строке и каждом столбце, кроме, возможно, последних, не убывают.

Рассмотрим ячейки таблицы со значениями 1, расположенные не в последней строке и не в последнем столбце. Выберем из них ячейки с минимальным номером строки k, а среди них выберем ячейку с минимальным номером столбца l. Это означает, что x_k∧y_l=1, а все конъюнкции x_i∧y_l=0, x_k∧y_j=0 и x_i∧y_j=0, где i<k и j<l. Отсюда следует, что x_k=1 и y_l=1, а все x_i=0 и y_j=0, где i<k и j<l, поэтому первые (k−1) строка и (l−1) столбец полностью состоят из нулей.

Внутри каждой строки и каждого столбца, кроме, возможно, последних, значения расположены по принципу не убывания, поэтому все клетки строки k правее выбранной ячейки, а также все клетки столбца l ниже выбранной ячейки, тоже должны быть равны 1. Поэтому x_i=1 при k≤i≤m и y_j=1 при l≤j≤n, откуда следует, что весь правый нижний прямоугольник состоит из единиц.

Получаем, что для нашего выбора ячейки существует ровно одна таблица значений конъюнкций и ровно один набор переменных. Поскольку ячейку со значением 1, находящуюся не в последнем столбце и не в последней строке, можно выбрать (m−1)*(n−1) способами, следовательно, существует столько же таблиц значений конъюнкций и столько же наборов переменных.

Теперь рассмотрим случай, когда такой ячейки нет, то есть на пересечении первых (m−1) строк и первых (n−1) столбцов стоят только нули. Это означает, что x_i=0 при i<m или y_j=0 при j<n (возможно, одновременно).

Если x_i=0 при i<m, то x_m и все y_j могут принимать любые значения, то есть существует 2*2n вариантов наборов переменных. Если y_j=0 при j<n, то y_n и все x_i могут принимать любые значения, то есть существует 2*2m вариантов.

Осталось посчитать случаи, которые мы посчитали дважды. Если x_i=0 при i<m и y_j=0 при j<n, то эти наборы мы посчитали 2 раза. В этих случаях x_m и y_n могут быть любыми, поэтому имеем 4 лишних случая.

В итоге получаем формулу (m−1)*(n−1)+2ⁿ⁺¹+2^m+1−4.

Подставляя значения m  =  6 и n  =  7 получаем:

 

(6 − 1) · (7 − 1) + 2^{6 + 1} + 2^{7 + 1} − 4  =  410.