previous arrow
next arrow
Slider

ЕГЭ по информатике 2020. Как решалось задание 23!

Вчера прошла основная волна ЕГЭ по информатике. Экзаменационная работа ничем не удивила, кроме 23-й задачи. Задача была не столько сложная, сколько необычная. Мне, например, она больше напомнила 10-ю задачу на элементы комбинаторики. Наверняка, будет предложено много самых разных решений. Предложу свое, которое возникло в голове при первом взгляде на задачу и заняло не более 10 минут (включая первый шок от прочтения).

Найти количество решений системы логических уравнений:

({ x }_{ i }\wedge { y }_{ j }\rightarrow { x }_{ i }\wedge { y }_{ j+1 })\wedge ({ x }_{ i }\wedge { y }_{ j }\rightarrow { x }_{ i+1 }\wedge { y }_{ j })=1

Где 1 ≤ i ≤ 8, 1 ≤ j ≤ 5;

Решим уравнение для i=1

Точно так же будет выглядеть решение для других значений i. Т.е. нам подойдут все наборы, кроме наборов:

Посчитаем общее число наборов и вычтем из него не подходящие. Это и будет ответом задачи.

Поскольку 1 ≤ i ≤ 8 ; 1 ≤ j ≤ 5, то общее число наборов равно { 2 }^{ 8 }\cdot { 2 }^{ 5 }

Наборы переменных { x }_{ i },{ x }_{ i+1 }, содержащие 10, это все наборы, кроме наборов:

Т.е. ({ 2 }^{ 8 } - 9) наборов.

Наборы переменных { y }_{ j },{ y }_{ j+1 }, содержащие 10 или 11, это все наборы, кроме наборов:

Т.е. ({ 2 }^{ 5 } - 2) наборов.

Наборы переменных { x }_{ i },{ x }_{ i+1 }, содержащие 11, но не содержащие 10 (т.к. мы их уже учли) это наборы:

Их 7 штук.

Наборы переменных { y }_{ j },{ y }_{ j+1 }, содержащие 10, это все наборы, кроме наборов:

Т.е. ({ 2 }^{ 5 } - 6) наборов.

Итак, ответ задачи: { 2 }^{ 8 }\cdot { 2 }^{ 5 }-({ 2 }^{ 8 }-9)\cdot ({ 2 }^{ 5 }-2)-7\cdot ({ 2 }^{ 5 }-6)=600.