Entertaining tasks
April 2015 17

Задача о мудрецах. Решение

From Sandbox
image

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

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

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

Каноничного решения этой задачи я так и не нашел, поэтому держите мой вариант (с претензией на каноничность).

Один из найденных мной ответов: числа 2 и 9 (да-да, ответов несколько). Попробую доказать верность решения.

Итак, 2 и 9. У Али произведение — 18. У Вали сумма — 11.

Вали знал, что Али не сможет отгадать числа. Значит, перемножив попарно все возможные слагаемые своей суммы, он не получил ни одного произведения, позволившего бы отгадать эти числа.

Основная теорема арифметики утверждает, что разложение числа на простые сомножители единственно, так что произведение двух простых чисел всегда позволяет отгадать эти числа. Следовательно, сумма Вали не должна получаться путем сложения двух простых чисел.

Тогда, Али отбрасывает те множители, сумму которых можно получить этим способом. Сумма множителей числа 18 — 3 и 6 — равна 9. Так же 9 можно получить сложением 2 и 7 — простых чисел. Отбрасываем эти множители. Остается одна пара множителей — 2 и 9. Их сумму — 11 — нельзя представить в виде суммы двух простых чисел. Следовательно, исходные числа — 2 и 9.

UPD: Прошу извинить, по всей видимости не добрался в своих рассуждениях до логического конца. Спасибо Shultc.

Вот, что я упустил: после того, как Али отгадывает числа, отгадать их должен и Вали. Как он это делает? Вали перемножает попарно все возможные слагаемые своей суммы, а затем перебирает их. Искомое произведение то, которое имеет одну единственно возможную сумму своих множителей, не являющуюся суммой двух простых чисел. Множители, с помощью которых Вали получил это произведение, и являются исходными числами.

Таким образом, я опроверг свой собственный ответ. 3 и 8, 4 и 7, 5 и 6 — все их попарные произведения подходят под рассуждение, поэтому выбрать нужное из них Вали не мог.

Подобрать ответ, как я понял, можно только перебором. Теперь решение должно быть верно.

UPD2: Для полноты приведу взятый из этой статьи ответ. Исходные числа — 13 и 4. Ответ единственен.
P.S. Идите в статью, там еще и сорцы есть.
-8
21.3k 45
Comments 81