Завдання про двох мудреців. Комп'ютерна програма для вирішення

Завдання про двох мудреців вже багато років спливає на різних форумах і постійно відновлює до себе інтерес. Нагадаю умову:

У деякого султана було два мудреці: Алі-ібн-Валі і Валі-ібн-Алі. Бажаючи переконатися в їхній мудрості, султан закликав мудреців до себе і сказав: "Я задумав два числа. Обидва вони цілі, кожне більше одиниці, але менше ста. Я перемножив ці числа і результат повідомлю Алі і при цьому Валі я скажу суму цих чисел. Якщо ви справді такі мудрі, як про вас кажуть, то зможете дізнатися вихідні числа ".

Султан сказав Алі твір, а Валі - суму. Мудреці задумалися. Першим порушив мовчання Алі.

- Я не знаю цих чисел, - сказав він, опускаючи голову.

- Я це знав, - подав голос Валі.

- Тоді я знаю ці числа, - зрадів Алі.

- Тоді я знаю! - вигукнув Валі.

І мудреці повідомили враженому султану задумані ним числа.

Назвіть ці числа.

Готової комп'ютерної програми, що дозволяє вирішувати такі завдання при будь-якому заданому максимальному числі, виявити не вдалося. Тому я вирішив сам написати подібну програму. Алгоритм рішення буду описувати на прикладі класичного завдання для максимального числа, рівного 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 (більше половини Max, в нашому випадку це просте число 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 30

2: X + Y = 17, X * Y =: 30 42 52 60 66 70 72

3: X + Y = 23, X * Y =: 42 60 76 90 102 112 120 126 130 132

4: X + Y = 27, X * Y =: 50 72 92 110 126 140 152 162 170 176 180 182

5: X + Y = 29, X * Y =: 54 78 100 120 138 154 168 180 190 198 204 208 210

6: X + Y = 35, X * Y =: 66 96 124 150 174 196 216 234 250 264 276 286 294 300 304 306

7: X + Y = 37, X * Y =: 70 102 132 160 186 210 232 252 270 286 300 312 322 330 336 340 342

8: X + Y = 41, X * Y =: 78 114 148 180 210 238 264 288 310 330 348 364 378 390 400 408 414 418 420

9: 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 552

10: 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 650

11: 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 28

2: X + Y = 17, X * Y =: 52

3: X + Y = 23, X * Y =: 76 112 130

4: X + Y = 27, X * Y =: 50 92 110 140 152 162 170 176 182

5: X + Y = 29, X * Y =: 54 100 138 154 168 190 198 204 208

6: X + Y = 35, X * Y =: 96 124 174 216 234 250 276 294 304 306

7: X + Y = 37, X * Y =: 160 186 232 252 270 336 340

8: X + Y = 41, X * Y =: 114 148 238 288 310 348 364 378 390 400 408 414 418

9: X + Y = 47, X * Y =: 172 246 280 370 442 480 496 510 522 532 540 550 552

10: 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 = 63

1: X = 4, Y = 13

Результат для Max = 867

1: X = 4, Y = 13

2: X = 4, Y = 61

Результат для Max = 1503

1: X = 4, Y = 13

2: X = 4, Y = 61

3: X = 32, Y = 131

Результат для Max = 1967

1: X = 4, Y = 13

2: X = 4, Y = 61

3: X = 16, Y = 73

4: X = 32, Y = 131

Кінець обчислень. Час обчислення: 0:00:29

Видно, що рішення 4, 13 є унікальним у діапазоні від 63 до 866.

До речі, завдання, опубліковане в журналі «Наука і Життя», не має рішення взагалі, оскільки там була умова, що числа менше 60. Уявляю, скільки часу угробили читачі намагаючись вирішити завдання, а вона не має коректного рішення...

Готовий викласти лістинги програми і саму програму (написана на Delphi), якщо це можливо.