РЕШУ ЕГЭ — информатика

Задания

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Например, 14&5  =  1110₂&0101₂  =  0100₂  =  4.

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

x&25 ≠ 0 → (x&9 = 0 → x&А ≠ 0)

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

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

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

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

Имеем импликацию Z₉Z_A → Z₂₅ или Z_{(9 or A)} → Z₂₅. Запишем число 25 в двоичной системе счисления: 25₁₀  =  11001₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 9₁₀  =  01001₂, двоичная запись искомого числа А должна содержать единичный бит в четвертом разряде (как обычно, считая справа налево, начиная с нуля).

Таким образом, наименьшее А  =  10000₂  =  16₁₀.

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

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

var

A, x: integer;

B: boolean;

begin

for A := 0 to 31 do begin

B := True;

for x := 0 to 31 do

if not (((x and 25) = 0) or ((x and 9) <> 0) or ((x and A) <> 0)) then

B := False;

if B then begin

writeln(A);

break;

end;

end.

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

for A in range(32):

B = True

for x in range(32):

if ((x&25==0) or (x&9!=0) or (x&A!=0))==0:

B=False

if B:

print(A)

break

Заметим, что можно не перебирать числа, большие 31, поскольку для записи чисел 25 и 9 хватит пяти разрядов. Программа выведет ответ 16.

Ответ: 16.

№ п/п	№ задания	Ответ
1	34510	16

Ключ