Решаем задачу про мудрецов без ЭВМ

Несколько дней назад в комментариях к задаче про возраст Шерил была предложена похожая, но более интересная и сложная задачка, сформулированная таким образом:
У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».
Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.
Назовите эти числа.

Были предложены несколько вариантов решения задачи, в том числе на 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 = 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.
  • +25
  • 16,9k
  • 9
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 9

    0
    Любопытно, что в журнале «Квант» за 1977 год (http://school-collection.edu.ru/catalog/res/0d7a6b7e-d04a-f9c1-bd42-b76f0a76af05/?fullView=1) было дополнительное ограничение, что сумма меньше ста. Оказывается, и без него однозначно решается
      +2
      Вообще это ограничение сильно облегчает жизнь, потому что до фишки с 53 + x я додумался позже всего. А о том, что она работает уже на первой подсказке, а не на третьей, только когда писал статью и упрощал решение.
      Иначе после первого шага оставались все нечетные суммы больше 100, а после третьего — числа 57 и 59, одно из которых неочевидно убиралось.
        0
        Не совсем понял отсев чисел 53 + х. Например 3360 = 60 х 56 = 96 х 35 = 48 х 70. Как-то неоднозначно.
          +1
          3360 = 2*2*2*2*2*3*5*7 — здесь нет простого множителя больше 50.

          Фишка заключается в том, что любое число, в которое в качестве множителя входит простое число больше 50 (а первое из них — это 53) однозначно раскладывается на два множителя меньших 100.

          Например, произведение наших чисел равно 318=2*3*53. В принципе, исходными числами могут быть 6 и 53, 2 и 159 или 3 и 106, но вторая и третья пара не подходят, так как в них одно из чисел больше 100.

          Любую сумму больше 54 можно разложить на 53 и х. И этот вариант всегда дает «плохое» произведение. Поэтому суммы больше 54 можно не рассматривать.
          0
          Следующий шаг — максимально обобщить задачу, т.е. найти такое N>100, при котором все еще единственное решение
        +2
        С ЭВМ, без ЭВМ… эх…
        Несчастный султан хотел узнать — будут ли его мудрецы настолько мудры, чтобы договориться между собой, решить квадратное уравнение и сказать ответ. Потому султан и был поражен.
          0
          Всё-таки, вернусь снова к этой задаче. Объясните мне, пожалуйста, в чём я неправ.

          Пусть султан загадал числа 4 и 7. Али услышал 28, Вали — 11.

          Али не знает ответа, т. к. 28 раскладывается не однозначно (на 4×7 или 2×14). Он об этом говорит.

          Вали знал об этом, т. к. среди разложений 11 на слагаемые нет разложения на простые числа (также оно не является суммой простого числа и его квадрата). Он об этом говорит.

          Али: раз Вали сказал, что знает, что числа не простые, значит их сумма как минимум нечётная. Значит, одно из чисел чётное, а другое нет, что оставляет только один вариант разложения — 4×7. Али теперь знает ответ и говорит об этом.

          Вали: раз Али знает ответ, значит, его разложение стало единственным после уточнения, что одно из чисел чётное. Какого рода числа имеют однозначное разложение на чётный и нечётный множители? Любое число раскладывается на прозведение простых, в нашем случае одно из этих простых гарантированно двойка. Число множителей должно быть больше двух (иначе бы у нас было просто два простых числа и Али бы знал ответ сразу). Подходят только числа с множителями вида (2^n, p), где p — простое число больше двух (нечётное), а n > 1. 11 — это 2^2 + 7, значит, искомые числа — 4 и 7. Вали тоже знает ответ.

          Если эта логика верна, то решением задачи являются любые пары вида (2^n, p) такие, что 2^n + p ≠ q + 2 где q — простое число > 2. Это условие нужно потому, что иначе в возможных слагаемых Вали появится простая пара (q, 2), и Вали не сможет с уверенностью сказать, что Али не знает ответа.

            0
            Сумма 11 действительно занятная, т. к. остается после третьей подсказки.

            В Ваших рассуждениях ошибка в том, что 11 можно представить в виде 2^n + p двумя способами: 4 + 7 и 8 + 3.
            А значит Вали не сможет выбрать один из двух этих ответов.
              0
              Спасибо! Да, Вы правы, этот момент я упустил.

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

            Самое читаемое