"Убойная задача" B10

Прошел ЕГЭ по информатике. Не без неожиданностей. Некоторые задачи получили непривычную и незнакомую форму. И сложность их оказалась выше ожидаемой. Ученики, проштудировавшие всевозможные «самые полные» и «самые последние» сборники, растерялись. Судя, по высказываниям на форумах (http://pedsovet.org/forum/index.php?showtopic=6336&st=250&p=193843&#entry193843), учителя не одобрили такой поворот событий.

Действительно, задача B10 не очень-то соответствует заявленной спецификации «умение строить и преобразовывать логические выражения».

Один из вариантов задачи B10:

Сколько решений имеет система логических уравнений

(Х₁ /\ X₂ ) V (не Х₁/\ не Х₂) V (X₁=X₃) = 1
(Х₂ /\ X₃ ) V (не Х₂/\ не Х₃) V (X₂=X₄) = 1
(Х₃ /\ X₄ ) V (не Х₃/\ не Х₄) V (X₃=X₅) = 1
…

(Х₇ /\ X₈) V (не Х₇/\ не Х₈) V (X₇=X₉) = 1
(Х₈/\ X₉ ) V (не Х₈/\ не Х₉) V (X₈=X₁₀) = 1

«Умение строить и преобразовывать логические выражения» — только один из этапов решения задачи. Но так ли далеко от информатики ушли остальные этапы? По-моему, здесь все в рамках предмета — умение анализировать и выстраивать цепочку логических суждений, умение строить формализованную модель и выбирать подходящие для анализа и синтеза информационные структуры. Задача может быть решена, разумеется, разными способами. Я бы предложила такое решение.

1. Прежде всего, на основе тождественных преобразований приведем систему к виду:

(Х₁  = X₂ ) V (X₁=X₃) = 1
(Х₂  = X₃ ) V (X₂=X₄) = 1
(Х₃  = X₄ ) V (X₃=X₅) = 1
…

(Х₇  = X₈) V (X₇=X₉) = 1
(Х₈ = X₉) V (X₈=X₁₀) = 1

2. В отличие от остальных переменных, X₁₀ встречается в системе один раз и интуитивное желание — начать решать систему с последнего уравнения. Рассмотрим X₁₀=0. Тройки значений, удовлетворяющие при этом последнему уравнению, такие:
X₁₀ = 0, X₉=0, X₈=0;          X₁₀ = 0, X₉=1, X₈=1;          X₁₀ = 0, X₉=1, X₈=0;

Нам важно здесь, что в первых двух тройках X₉ и X₈ имеют одинаковые значения. Тогда для каждой из них в предпоследнем уравнении существует только одно значение X₇, удовлетворяющее этому уравнению. А именно, для первой тройки X₇ = 0, а для второй X₇ = 1. Для третьей тройки подойдут уже оба значения.

Дальше, продвигаясь шаг за шагом снизу вверх к первому уравнению, рассуждаем аналогично и ход  рассуждения удобно иллюстрировать в виде дерева, по которому мы продвигаемся в поисках решений. Каждый новый узел — это значение соответствующей переменной. Если значения двух смежных узлов различны, то из узла будут выходить две ветви, иначе — одна.

Таблица внизу заменяет описанное дерево. Цветом выделены узлы, в котором происходит ветвление.

	X10	X9	X8	X7	X6	X5	X4	X3	X2	X1
1	0	0	0	0	0	0	0	0	0	0
2		1	1	1	1	1	1	1	1	1
3			0	0	0	0	0	0	0	0
4				1	1	1	1	1	1	1
5					0	0	0	0	0	0
6						1	1	1	1	1
7							0	0	0	0
8								1	1	1
9									0	0
10										1

Таким образом, мы получаем 10 решений.

Эти 10 решений были получены в предположении, что X₁₀ = 0. Точно также находятся решения (их количество) в предположении, что X₁₀ = 1. Итого — 20 решений.

Когда решение получено, то оно кажется совсем не сложным, но на его поиск у ученика уйдет, конечно, не 10 и не 15 минут. То есть, эта задача, не C4, а B10  — реальный барьер для 100-балльников. Может быть, так и было задумано? Взять врасплох? :)

Разбор подобных задач можно уже(!) посмотреть на сайте Константина Юрьевича Полякова.