Несколько дней назад в комментариях к задаче про возраст Шерил была предложена похожая, но более интересная и сложная задачка, сформулированная таким образом:
У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».
Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.
Назовите эти числа.
Были предложены несколько вариантов решения задачи, в том числе на Scala и C#, предполагающие достаточно грубый перебор множества возможных ответов. Тем не менее, задачу можно решить, если под рукой не оказалось ноутбука, только карандаш и листок бумаги.
Мотивация
Для начала давайте разберемся, почему решение без компьютера — не совсем пустая трата времени.
- Перебор программой в данной задаче довольно очевиден. А если ограничить себя бумажкой, получится хорошее упражнение.
- В ходе решения нам придется вспомнить различные математические свойства и приемы.
- Анализ условия позволяет существенно сократить перебор, это полезный навык и в более сложных задачах.
- Поломать голову довольно интересно, особенно если нечем заняться на скучной лекции.
- Неаккуратно написанная программа может выдать лишние результаты, которые все равно надо как-то отфильтровать
- Если бы задача попалась на олимпиаде по математике, пришлось бы выкручиваться без написания программы.
Подсказка 1: Я не знаю этих чисел
Это значит, что произведение неоднозначно раскладывается на произведение двух множителей, меньших 100.
Рассмотрим те произведения, которые так раскладываются единственным образом, назовем их однозначными.
Выделим несколько важных классов однозначных произведений:
- Произведение двух простых.
- Куб простого числа — представляется только как произведение этого числа на его квадрат.
- Произведение простого числа больше 50 на что-то еще — при любом другом разбиении на множители один из них окажется больше 100.
Примеры:
По произведению 15 можно однозначно сказать, что загаданы 3 и 5.
По произведению 125 можно однозначно сказать, что загаданы 5 и 25.
По произведению 2130 = 2 * 3 * 5 * 71 можно однозначно сказать, что загаданы 71 и 30.
Подсказка 2: Я это знал
Это значит, что как ни разбей загаданную сумму на два слагаемых, их произведение будет неоднозначным.
Займемся прореживанием множества потенциально подходящих сумм:
- Для четных чисел, меньших 200, можно не проверять гипотезу Гольдбаха, т. е. их можно представить в виде суммы двух простых.
- Все числе больше 54 можно представить как 53 + x, x > 1. Произведение 53 и x будет однозначным, т. к. 53 — простое больше 50.
- Если p — простое число, то p + 2 — неподходящая сумма, т. к. представляется в виде суммы двух простых.
Таким образом остаются нечетные числа S < 54 такие, что (S-2) — составное:
11, 17, 23, 27, 29, 35, 37, 41, 47, 51
Подсказка 3: Тогда я знаю эти числа
Это значит, что для данного произведения есть единственное разложение на множители, сумма которых находится в нашем списке. Назовем такие произведения хорошими.
Заметим, что все суммы в списке нечетные, а значит одно из чисел должно быть четным, а второе — нечетным.
Частный случай хорошего произведения — произведение степени двойки и простого числа, сумма которых лежит в нашем списке. Действительно, как ни разбей на множители по-другому, они оба окажутся четными и их сумма не сможет оказаться подходящей.
Пример: 8 * 19 = 4 * 38 = 2 * 76, только сумма первых двух множителей подходящая.
Подсказка 4: Тогда и я знаю!
Это значит, что сумму можно единственным образом разбить на два слагаемых, дающих хорошее произведение.
Проверять отсутствие или единственность такого разложения будет сложно, так что заметим, что если для какой-то суммы нашлось хотя бы два разложения, она нас не устраивает.
Снова прореживаем множество сумм, используя частный случай из предыдущей подсказки:
11 = 4 + 7 = 8 + 3
17 = 4 + 13 =?
23 = 4 + 19 = 8 + 13
27 = 4 + 23 = 8 + 29
29 = 8 + 19 =?
35 = 4 + 31 = 16 + 19
37 = 8 + 29 = 32 + 5
41 = 4 + 37 =?
47 = 4 + 43 = 16 + 31
51 = 4 + 47 = 32 + 19
Суммы, для которых пока нашлось единственное хорошее произведение: 17, 29, 41.
29 = 25 + 4
25 * 4 = 100 = 20 * 5, но 25 — неподходящая сумма, а значит 100 — хорошее произведение.
41 = 16 + 25
16 * 25 = 400 = 80 * 5, но 85 — неподходящая сумма, а значит 400 — хорошее произведение.
Остается число 17:
17 = 2 + 15, 2 * 15 = 5 * 6 (сумма 11) — плохое произведение
17 = 3 + 14, 3 * 14 = 21 * 2 (сумма 23) — плохое
17 = 4 + 13 — хорошее
17 = 5 + 12, 5 * 12 = 20 * 3 (сумма 23) — плохое
17 = 6 + 11, 6 * 11 = 33 * 2 (сумма 35) — плохое
17 = 7 + 10, 7 * 10 = 35 * 2(сумма 37) — плохое
17 = 8 + 9, 8 * 9 = 24 * 3 (сумма 27) — плохое
Значит, число 17 можно единственным образом представить в виде суммы двух чисел, произведение которых можно единственным образом разложить на два множителя меньше 100, сумму которых нельзя представить в виде суммы двух чисел, которые однозначно определяются своим произведением. А загаданные числа — 4 и 13.
Автор: Galvanometer
