А теперь сложнее, чем вчера

Вчера я пытался разобраться в логическом решении задачки, которую как то решал весь интернет. Разобрался. Спасибо всем комментаторам.

Однако есть подобная задачка и сложнее и интереснее. Это уж тем более мне не "по зубам", но знаю, что среди читателей есть любители такого:

У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».

Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.

Назовите эти числа.

В интернете встречаются программные алгоритмы решения этой задачки, но можно и чисто логикой. Разберем процесс рассуждения...

Подсказка 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 = 16 + 7
27 = 4 + 23 = 8 + 19
29 = 16 + 13 =?
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.

Вот тут источник этого объяснения

Взято: masterok.livejournal.com

уникальные шаблоны и модули для dle