[Из песочницы] Задача о двух мудрецах. Компьютерная программа для решения
Задача о двух мудрецах уже много лет всплывает на различных форумах и постоянно возобновляет к себе интерес. Напомню условие: У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».Султан сказал Али произведение, а Вали — сумму. Мудрецы задумались. Первым нарушил молчание Али.— Я не знаю этих чисел, — сказал он, опуская голову.— Я это знал, — подал голос Вали.— Тогда я знаю эти числа, — обрадовался Али.— Тогда и я знаю! — воскликнул Вали.И мудрецы сообщили пораженному султану задуманные им числа.Назовите эти числа.
Готовой компьютерной программы, позволяющей решать такие задачи при любом заданном максимальном числе, обнаружить не удалось. Поэтому я решил сам написать подобную программу. Алгоритм решения буду описывать на примере классической задачи для максимального числа, равного 100.1. Я не знаю этих чисел, сказал мудрец, знающий произведение двух чисел Отсюда вытекает, что это произведение, не может быть однозначно представлено в виде произведения двух чисел. Есть как минимум несколько способов, как можно получить это произведение с другими парами чисел, причем эти числа должны удовлетворять условию, что они оба меньше 100. Произведение, которое можно представить только одним способом, будем в дальнейшем называть уникальным.С этого высказывания можно сделать вывод о некоторых свойствах этих чисел. Во-первых, они не могут оба быть одновременно простыми, иначе их произведение уникально и представляется только в виде произведения этих двух простых чисел. Это условие является необходимым, но не достаточным условием уникальности произведения. В дальнейшем мы обнаружим другие уникальные произведения, которые не являются произведением двух простых чисел.
2. Я это знал, сказал мудрец, знающий сумму двух чисел Сумму двух чисел S, можно представить парой чисел различными способами: 2 + (S — 2), 3 + (S — 3) и т.д. Это высказывание говорит нам, что ни одна из этих пар чисел, при умножении друг на друга не дает уникальное произведение. Попробуем определить какие суммы двух чисел имеют такие свойства, т.е. составим список возможных кандидатов для сумм двух чисел.
Во-первых, как мы уже показали, два числа не могут быть оба простыми, поэтому их сумма не может быть суммой двух простых чисел. Итак, компьютерная программа, сначала вычисляет список всех простых чисел, которые меньше заданного максимального числа. Далее, находит все возможные суммы, которые могут быть получены этими простыми числами и исключает их из дальнейшего исследования. В результате мы получим первое приближение — возможных сумм:
11 17 23 27 29 35 37 41 47 51 53 57 59 65 67 71 77 79 83 87 89 93 95 97 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 174 175 177 179 181 182 183 184 185 187 188 189 190 191 192 193 195 196
В принципе, мы могли бы сразу все эти возможные суммы проверять на уникальность. Т.е. для каждой суммы составляем все возможные пары чисел и произведение этих чисел проверяем на уникальность. Если хоть одна пара чисел, для исследуемой суммы, дает уникальное произведение, то эта сумма вычеркивается из возможных кандидатов. Эта подпрограмма для проверки на уникальность произведения — самая сложная часть всей программы. Многие, кто пытался составить подобную программу, просто забывали об этом и получали не до конца корректные результаты.
В этой подпрограмме в начале исследуемое произведение разбивается на простые множители, далее составляется список всех возможных произведений, которые могут быть получены их этих простых множителей — это первый множитель. Второй множитель получаем делением произведения на первый множитель и проверяем только варианты, когда первый множитель меньше второго. Далее оба множителя проверяем, удовлетворяют ли они условию задачи (оба меньше максимального числа 100, или их сумма меньше Max). Так мы получаем допустимые разложения произведения на два множителя и если таких разложений только одно, то это произведение уникально.
Но перед тем, как начать проверку на уникальность, мы упростим задачу, чтобы не грузить компьютер лишними вычислениями. Воспользуемся не очень очевидным свойством — какая сумма может быть максимальной.Если исследуемое произведение имеет множителем простое число больше 50 (больше половины Мax, в нашем случае это простое число 53), то это произведение уникально. Так как при попытке получить второй вариант разложения, мы как минимум должны умножать 53 на 2 и получаем множитель больший 100.
Для любой суммы S, больше чем 53 + 2, мы можем найти пару чисел 53 и S — 53 и произведение этих чисел будет уникальным. Отсюда делаем вывод, что все суммы больше чем 55 можно исключить из дальнейших вычислений.Это сужает круг поиска до 11 возможных сумм:
11 17 23 27 29 35 37 41 47 51 53
Теперь делаем проверку на уникальность произведения всех возможных пар чисел. Программа выводит уникальные произведения с отрицательным знаком.
1: X + Y = 11, X * Y =: 18 24 28 302: X + Y = 17, X * Y =: 30 42 52 60 66 70 723: X + Y = 23, X * Y =: 42 60 76 90 102 112 120 126 130 1324: X + Y = 27, X * Y =: 50 72 92 110 126 140 152 162 170 176 180 1825: X + Y = 29, X * Y =: 54 78 100 120 138 154 168 180 190 198 204 208 2106: X + Y = 35, X * Y =: 66 96 124 150 174 196 216 234 250 264 276 286 294 300 304 3067: X + Y = 37, X * Y =: 70 102 132 160 186 210 232 252 270 286 300 312 322 330 336 340 3428: X + Y = 41, X * Y =: 78 114 148 180 210 238 264 288 310 330 348 364 378 390 400 408 414 418 4209: X + Y = 47, X * Y =: 90 132 172 210 246 280 312 342 370 396 420 442 462 480 496 510 522 532 540 546 550 55210: X + Y = 51, X * Y =: 98 144 188 230 270 308 344 378 410 440 468 494 518 540 560 -578 594 608 620 630 638 644 648 65011: X + Y = 53, X * Y =: 102 150 196 240 282 322 360 396 430 462 492 520 546 570 592 612 630 646 660 672 682 690 696 700 702
Обнаруживается одно уникальное произведение — 578 = 2×17*17. Действительно это число можно представить только одним способом — 17×34, второй способ 2×289, не удовлетворяет условию — оба числа меньше 100.
Значит сумма 51 так же удаляется их возможных кандидатов, оставляя только 10 допустимых сумм.
Кстати, благодаря программе, можно легко найти следующее простое правило, как обнаружить уникальные произведения.
Если произведение имеет вид 2 * P * P, где P — простое число, квадрат которого больше максимального числа (100), то это произведение уникально и оно соответствует сумме двух чисел P и 2*P и эта сумма равна 3*P.
Значит мы можем вычеркивать все суммы, которые равны 3*P, где P простое число больше 10. В нашем случае это сумма 51 = 3×17.
При дальнейшей работе с программой обнаружились еще и другие интересные правила для уникальных произведений…
Итак, после первых двух реплик мудрецов, первый мудрец знает, что сумма двух чисел может быть только одной из 10 чисел:
11 17 23 27 29 35 37 41 47 53
3. Тогда я знаю эти числа, — обрадовался Али В каком случае Али может однозначно определить, на какую пару чисел разложить свое произведение? На ту пару чисел, сумма которой, равна одной из этих 10 сумм, причем только одна пара чисел имеет сумму из этого множества. С точки зрения компьютерного алгоритма, те произведения, которые встречаются больше одного раза, должны быть удалены. Например, произведение 30 встречается два раза — для суммы 11 и для суммы 17. Если бы Али сказали число 30, то он бы обнаружил, что условиям задачи удовлетворяют две пары чисел: 5, 6 (сумма 11) и 2, 15 (сумма 17) и он не мог бы однозначно сказать — я знаю эти числа. Значит все повторяющиеся произведения удаляются. В результате мы получаем такую картину — все допустимые суммы и все допустимые произведения для этих сумм:1: X + Y = 11, X * Y =: 18 24 282: X + Y = 17, X * Y =: 523: X + Y = 23, X * Y =: 76 112 1304: X + Y = 27, X * Y =: 50 92 110 140 152 162 170 176 1825: X + Y = 29, X * Y =: 54 100 138 154 168 190 198 204 2086: X + Y = 35, X * Y =: 96 124 174 216 234 250 276 294 304 3067: X + Y = 37, X * Y =: 160 186 232 252 270 336 3408: X + Y = 41, X * Y =: 114 148 238 288 310 348 364 378 390 400 408 414 4189: X + Y = 47, X * Y =: 172 246 280 370 442 480 496 510 522 532 540 550 55210: X + Y = 53, X * Y =: 240 282 360 430 492 520 570 592 612 630 646 660 672 682 690 696 700 702
4. Тогда и я знаю! — воскликнул Вали После третьей реплики, Вали проделал всю вычислительную работу как и мы и отбросил все повторяющиеся произведения. И он может определить однозначно числа только тогда, когда для его суммы, остается допустимым только одно произведение. С точки зрения компьютера — в одной строчке осталось только одно допустимое произведение. В нашем случае — это произведение 52 для суммы 17, которое соответствует паре чисел 4, 13. Это решение является единственным.Моя компьютерная программа позволяет получить результат задачи для любого значения максимального числа.Существуют различные вариации этой задачи: — оба числа меньше заданного; — сумма чисел меньше заданного максимального числа; — числа могут быть одинаковые; — числа обязательно разные; Программа позволяет рассчитать результат для всех этих вариаций.Программа может выводить промежуточные результаты для каждого этапа вычислений.Также есть возможность вычислить все граничные точки, при которых появляются новые решения для указанного диапазона чисел. Например, при сканировании всех чисел до 2000 мы получим следующий результат:
Результат для Max = 10Нет результата
Результат для Max = 631: X = 4, Y = 13
Результат для Max = 8671: X = 4, Y = 132: X = 4, Y = 61
Результат для Max = 15031: X = 4, Y = 132: X = 4, Y = 613: X = 32, Y = 131
Результат для Max = 19671: X = 4, Y = 132: X = 4, Y = 613: X = 16, Y = 734: X = 32, Y = 131
Конец вычислений. Время вычислений: 0:00:29
Видно, что решение 4, 13 есть уникальным в диапазоне от 63 до 866.
Кстати, задача, опубликованная в журнале «Наука и Жизнь», не имеет решения вообще, так как там было условие, что числа меньше 60. Представляю, сколько времени угробили читатели пытаясь решить задачу, а она не имеет корректного решения…
Готов выложить листинги программы и саму программу (написана на Delphi), если это возможно.
