- PVSM.RU - https://www.pvsm.ru -
Несколько дней назад в комментариях к задаче про возраст Шерил [1] была предложена похожая, но более интересная и сложная задачка, сформулированная таким образом:
У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».
Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.
Назовите эти числа.
Были предложены несколько вариантов решения задачи, в том числе на Scala [2] и C# [3], предполагающие достаточно грубый перебор множества возможных ответов. Тем не менее, задачу можно решить, если под рукой не оказалось ноутбука, только карандаш и листок бумаги.
Для начала давайте разберемся, почему решение без компьютера — не совсем пустая трата времени.
Это значит, что произведение неоднозначно раскладывается на произведение двух множителей, меньших 100.
Рассмотрим те произведения, которые так раскладываются единственным образом, назовем их однозначными.
Выделим несколько важных классов однозначных произведений:
Примеры:
По произведению 15 можно однозначно сказать, что загаданы 3 и 5.
По произведению 125 можно однозначно сказать, что загаданы 5 и 25.
По произведению 2130 = 2 * 3 * 5 * 71 можно однозначно сказать, что загаданы 71 и 30.
Это значит, что как ни разбей загаданную сумму на два слагаемых, их произведение будет неоднозначным.
Займемся прореживанием множества потенциально подходящих сумм:
Таким образом остаются нечетные числа S < 54 такие, что (S-2) — составное:
11, 17, 23, 27, 29, 35, 37, 41, 47, 51
Это значит, что для данного произведения есть единственное разложение на множители, сумма которых находится в нашем списке. Назовем такие произведения хорошими.
Заметим, что все суммы в списке нечетные, а значит одно из чисел должно быть четным, а второе — нечетным.
Частный случай хорошего произведения — произведение степени двойки и простого числа, сумма которых лежит в нашем списке. Действительно, как ни разбей на множители по-другому, они оба окажутся четными и их сумма не сможет оказаться подходящей.
Пример: 8 * 19 = 4 * 38 = 2 * 76, только сумма первых двух множителей подходящая.
Это значит, что сумму можно единственным образом разбить на два слагаемых, дающих хорошее произведение.
Проверять отсутствие или единственность такого разложения будет сложно, так что заметим, что если для какой-то суммы нашлось хотя бы два разложения, она нас не устраивает.
Снова прореживаем множество сумм, используя частный случай из предыдущей подсказки:
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
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/logika/89516
Ссылки в тексте:
[1] возраст Шерил: http://geektimes.ru/post/249014/
[2] Scala: http://geektimes.ru/post/249098/
[3] C#: http://pastie.org/10093271
[4] программа: http://geektimes.ru/post/249098
[5] гипотезу Гольдбаха: https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%93%D0%BE%D0%BB%D1%8C%D0%B4%D0%B1%D0%B0%D1%85%D0%B0
[6] Источник: http://geektimes.ru/post/249372/
Нажмите здесь для печати.