Автор статьи: Андрей Роженцов
В этой статье мы продолжим разбирать задание № 15 из ЕГЭ по информатике, но теперь сосредоточимся на арифметических операциях. Если в предыдущих заданиях (например, с множествами и отрезками) можно было применить перебор значений x, то здесь ключевую роль играет анализ логических и арифметических условий.
Перед тем как перейти к заданиям, вспомним из математики, что такое НОК.
НОК (наименьшее общее кратное) — наименьшее натуральное число, которое делится нацело на каждое из двух или более натуральных чисел.
Алгоритм нахождения НОК:
- Разложить числа на простые множители
- Найти в разложении меньшего числа множители, не вошедшие в разложение большего
- Добавить эти множители в разложение большего числа
Пример
Найдём НОК для чисел 20 и 42.
-
42 = 2 × 3 × 7\
20 = 2 × 2 × 5 -
В разложении числа 20 две двойки и одна пятёрка. В разложении 42 — только одна двойка и нет пятёрок
-
Добавляем недостающие множители\
2 × 3 × 7 × 2 × 5 = 420
НОК для чисел 20 и 42 равно 420. 420 : 20 = 21, 420 : 42 = 10
Правило: если число делится на два других числа, то оно делится на их НОК.
Задача 1: простое условие
По условию задачи выражение ДЕЛ(x, A) проверяет, что число х делится на А. Если это так, то ДЕЛ(x, A) = 1, в противном случае ДЕЛ(x, A) = 0. Например, число 10 делится на 2, поэтому ДЕЛ(10, 2) = 1, а на 3 не делится: ДЕЛ(10, 3) = 0.
Найдём, при каких значениях x выражение будет истинным. Между утверждениями ДЕЛ(x, 30) и ДЕЛ(15, x) стоит логическое сложение. Это значит, что если хотя бы одно из утверждений истинно, то и всё выражение будет истинным.
ДЕЛ(x, 30) — утверждение проверяет, что х делится на 30. Подходящие числа: 30, 60, 90 и т. д.
ДЕЛ(15, х) — утверждение проверяет, что 15 делится на х. Подходящие числа: 1, 3, 5, 15.
По условию нам необходимо минимальное число больше 1, подходящее хотя бы под одно условие. Это 3.
Проверка: ДЕЛ(x, 30) ∨ ДЕЛ(15, x) = ДЕЛ(3, 30) ∨ ДЕЛ(15, 3) = 0 ∨ 1 = 1
Ответ: 3
Задача 2: анализ выражения
Найдём те значения х, при которых число А будет влиять на выражение и делать его истинным. Если выражение в первой скобке ¬(ДЕЛ(x, 3) ∧ ДЕЛ(x, 5)) = 1, то выражение примет вид 1 ∨ (A ≥ 42 − x) = 1 и число А никак не будет влиять на результат. А если ¬(ДЕЛ(x, 3) ∧ ДЕЛ(x, 5)) = 0, то выражение в скобке (A ≥ 42 − x) обязательно должно быть истинным.
Если ¬(ДЕЛ(x, 3) ∧ ДЕЛ(x, 5)) = 0, то (ДЕЛ(x, 3) ∧ ДЕЛ(x, 5)) = 1. Логическое произведение равно 1 только в том случае, когда оба множителя равны 1, т. е. ДЕЛ(x, 3) = 1 и ДЕЛ(x, 5) = 1. ДЕЛ(x, 3) равен 1, когда х делится на 3, а ДЕЛ(x, 5) = 1, когда х делится на 5.
Чтобы число делилось и на 3, и на 5, оно должно делиться на 15.
Правило: если число делится на два других, то оно делится на их НОК.
Получаем, что для чисел, которые делятся на 15, условие A ≥ 42 − x должно быть истинным.
Выпишем числа, которые делятся на 15: 15, 30, 45, 60 и т. д. Подставим в неравенство несколько первых чисел.
- X = 15, A ≥ 42 − x, A ≥ 42 − 15, A ≥ 27
- X = 30, A ≥ 42 − x, A ≥ 42 − 30, A ≥ 12
- X = 45, A ≥ 42 − x, A ≥ 42 − 45, A ≥ −3
Т. к. все числа, которые мы подставляли, были положительными и шли по возрастанию, то выражение 42 − х становилось меньше с каждым новым х. По условию задачи необходимо, чтобы неравенство выполнялось для любого числа х, поэтому дальше подставлять нет смысла. A ≥ 27 — условие, чтобы при любом х неравенство было верным. Минимальное А, подходящее под это условие, — 27.
Ответ: 27
Задача 3: сложная формула
Упростим выражение:
(¬ДЕЛ(x, A) ∧ ДЕЛ(x, 35)) → (¬ДЕЛ(x, 21) ∨ ¬ДЕЛ(x, 35)) =\
= ¬ (¬ДЕЛ(x, A) ∧ ДЕЛ(x, 35)) ∨ (¬ДЕЛ(x, 21) ∨ ¬ДЕЛ(x, 35)) =\
= ДЕЛ(x, A) ∨ ¬ДЕЛ(x, 35) ∨ ¬ДЕЛ(x, 21) ∨ ¬ДЕЛ(x, 35) =\
= ДЕЛ(x, A) ∨ ¬ДЕЛ(x, 35) ∨ ¬ДЕЛ(x, 21)
После преобразований получается три скобки, объединённые логическим сложением. Если выражение в одной из скобок будет равно 1, то и всё выражение будет равно 1.
Рассмотрим только тот случай, когда ¬ДЕЛ(x, 35) = 0 и ¬ДЕЛ(x, 21) = 0, т. е. ДЕЛ(x, 35) = 1 и ДЕЛ(x, 21) = 1. При других значениях выражение будет истинно независимо от числа А. В этой ситуации обязательно должно выполняться условие ДЕЛ(x, A) = 1, только в этом случае всё выражение будет истинным.
Запишем это условие в письменной форме: если х делится на 35 и х делится на 21, то он должен делиться на А. Если число делится на 21 и на 35, то оно делится и на их НОК. Найдём его.
21 = 3 × 7, 35 = 5 × 7, НОК(21, 35) = 3 × 5 × 7 = 105
Упростим условие: если число делится на 105, то оно должно делиться на А.
Выпишем числа, делящиеся на 105: 105, 210, 315, 420, 525 и т. д. Их наибольший общий делитель — 105, поэтому А = 105.
Ответ: 105
Задача 4: вспоминаем алгебру
Выражение должно быть истинным. Последнее действие — логическое умножение, значит, оба множителя должны быть равны 1, т. е. ((ДЕЛ(x, 36) ∧ ДЕЛ(x, 42)) → ДЕЛ(x, A)) = 1 и (A × (A − 25) \< 25 × (A + 200)) = 1.
- Начнём с первого выражения: ((ДЕЛ(x, 36) ∧ ДЕЛ(x, 42)) → ДЕЛ(x, A)) = 1
Последнее действие — импликация. Если (ДЕЛ(x, 36) ∧ ДЕЛ(x, 42) = 0, то 0 → ДЕЛ(x, A) =1, то есть выражение от А не зависит. Но если (ДЕЛ(x, 36) ∧ ДЕЛ(x, 42) = 1, то выражение ДЕЛ(x, A) обязательно должно быть истинным. Логическое умножение равно 1, когда оба множителя равны 1, т. е. ДЕЛ(x, 36) = 1 и ДЕЛ(x, 42) = 1.
Получается, что если х делится на 36 и на 42, то он должен делиться ещё и на А. Разложим числа на простые множители: 36 = 2 × 2 × 3 × 3, 42 = 2 × 3 × 7. Числа, которые делятся и на 36 и на 42, делятся на НОК(36,42) = 2 × 2 × 3 × 3 × 7 = 252. Примеры таких чисел: 252, 504, 756, 1008 и т. д. Каждое из этих чисел должно делиться на А.
- Перейдём ко второму выражению: (A × (A − 25) \< 25 × (A + 200)) = 1
Неравенство должно быть верным. Раскроем скобки и решим его.
$A^2 − 25A < 25A + 5000$\
$A^2 − 50A − 5000 < 0$
Решаем уравнение:
$A^2 − 50A − 5000 = 0$\
$D = b^2 − 4ac = (−50)^2 − 4 × 1 × (−5000) = 2500 + 20 000 = 22 500$\
$A = (50 + \sqrt{22 500}) / 2 = (50 + 150) : 2 = 100, A = (50 − \sqrt{22 500}) : 2 = (5 − 150) : 2= −50$
Отмечаем найденные значения А на числовой прямой и подставляем числа из каждого промежутка в уравнение, определяем знаки.
Получаем, что −50 \< A \< 100
Подводим итог:
- Каждое из чисел, делящихся на 252 (например, 252, 504, 756, 1008 и т. д.), должно делиться на А
- −50 \< A \< 100
- А — наибольшее натуральное число из подходящих (по условию задачи)
Для чисел, которые делятся на 252, находим общий делитель, но проверяем, чтобы он был меньше 100.
Найдём наибольший, но меньше 100 делитель для числа 252. Для этого рассмотрим его как произведение двух его делителей.
252 = 2 × 126 = 3 × 84 = 4 × 63
Дальше рассматривать все пары нет смысла, т. к. при увеличении первого множителя уменьшается второй, а нужно найти число А, меньшее 100, но как можно большее. Значит, А = 84.
Ответ: 84
Итог
- В таких задачах используются свойства делимости чисел. Если число делится на два других, то оно делится на их НОК — наименьшее общее кратное. Например, если х делится на 3 и на 5, значит, оно делится и на 15.
- Другие способы решения мы рассматривали в предыдущих статьях. Основной ключ к решению — это вопрос: «При каких значениях х число А будет влиять на выражение?»