Задача о двух мудрецах

С олимпиадными задачами на движение, в которых почти ничего не дано, мы уже имели дело. В следующей задаче на теорию чисел данные тоже придётся добывать по крупицам - но тем больше удовольствия принесёт результат!

Условие

У одного султана было два мудрых визиря. Захотел он проверить, насколько они сообразительны. Позвал он их обоих и сказал:
- Я загадал два числа от 2 до 100. Вы должны их мне назвать.
При этом султан сообщил первому визирю произведение этих чисел, а второму - их сумму.
Первый визирь подумал и говорит:
- Я не знаю что это за числа
На что второй ответил:
- Я был в этом уверен.
Тогда первый говорит:
- В таком случае, я знаю, что это за числа.
Второй:
- Тогда и я знаю, что это за числа.

Какие числа загадал султан? Определи их, читатель, и ты окажешься мудрее обоих мудрецов, ибо они узнали числа, зная их сумму или произведение, а ты же не знаешь об этих числах ничего!

Это ещё одна из задач математического фольклора, способных спровоцировать форумную войну, будучи загаданной в интернете. Поэтому постараемся разобрать её решение довольно подробно.

Решение

Обозначим сумму чисел как S, а их произведение - как P. Сами числа пусть будут x и y x+y=S, xy=P.
Разберём реплики визирей.
- Я не знаю что это за числа, – сказал первый визирь (ему было сообщено P).
Отсюда мы извлекаем информацию о том, что x и y – это не пара простых чисел. Кроме того, их произведение не может быть однозначно разложено на два множителя, не превосходящие ста.

- Я был в этом уверен, – сказал второй визирь (ему было сообщена S).
Зададимся вопросом: в каком случае второй визирь не мог быть на все сто уверенным в том, что первый не угадает числа с первого раза? Во-первых, когда S представляется в виде суммы двух простых чисел. Во-вторых, когда существует такое разложение S в сумму S=a+(S-a), что произведение a(S-a) однозначно раскладывается на множители, меньшие ста.
Таким образом, существует всего десять вариантов значения S, при которых вторым визирем могла быть сказана его реплика. Это числа 11, 17, 23, 27, 29, 35, 37, 41, 47, 53. Вот эту информацию и получил первый визирь после реплики второго.

- Я знаю что это за числа, – сказал первый визирь.
Итак, первый визирь знает, что xy=P и что x+y=11 или 17 или 23 или 27 или 29 или 35 или 37 или 41 или 47 или 53. Поскольку он может однозначно восстановить числа x и y, то произведение P таково, что сумма его сомножителей для одного варианта разложения равняется одному из десяти допустимых значений (ДДЗ), а для прочих – не равняется. Эту информацию получает перед своей репликой второй визирь.

- Я знаю что это за числа, – сказал второй визирь.
Второй визирь знает сумму чисел и узнал, что для произведения чисел существует единственный вариант разложения на множители, сумма которых равна одному из ДДЗ.
Поскольку он определил числа, то существует единственное разложение суммы S = a+(S-a) такое, что для произведения P=a(S-a) существует единственное разложение на множители P=b*(P/b), такое, что сумма b+P/b равна одному из ДДЗ.

А такое возможно лишь для суммы S=17 и произведения P=52.
Покажем теперь ещё раз как рассуждали мудрецы:
Первый мудрец рассуждает так:
52=2*26=4*13, так что однозначный ответ я получить не могу.
- Я не знаю, что это за числа.

Второй мудрец рассуждает так:
17=2+15, 2*15=30, но и 5*6=30
17=3+14, 3*14=42, но и 6*7=42
17=4+13, 4*13=52, но и 2*26=52
17=5+12, 5*12=60, но и 6*10=60
17=6+11, 6*11=66, но и 3*22=66
17=7+10, 7*10=70, но и 2*35=70
17=8+9, 8*9=72, но и 2*36=72
Значит, первый мудрец в любом случае не сможет однозначно назвать задуманные султаном числа.

О чём и сообщает:
- Я был в этом уверен.

Теперь первый мудрец думает так:
Поскольку второй мудрец был уверен в том, что я с первого раза не назову загаданные числа, то сумма их равна одному из чисел: 11, 17, 23, 27, 29, 35, 37, 41, 47 или 53. При произведении, равном 52 мы имеем:
52=2*26; 2+26=28
52=4*13; 4+13=17 – вот это число входит в ДДЗ
Значит, я могу однозначно определить пару загаданных чисел: это 4 и 13.
И говорит:
- Я знаю, что это за числа.

Теперь второй мудрец думает так:
Первый мудрец после моей фразы понял, что сумма чисел равна 11, 17, 23, 27, 29, 35, 37, 41, 47 или 53 и, зная своё произведение, получил однозначный ответ.

Пробуем перемножать числа, дающие в сумме 17:
2*15=30=5*6; 5+6=11 – в этом случае первый мудрец не смог бы однозначно найти числа
3*14=42=2*21; 2+21=23 – и в этом случае тоже
4*13=52=2*26; 2+26=28 – и тут второй вариант произведения не принадлежит указанным выше 10-ти числам, что и позволило первому визирю однозначно узнать загаданные числа. Продолжая перебор, окажется, что этот вариант – единственный, когда сумма множителей альтернативного произведения не равно одному из ДДЗ
5*12=60=3*20; 3+20=23
6*11=66=2*33; 2+33=35
7*10=70=2*35; 2+35=37
8*9=72=3*24; 3+24=27

Так что и второй мудрец может однозначно сказать, что знает загаданные числа.

Чтобы окончательно разобраться с задачей, разберём другой вариант загаданных чисел и поясним, почему данный диалог не мог состояться. Допустим, султан загадал числа 23 и 6.

Итак, первый визирь знает P=138, второй визирь знает S=29
- Я не могу однозначно определить числа, т.к. 138=23*6=46*3=69*2, - подумал первый визирь
- Хе, конечно, не можешь, - подумал второй, - т.к. любое произведение х*(29-х) не представляется однозначно произведением двух сомножителей.

Произошёл первый обмен репликами. Из него первый визирь узнал, что сумма чисел равна одному из (ДДЗ). Пробует:
69+2=71 – не подходит
46+3=49 – не подходит
23+6=29 – подходит!

Значит, он теперь числа может установить однозначно, о чём и сообщает.

Хорошо, а что же делает второй визирь? Он думает:
-Ага, значит, первому визирю было сообщено некоторое произведение P, причём при одном разложении его на множители сумма y1+P/y1 равна одному из ДДЗ (а именно, равна 29), а при остальных разложениях сумма y2+P/y2 не входит в ДДЗ
А дальше – тупик. Поскольку, первый визирь скажет, что отгадал числа и в случае, если были загаданы, к примеру, 2 и 27:
29=2+27; 2*27=54

54=2*27=3*18=6*9
2+27 входит в ДДЗ
3+18=21 не входит в ДДЗ
6+9=15 не входит в ДДЗ

И второй всё ещё не знает, что это была за пара: 23 и 6 или 2 и 27, и его последняя реплика в этом случае будет невозможна.

Ключевой момент в решении – существование такого S, входящего в ДДЗ, что для единственного P=a(S-a) существует единственное b+P/b, что входит в ДДЗ

Так что все 4 реплики могли быть произнесены только если были загаданы числа 4 и 13.