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

Задания

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

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

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

¬ДЕЛ(x, А) → (¬ДЕЛ(x, 21) ∧¬ ДЕЛ(x, 35))

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

(Задание М. В. Кузнецовой)

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

Решение.

Введём обозначения: A = ДЕЛ(x, А), D₂₁ = ДЕЛ(x, 21), D₃₅ = ДЕЛ(x, 35) и D_N = ДЕЛ(x, N).

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

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

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

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

…

Тогда исходное выражение

¬ДЕЛ(x, А) → (¬ДЕЛ(x, 21) ∧¬ ДЕЛ(x, 35))

принимает вид $\overlineA \to левая круглая скобка \overlineD_21 умножить на \overlineD_35 правая круглая скобка ,$ откуда в силу правила $A \to B = \overlineA плюс B$ получаем:

$\overlineA \to левая круглая скобка \overlineD_21 плюс \overlineD_35 правая круглая скобка = A плюс \overlineD_21 умножить на \overlineD_35.$

Заметим, что второе слагаемое принимает значение 0 для чисел кратных 21 или 35, то есть для чисел вида 21k и 35n, где k и n натуральные. Чтобы логическая сумма была тождественно истинной, для чисел указанного вида первое слагаемое должно обращаться в 1. Следовательно, число А должно быть таким, чтобы любое из чисел 21k и 35n делилось на него нацело. Общие делители чисел 21k и 35n, не зависящие от k и n,  — суть числа 1 и 7. Наибольшее из них равно 7.

Ответ: 7.

Примечание.

Если бы требовалось определить наименьшее натуральное А, обеспечивающее истинность исходного выражения для всех чисел Х, можно было бы начать анализ с наименьшего натурального числа  — с числа 1, и убедиться, что оно и является искомым: посылка импликации для числа 1 ложна, а значит, сама импликация истинна.

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

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

k = 0

for x in range(1, 1000):

if (x % a != 0) <= ((x % 21 != 0) and (x % 35 != 0)):

k += 1

if k == 999:

print(a)

break

Аналоги к заданию № 8106: 9320 9321 9322 ...9320 9321 9322 27412 68516 Все

Раздел кодификатора ФИПИ: 1.5.1 Высказывания, логические операции, кванторы, истинность высказывания

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

Андрей Андреев 13.06.2015 14:07

Обозначим функцию как D%аргумент_m% и упростим эквивалентными выражениями

!DA -> (!D21&&!D35) ==

!DA -> !(D21||D35) == // Закон де Моргана

(D21||D35) -> DA ==    // Закон контрапозиции

!(D21||D35) || DA     // Свойство импликации

Из последнего следует, что DA должно быть истинно, когда натуральное число x делится на 21 или 35, чтобы получить тождество. Значит, А должно делить x нацело, если оно делится на 21 или 35 нацело. Максимальное такое число это НОД 21 и 35, то есть 7.