СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости



Задания
Версия для печати и копирования в MS Word
Задание 18 № 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 должно быть выражение Упростим это выражение, раскрыв импликацию по правилу

 

 

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

Ответ: 5.

 

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

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

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

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

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

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

Запишем формулу из условия в наших обозначениях . Раскроем импликацию по правилу

 

 

Чтобы формула была тождественно истинной необходимо, чтобы (т.е. А = 0), когда Тогда наибольшее множество А определяется как Множество Amax, точно соответствующее выражению с помощью функции ДЕЛ получить невозможно. Очевидно, что Аmin = D35, т. е. 35 — наибольшее из чисел, соответствующих условию задачи. Меньшим может быть делитель 35, не являющийся делителем 21. Чтобы делитель 35 был решением необходимо, чтобы ни для одного из чисел, кратных ему не выполнилось условие:

 

 

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

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

Ответ: 5.


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