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

Задания

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

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

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

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

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

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

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

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

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

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

Решим задание с помощью языка программирования 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 17) <> 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&17!=0) or (x&A!=0))==0:

B=False

if B:

print(A)

break

Ответ: 8.

№ п/п	№ задания	Ответ
1	34506	8

Ключ