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

Задания

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

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

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

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

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

Задание К. Ю. Полякова

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

Решение.

Приведём решение К. Ю. Полякова.

Введём обозначения A = ДЕЛ(x, А), P = ДЕЛ(x, 21) и Q = ДЕЛ(x, 35)

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

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

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

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

Истинным для всех X должно быть выражение $A \to левая круглая скобка \overlineP плюс Q правая круглая скобка .$ Упростим это выражение, раскрыв импликацию по правилу $A \to B = \overlineA плюс B:$

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

Из этой формулы видно, что $\overlineA$ может быть равно 0 (и соответственно, A может быть равно только там, где  $\overlineP плюс Q =1;$ таким образом, наибольшее возможное множество A определяется как $A_max=\overlineP плюс Q$   — множество всех чисел, которые делятся на 35 плюс множество чисел, которые не делятся на 21. Заметим, что в точности такое множество A_max нельзя получить с помощью функции ДЕЛ никаким выбором A. Итак, нам нужно множеством A перекрыть все числа, которые делятся на 35, это можно сделать, например, выбрав в качестве A любой делитель числа 35 = 5 · 7 в то же время нам нельзя перекрывать числа, которые не делятся на 35, но делятся на 21 = 3 · 7 (в этих точках $\overlineP плюс Q = 0,$ и если будет A = 1, то $\overlineA плюс \overlineP плюс Q = 0.$ Предположим, что мы выбрали некоторое значение A; тогда выражение $\overlineA$ ложно в точках A · k, где k  — натуральное число, если число A · k делится на 21, то есть A · k  =  21 · m при некотором натуральном числе m, то такое число должно (для выполнения условия $\overlineA плюс \overlineP плюс Q =1$ ) делиться на 35. Раскладываем 21 на простые сомножители: 21  =  3 · 7; для того, чтобы число A · k  =  3 · 7 · m делилось на 35, в правой части нужно добавить сомножитель 5, это и есть искомое минимальное значение A (вообще говоря, А может быть любым числом, кратным 5)

Ответ: 5.

Приведём второй способ решения:

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

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

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

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

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

…

Запишем формулу из условия в наших обозначениях $A \to левая круглая скобка \overlineD_21 плюс D_35 правая круглая скобка = 1.$ Раскроем импликацию по правилу $A \to B = \overlineA плюс B:$

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

Чтобы формула была тождественно истинной необходимо, чтобы $\overlineA = 1$ (т. е. А = 0), когда $\overlineD_21 плюс D_35 = 0.$ Тогда наибольшее множество А определяется как $A_max=\overlineD_21 плюс D_35$ Множество A_max, точно соответствующее выражению с помощью функции ДЕЛ получить невозможно. Очевидно, что А_min = D₃₅, т. е. 35  — наибольшее из чисел, соответствующих условию задачи. Меньшим может быть делитель 35, не являющийся делителем 21. Чтобы делитель 35 был решением необходимо, чтобы ни для одного из чисел, кратных ему не выполнилось условие:

$\overlineA_max = D_21 умножить на \overlineD_35 = 1.$

Разложим 35 и 21 на простые множители: 35 = 5 · 7, 21 = 3 · 7. 7  — общий делитель, не может быть решением.

Проверим 5. Вычислим «опасное» число, принадлежащее множеству $D_5 умножить на D_21,$ это 5 · 21 = 105, но 105 : 35 = 3 (остаток 0), т. е. 105 ∈ D₃₅ и для него $D_21 умножить на \overlineD_35 = 0,$ значит, 5 соответствует условию задачи.

Ответ: 5.

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

for a in range(1, 100):

k = 0

for x in range(1, 1000):

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

k += 1

if k == 999:

print(a)

break

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

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

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