ЕГЭ–2026, информатика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип Д15 № 10508 Добавить в вариант

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 1100₂&0110₂ = 0100₂ = 4.

Для какого наибольшего целого числа А формула

х&А $не равно 0$ → (x&36 = 0 → х&6 $не равно 0$ )

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

Спрятать решение

Решение.

Преобразуем выражение по законам алгебры логики:

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.

Имеем импликацию Z₃₆Z₆ → Z_A или Z_{(36 or 6)} → Z_A. Запишем числа 36 и 6 в двоичной системе счисления: 36₁₀  =  100100₂, 6₁₀  =  110₂, найдем побитовую дизъюнкцию: 100110. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут не быть) только первый, второй или пятый биты (как обычно, считая справа налево, начиная с нуля).

Тем самым, наибольшее А = 100110₂  =  38₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

var

A, x: integer;

B: boolean;

begin

for A := 0 to 63 do begin

B := True;

for x := 0 to 63 do

if not (((x and 6) <> 0) or ((x and 36) <> 0) or ((x and (63-A)) = 0)) then

B := False;

if B then begin

writeln((63-A));

break;

end;

end.

Приведём аналогичное решение на языке Python.

for A in range(64):
    B = True
    for x in range(64):
        if ((x&(63-A)==0) or (x&36!=0) or (x&6!=0))==0:
            B=False
    if B:
        print(63-A)
        break

Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 6 и 36 хватит шести разрядов. Программа выведет ответ 38.

Ответ: 38.

Спрятать решение · Помощь