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

Задания

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

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

¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4))

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

Решение. Введём обозначения A  =  ДЕЛ(x, А), P  =  ДЕЛ(x, 6) и Q  =  ДЕЛ(x, 4).

Введём множества:

A  — множество натуральных чисел, для которых выполняется условие A;

P  — множество натуральных чисел, для которых выполняется условие P;

Q  — множество натуральных чисел, для которых выполняется условие Q;

истинным для всех X должно быть выражение $\overlineA \to левая круглая скобка P \to \overlineQ правая круглая скобка .$

Упростим это выражение, раскрыв импликацию по правилу $A \to B = \overlineA плюс B:$

$\overlineA \to левая круглая скобка P \to \overlineQ правая круглая скобка = A плюс левая круглая скобка P \to \overlineQ правая круглая скобка = A плюс \overlineP плюс \overlineQ$

из этой формулы видно, что множество A должно перекрыть множество, которое не перекрыто множеством  $\overlineP плюс \overlineQ,$ то есть перекрыть множество $\overline\overlineP плюс \overlineQ = P умножить на Q.$ Множество P · Q  — это множество всех чисел, которые делятся одновременно на 4 и 6 (все числа, кратные 4 и 6), то есть 12, 24, 36 и так далее. (заметим, что 12  — это наименьшее общее кратное чисел 4 и 6). Для того, чтобы перекрыть эти числа, можно выбрать в качестве A любой делитель числа 12, то есть 1, 2, 3, 4, 6 или 12; наибольшее из этих чисел  — 12.

Ответ: 12.

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

for a in range(100, 0, -1):

k = 0

for x in range(1, 1000):

if (x % a != 0) <= ((x % 6 == 0) <= (x % 4 != 0)):

k += 1

if k == 999:

print(a)

break

№ п/п	№ задания	Ответ
1	8106	12

Ключ