Вчера прошла основная волна ЕГЭ по информатике. Экзаменационная работа ничем не удивила, кроме 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\).
