Невирішувана головоломка, інша назва Головоломка суми та множення — це головоломка, яка називається «невирішуваною», бо їх наче не достатньо інформації для вирішення. Вона вперше була надрукована в 1969 році Гансом Фройденталем,Ганс Фройденталь, Nieuw Archief Voor Wiskunde, Series 3, Volume 17, 1969, page 152, а назву Невирішувана головоломка отримала від Мартіна Гарднера.. Головоломка насправді вирішувана, хоча і не легко. Існує багато схожих версій головоломок.
Головоломка X та Y є два різні цілі числа, більші за 1, сума яких менше 100. S та P — два математики; S знає суму X+Y, P знає результат множення X*Y, і обидва знають інформацію у цих двох твердженнях. Відбувається така розмова:
P каже «Я не можу вгадати ці два числа.» S каже «Я був впевнений, що ти їх не вгадаєш. Я їх теж не можу вгадати.» P каже «Тоді, я їх знаю.» S каже «Якщо ти можеш їх вгадати, то і я їх знаю.»
Що це за два числа?
Рішення У рішенні X та Y дорівнюють 4 та 13 (або навпаки), коли P знає, що результат множення 52, а S знає, що сума — 17.
Спочатку P не знає рішення, бо 52 = 4 × 13 = 2 × 26 а S знає, що P не знає рішення, оскільки всі можливі пари чисел, сума яких дорівнює 17, також дають неоднозначні результати множення. Однак кожен може отримати рішення шляхом відкидання інших варіантів, беручи до уваги твердження опонента, і це достатньо, щоб читач знайшов рішення в наданих обмеженнях.
Детальне рішення Математик P
P знає, що результат множення p=52. P має варіанти (2,26) та (4,13). Тому P знає, що сума s=28 або s=17.
Якщо s=28:
S матиме варіанти (2,26), (3,25), (4,24), (5,23), (6,22), (7,21), (8,20), (9,19), (10,18), (11,17), (12,16) та (13,15). S знатиме, що якщо (5,23) або (11,17), P знатиме ці числа. S не зможе сказати «Я був впевнений, що ти їх не вгадаєш.»
Якщо s=17:
S матиме варіанти (2,15), (3,14), (4,13), (5,12), (6,11), (7,10) та (8,9). S знатиме, що P не знатиме ці числа. S зможе сказати «Я був впевнений, що ти їх не вгадаєш».
Тому, коли S каже «Я був впевнений, що ти їх не вгадаєш», P відкидає (2,26) та розуміє, що відповідь — (4,13).
Математик S
S знає, що сума s=17. S має варіанти (2,15), (3,14), (4,13), (5,12), (6,11), (7,10) та (8,9). Тому S знає, що результат множення p може бути 30, 42, 52, 60, 66, 70 або 72.
Коли P каже «Тоді, я їх знаю», S розуміє, що його попереднє твердження відкинуло для P всі варіанти крім одного.
S повторює хід думки P
Лише варіант 3 виключає всі, крім однієї можливості для P. Так S вирішує, що (4,13) є відповіддю.
Вищенаведене рішення є підтвердженням, а не вирішенням. Воно підтверджує, що якщо P повідомили число 52, а S повідомили число 17, тоді і P визначить пару чисел, і S визначить цю пару чисел. Однак воно не доводить, що (4,13) є єдиною відповіддю. Коли є відповідь на друге питання, (тобто S каже «Я був впевнений, що ти їх не вгадаєш»), чи справді 52 це результат множення, який отримав P?
Відповідь — так. Для отримання відповіді можна використати книгу excel. Якщо x та y — це загадані числа, двома рівняннями будуть x+y=s та x*y=p. Підставляючи замість y, отримаємо x2-s*x+p=0. В книзі excel відбувається пошук цілих чисел для заданих значень s та p.
Код мовою Python
Нижче наведено код мовою програмування Python, який доводить, що вищенаведене рішення є унікальним.
limit = 100 #до їх розмови будь-яке x*y де 1<x<y<x+y<limit дозволено як P PAllowed1 = {} for x in range(2, limit): for y in range(x+1, limit-x): if x*y not in PAllowed1: PAllowed1[x*y] = 1 else: PAllowed1[x*y] += 1 # коли P каже "Я не знаю", дозволені лише P з PAllowed1[P]>1 SNotAllowed1 = {} for x in range(2, limit): for y in range(x+1, limit-x): if PAllowed1[x*y] == 1 : SNotAllowed1[x+y] = 1 # коли S каже "Я не знаю", дозволені лише ті S, що лежать в площині SNotAllowed1 PAllowed2 = {} for n in range(2, limit): if n not in SNotAllowed1: for x in range(2, n//2+1): p = x * (n-x) if p in PAllowed1 and PAllowed1[p] > 1: if p in PAllowed2: PAllowed2[p] += 1 else: PAllowed2[p] = 1 # дозволені лише ті P, що можуть бути поділені на два числа x,y де x+y дозволено лише в одному варіанті, тоюто PAllowed2[P]==1 SAllowed2 = {} for n in range(2, limit): if n not in SNotAllowed1: for x in range(2, n//2+1): if x*(n-x) in PAllowed2 and PAllowed2[x*(n-x)] == 1: if n in SAllowed2: SAllowed2[n] += 1 else: SAllowed2[n] = 1 # оскільки S тепер знає відповідь, то поділ може бути здійснений лише в одному варіанті - S, де SAllowed2[S]==1 for n in SAllowed2: if SAllowed2[n] == 1: for x in range(2, n//2+1): if x*(n-x) in PAllowed2 and PAllowed2[x*(n-x)] == 1: print '(S,P) = ( %d , %d ), (x,y)= ( %d , %d )' % (n, x*(n-x), x, n-x)
Код мовою Scala Нижче наведено код мовою програмування Scala, який доводить, що вищенаведене рішення є унікальним.
object ImpossiblePuzzle extends App { type XY = (Int, Int) val step0 = for { x <- 1 to 100 y <- 1 to 100 if 1 < x && x < y && x + y < 100 } yield (x, y)
def sum(xy: XY) = xy._1 + xy._2 def prod(xy: XY) = xy._1 * xy._2 def sumEq(xy: XY) = step0 filter { sum(_) == sum(xy) } def prodEq(xy: XY) = step0 filter { prod(_) == prod(xy) }
val step2 = step0 filter { sumEq(_) forall { prodEq(_).size != 1 }} val step3 = step2 filter { prodEq(_).intersect(step2).size == 1 } val step4 = step3 filter { sumEq(_).intersect(step3).size == 1 } println(step4) }
Див. також Список невирішуваних головоломок Задача про три стакани
Примітки
Посилання Puzzles by John Burkardt The Impossible Problem by Torsten Sillke Two Mathematicians Problem on mathforum Model Checking Sum and Product Survey: The Freudenthal problem and its ramifications