Сложная задача B18 за пару минут
Создание: 15.01.2017
В ЕГЭ по информатике появился новый непростой класс задач, для решения которых нужно уметь работать с логическими выражениями, множествами и двоичными числами.

Вот пример такой задачи:

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула

(x & 29 ≠ 0) → ((x & 12 = 0) → (x & А ≠ 0))

тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

Задача сложна по нескольким причинам.

Во-первых, в задаче сознательно смешиваются логические и алгебраические выражение. Например, x & 12 – это алгебраическое выражение, несмотря на то, что для чисел выполняется поразрядная конъюнкция, и результатом этого выражения может быть любое число. При этом выражение x & 12 = 0 уже является логическим, оно может принимать только два значения истина, например, для x=16 или ложь для x=3 (почему так, будет объяснено ниже). Для того чтобы отличать эти два разных равенства, в тексте мы будем использовать знак  «двойного равно», которое будет показывать нам тождественность. Итак исходное выражение выглядит так:

(x & 29 ≠ 0) → ((x & 12 = 0) → (x & А ≠ 0)) == 1

Во-вторых, в задаче необходимо не просто найти, число А, удовлетворяющее условию, но и иметь доказательство, что это число подойдет для всех натуральных чисел x и к тому же найденное A минимальное из всех возможных.

В начале, выполним формальные логические преобразования. Заменим логическое следование – простыми логическими операциями: A→B == не(A) или B

(не(x & 29 ≠ 0)) или (не(x & 12 = 0) или (x & А ≠ 0)) == 1

Инвертируем логическое отрицание: не(A=0) == A≠ 0

(x & 29 = 0) или (x & 12 ≠ 0) или (x & А ≠ 0) == 1

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

Пришло время разобраться с тем, как применяется операция поразрядное логическое умножение. Так как поразрядные логические  операции применяются к двоичным числам, переведем десятичное число 29 в его двоичный эквивалент. 2910 = 16+8+4+1 = 111012

Первое простое логическое выражение: x & 29 = 0.

Давайте убедимся, что мы одинаково понимаем, что означает это выражение. В нем написано о том, что мы берем произвольное число x и утверждаем, что результат будет равен нулю. Легко проверить, что

Выражение 1 & 29 = 0 – ложь,
так поразрядное умножение 000012 & 111012 дает в результате 000012

Выражение 2 & 29 = 0 – истина,
так поразрядное умножение 000102 & 111012 дает в результате 000002

Нетрудно заметить, что поразрядное умножение 11101на любое двоичное число, имеющее единицу в первом, третьем, четвертом или пятом разряде будет давать значение, отличное от нуля, например:

111012
000112
-----
000102

Это значит, что любые натуральные двоичные числа, содержащие единицы в указанных разрядах, будут приводить к ложности первого выражения.

Аналогично, разбираем второе простое логическое выражение. Десятичное число 1210 = 11002 Логическое выражение x & 12 ≠ 0 будет ложным, (то есть x & 12 = 0) при любом двоичном числе, имеющем нули в третьем и четвертых разрядках, например,

11002
00112
-----

00002

Теперь, зная правило для первого и второго выражения у нас есть возможность получить множество «проблемных» натуральных чисел x, для которых и первое и второе логическое выражение будет ложным. Для того чтобы найти это множество чисел, найдем пересечение множеств чисел для первого и второго правила

+++ +
111012
 ++
000112
-----
100012

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

10001 - это «минимальный проблемный х», при котором первые два выражения будут ложны. При желании можно построить бесконечное количество таких чисел x:

0010001
0110001
1110001

и т.д.

Для истинности всего исходного логического выражения, третье выражение (x & А ≠ 0) должно быть истинно для найденного минимального «проблемного х». Понятно, что если число A будет равно 10001, то его поразрядное логическое умножение с x=10001 даст число, отличное от нуля. Причем это число будет минимальным, все другие числа A, удовлетворяющие 0110001, 1110001 будут больше.

Итак, ответ задачи A = 100012 = 1710.

При всей сложности задачи, она решается всего за пару минут.

P.S.

Больше задач такого типа вы найдете здесь: http://kpolyakov.spb.ru/school/ege/gen.php?action=viewAllEgeNo&egeId=18