Невирішувана головоломка

Невирішувана головоломка, інша назва Головоломка суми та множення — це головоломка, яка називається «невирішуваною», бо їх наче не достатньо інформації для вирішення. Вона вперше була надрукована в 1969 році Гансом Фройденталем,[1], а назву Невирішувана головоломка отримала від Мартіна Гарднера.[2] Головоломка насправді вирішувана, хоча і не легко. Існує багато схожих версій головоломок.

Головоломка

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

Варіант 1 (p=30)

P знає, що p=30. P має варіанти (2,15), (3,10) та (5,6). P знає, що s дорівнює 17, 13 або 11.

Якщо s=17:

S матиме варіанти (2,15), (3,14), (4,13), (5,12), (6,11), (7,10) та (8,9).
S знатиме, що P не знатиме ці числа.
S зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=13:

S матиме варіанти (2,11), (3,10), (4,9), (5,8) та (6,7).
S знатиме, якщо (2,11), то P знатиме числа.
S не зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=11:

S матиме варіанти (2,9), (3,8), (4,7) та (5,6).
S знатиме, що P не знатиме ці числа.
S зможе сказати "Я був впевнений, що ти їх не вгадаєш".
Тому, коли S каже "Я був впевнений, що ти їх не вгадаєш", P відкидає (3,10), але не може вирішити між (2,15) та (5,6).
Варіант 2 (p=42)

P знає, що p=42. P має варіанти (2,21), (3,14) та (6,7). Отже P знає, що сума s - 23, 17 або 13.

Якщо s=23:

S матиме варіанти (2,21), (3,20), (4,19), (5,18), (6,17), (7,16), (8,15), (9,14), (10,13) та (11,12).
S знатиме, що P не знатиме ці числа.
S зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=17:

S матиме варіанти (2,15), (3,14), (4,13), (5,12), (6,11), (7,10) та (8,9).
S знатиме, що P не знатиме ці числа.
S зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=13:

S матиме варіанти (2,11), (3,10), (4,9), (5,8) та (6,7).
S знатиме, якщо (2,11), P знатиме числа.
S не зможе сказати "Я був впевнений, що ти їх не вгадаєш".
Тому, коли S каже "Я був впевнений, що ти їх не вгадаєш", P відкидає (6,7), але не може вирішити між (2,21) та (3,14).
Варіант 3 (p=52)
Див. розмірковування математика P вище.
Варіант 4 (p=60)

P знає, що p=60. P має варіанти (2,30), (3,20), (4,15), (5,12) та (6,10). Отже, P знає, що сума s - 32, 23, 19, 17 або 16.

Якщо s=32:

S матиме варіанти (2,30), (3,29), (4,28), (5,27), (6,26), (7,25), (8,24), (9,23), (10,22), (11,21), (12,20), (13,19), (14,18) та (15,17).
S знатиме, якщо (3,29) або (13,19), P знатиме числа.
S не зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=23:

S матиме варіанти (2,21), (3,20), (4,19), (5,18), (6,17), (7,16), (8,15), (9,14), (10,13) та (11,12).
S знатиме, що P не знатиме ці числа.
S зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=19:

S матиме варіанти (2,17), (3,16), (4,15), (5,14), (6,13), (7,12), (8,11) та (9,10).
S знатиме, якщо (2,17), P знатиме числа.
S не зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=17:

S матиме варіанти (2,15), (3,14), (4,13), (5,12), (6,11), (7,10) та (8,9).
S знатиме, що P не знатиме ці числа.
S зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=16:

S матиме варіанти (2,14), (3,13), (4,12), (5,11), (6,10) та (7,9).
S знатиме, якщо (3,13) or (5,11), P знатиме числа.
S не зможе сказати "Я був впевнений, що ти їх не вгадаєш".
Тому, коли S каже "Я був впевнений, що ти їх не вгадаєш", P відкидає (2,30), (4,15) та (6,10), але не може вирішити між (3,20) та (5,12).
Варіант 5 (p=66)

P знає, що p=66. P має варіанти (2,33), (3,22) та (6,11). Отже, P знає, що сума s - 35, 25 або 17.

Якщо s=35:

S матиме варіанти (2,33), (3,32), (4,31), (5,30), (6,29), (7,28), (8,27), (9,26), (10,25), (11,24), (12,23), (13,22), (14,21), (15,20), (16,19) та (17,18).
S знатиме, що P не знатиме ці числа.
S зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=25:

S матиме варіанти (2,23), (3,22), (4,21), (5,20), (6,19), (7,18), (8,17), (9,16), (10,15), (11,14) та (12,13).
S знатиме, якщо (2,23), P знатиме числа.
S не зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=17:

S матиме варіанти (2,15), (3,14), (4,13), (5,12), (6,11), (7,10) та (8,9).
S знатиме, що P не знатиме ці числа.
S зможе сказати "Я був впевнений, що ти їх не вгадаєш".
Тому, коли S каже "Я був впевнений, що ти їх не вгадаєш", P відкидає (3,22), але не може вирішити між (2,33) та (6,11).
Варіант 6 (p=70)

P знає, що p=70. P має варіанти (2,35), (5,14) та (7,10). Отже, P знає, що сума s - 37, 19 або 17.

Якщо s=37:

S матиме варіанти (2,35), (3,34), (4,33), (5,32), (6,31), (7,30), (8,29), (9,28), (10,27), (11,26), (12,25), (13,24), (14,23), (15,22), (16,21), (17,20) та (18,19).
S знатиме, що P не знатиме ці числа.
S зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=19:

S матиме варіанти (2,17), (3,16), (4,15), (5,14), (6,13), (7,12), (8,11) та (9,10).
S знатиме, якщо (2,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 відкидає (5,14), але не може вирішити між (2,35) та (7,10).
Варіант 7 (p=72)

P знає, що p=72. P має варіанти (2,36), (3,24), (4,18), (6,12) та (8,9). P знає, що сума s - 38, 27, 22, 18 або 17.

Якщо s=38:

S матиме варіанти (2,36), (3,35), (4,34), (5,33), (6,32), (7,31), (8,30), (9,29), (10,28), (11,27), (12,26), (13,25), (14,24), (15,23), (16,22), (17,21) та (18,20).
S знатиме, якщо (7,31), P знатиме числа.
S не зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=27:

S матиме варіанти (2,25), (3,24), (4,23), (5,22), (6,21), (7,20), (8,19), (9,18), (10,17), (11,16), (12,15) та (13,14).
S знатиме, що P не знатиме ці числа.
S зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=22:

S матиме варіанти (2,20), (3,19), (4,18), (5,17), (6,16), (7,15), (8,14), (9,13) та (10,12).
S знатиме, якщо (3,19) або (5,17), P знатиме числа.
S не зможе сказати "Я був впевнений, що ти їх не вгадаєш".

Якщо s=18:

S матиме варіанти (2,16), (3,15), (4,14), (5,13), (6,12), (7,11) та (8,10).
S знатиме, якщо (5,13) або (7,11), 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,36), (4,18) та (6,12), але не може вирішити між (3,24) та (8,9).

Лише варіант 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)
}

Див. також

Примітки
  1. Ганс Фройденталь, Nieuw Archief Voor Wiskunde, Series 3, Volume 17, 1969, page 152
  2. Гарднер, Мартін (December 1979). Mathematical Games: A Pride of Problems, Including One That Is Virtually Impossible. Scientific American 241: 22–30..

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.