Разбор решения задания 23 ЕГЭ по информатике с выводом формулы для i и j

В 2020 году на ЕГЭ 23 задание решило почти 0% учеников, сдававших информатику. Хочу предложить рассмотреть решение через побитовые цепочки. В заключении вывожу формулу для всех i и j

Задача: Сколько наборов логических переменных x₁,x₂,…,x₅,y₁,…,y₆ удовлетворяют всем условиям:

1. Упростим уравнения

используя равенства

получим

получим

получим

2. Рассмотрим случай, когда i=1, j=1

В этом случае имеем одно уравнение:

Х₁Y₁ -> X₂Y₂

a -> b = 1 в случае, когда a=0, b – любое, а когда а=1, b – тоже 1

Если X₁ или Y₁ равны нулю, то Х₂ и Y₂ могут принимать любое значение (*) – первые три строчки таблицы. В последнем случае (X₁ = 1, Y₁ = 1) Х₂ и Y₂ только единицы

Всего 4+4+4+1 корня, разместим корни в таблице

3. Рассмотрим случай, когда i=1, j=2

Выражение X₁Y₂->X₂Y₃ возьмем за основу по примеру выше, остается рассмотреть выражения с Y₁

Х₁Y₁ -> X₂Y₂

При Y₁ = 0 добавленное выражение не повлияет на решение и будет, как в предыдущем примере (первые четыре строки таблицы).

При Y₁ =1 рассмотрим два случая, когда X₁=0 (он повлияет на первую часть импликации а=0, таком случае X₂, Y₂ и Y₃ любые, четвертая строка) и второй случай X₁ = 1 и Y₁ = 1 (импликация X₁Y₁ -> X₂Y₂ получит в первой части а=1, и X₂Y₂ могут быть только единицам. После этого в X₁Y₂ -> X₂Y₃ также Y₃=1

4. Рассмотрим случай, когда i=2, j=2

Также как и в предыдущем случае сместим все номера и будем рассматривать новый X₁

X₂Y₂ -> X₃Y₃

X₂Y₁ -> X₃Y₂

Эти два мы уже посчитали, а новые два будем рассматривать в разрезе:

когда X₁=0, корни по таблице выше

когда X₁=1 Y₁=0 Y₂=0, восемь корней

когда X₁=1 Y₁=1, один корень

когда X₁=1 Y₁=0 Y₂=1, один корень

X₁Y₂ -> X₂Y₃

X₁Y₁ -> X₂Y₂

5. Таким образом можно повторить аналогично и будем получать таблицы

...

6. Итоги:

Видна закономерность и таблицу не сложно расширить

Для нужных i и j можем получить ответ по таблице суммировав ячейки или по формуле, составленной из закономерности в таблице (первая строчка – первый аргумент, первый столбец – второй, и квадрат единиц – третий)

(Например, для I=6, j=4 выделена синяя область)

256 + 64 + 48 - 4 = 364