Onmogelijke Puzzel

De Onmogelijke Puzzel of Som-en-productpuzzel is een puzzel die onmogelijk genoemd wordt omdat er schijnbaar te weinig informatie is voor een oplossing. De puzzel werd voor het eerst gepubliceerd in 1969 door Hans Freudenthal. De naam Impossible Puzzle werd door Martin Gardner voorgesteld. De puzzel is op te lossen, maar niet eenvoudig. Er bestaan vele gelijksoortige versies van dit probleem.

Puzzel

Van twee gehele getallen $x$ en $y$ is gegeven dat:

$1<x<y$ en $x+y\leq 100$

Aan persoon S wordt medegedeeld wat de som $x+y$ is en aan persoon P wat het product $xy$ is. Nu volgt dit gesprek:

• P zegt: "Ik weet niet wat $x$ en $y$ zijn."
• S zegt: "Dat wist ik al."
• P zegt: "Nu weet ik het wel."
• S zegt: "Dan weet ik het nu ook."

Nu kunt u het ook weten.

De oplossing is: $x=4$ en $y=13$.

Uitleg

We kunnen de mogelijkheden voor som en product inperken al naargelang de verloop van het gesprek. En mogelijkheden die wij kunnen uitsluiten, kunnen S en P, die elk meer weten dan wij, zeker ook uitsluiten.

Vooraf

Om te beginnen weten we, nog voordat er iets gezegd is, het volgende.

• Aangezien zowel $x$ als $y$ groter zijn dan 1, kan het product nooit een priemgetal (2, 3, 5, 7, 11, etc) zijn.
• Aangezien $y$ groter is dan $x$, kan het product nooit een kwadraat van een priemgetal (4, 9, 25, 49 etc.) zijn.

P kent het antwoord niet

Nu zegt P dat hij het antwoord niet weet. Dat betekent dat er ten minste twee verschillende geldige manieren zijn om het product te maken (ontbinden). Een product 6 bijvoorbeeld valt af, want dat kan alleen maar voor $x=2$ en $y=3$ gemaakt worden ($x=1$ immers is verboden). Meer algemeen vallen af voor de waarde van het product:

• Elk product van twee verschillende priemgetallen, want zo'n product is op geen enkele andere manier te ontbinden.
• Elk getal met een priemfactor groter dan 50 (dus elk veelvoud van 53 of van 59 of 61 etc.), want P zou dan kunnen weten dat dit priemgetal gelijk aan $y$ is: elk veelvoud ervan is groter dan 100 en dus verboden. Zou bijvoorbeeld het product 1830 zijn, dan zou P de priemfactoren 2,3,5,61 ervan kunnen vinden, en weten dat $x=2\times 3\times 5=30$ en $y=61$ de enige mogelijkheid is.
• Elke derde of vierde macht van een priemgetal; bijvoorbeeld het product $8=2\times 2\times 2$ komt alleen bij $x=2$ en $y=4$ voor, en $81=3\times 3\times 3\times 3$ alleen voor $x=3$ en $y=27$ (want ($x=y=9$ is verboden).

S wist dat al

Nu zegt S dat hij al wist dat P het niet wist. We moeten aannemen dat S niet licht gesproken heeft, dus dat op grond van de waarde van de som alleen alle mogelijkheden die door de uitspraak van P afvielen al uitgesloten waren, een heel sterke informatie. Bijvoorbeeld, als de som 9 zou zijn, dan kon S vooraf alleen weten dat het om een van de paren (2,7), (3,6) of (4,5) ging; van de bijbehorende producten 14, 18, 20 hebben we zojuist 14 uitgesloten (product van twee verschillende priemgetallen), terwijl S dat vooraf nog niet kon uitsluiten. We mogen dus concluderen dat de som niet 9 kan zijn geweest. In het algemeen kunnen we voor elk van de waarden van het product die we uitsloten op grond van de uitspraak van P, de bijbehorende som van de factoren uitsluiten voor de waarde van de som:

• Elke som van twee verschillende priemgetallen.
• De som van een priemgetal en zijn kwadraat, bijvoorbeeld 2+4=6.
• De som van een priemgetal en zijn derde macht, bijvoorbeeld 2+8=10.
• De waarde 55 en elke grotere waarde; immers elk paar $(x,53)$ met $x=2,3,\ldots ,46,47$ viel af op grond van de uitspraak van P.

Er blijven nu over aan mogelijkheden voor de som: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53. Dit rijtje getallen speelt nu een belangrijke rol, dus geven we het een naam:

Noem $L=(11,17,23,27,29,35,37,41,47,51,53)$, het lijstje mogelijkheden voor de som van $x$ en $y$.

P weet het antwoord

P zegt dat hij het antwoord nu weet. Dat betekent dat hoewel er meerdere paren met hetzelfde product waren, er precies een overblijft waarvan de som in het lijstje $L$ voorkomt. We formuleren deze eigenschap preciezer:

Een combinatie $(x,y)$ noemen we behouden als $x+y$ in $L$ voorkomt, en bovendien het product $p=x\cdot y$ geen enkele andere ontbinding $p=r\cdot s$ toelaat waarvoor $r+s$ in $L$ voorkomt.

We zouden nu voor elk van de manieren om een som in het lijstje te maken kunnen nagaan of die combinatie behouden is, en zo niet de combinatie schrappen. Dit is echter veel werk, en het is niet nodig om dit helemaal expliciet te doen om de oplossing te vinden.

Enkele zeker behouden combinaties

We kunnen echter handig gebruikmaken van het feit dat alle getallen in het lijstje oneven zijn. Om een oneven som te hebben moet van $x$ en $y$ er een even en een oneven zijn, en het product zal dus zeker even zijn. Het product heeft dus ten minste een priemfactor 2, en nog minstens twee andere priemfactoren (maar daarbij kan 2 opnieuw gebruikt worden, bijvoorbeeld een product 112=2×2×2×2×7 is mogelijk, bij $(x,y)=(7,16)$). Om nu aan een oneven som te komen moeten alle factoren 2 bij elkaar blijven; immers als zowel $x$ als $y$ een factor 2 bevatten dan is $x+y$ even en komt dus zeker niet in het lijstje voor. Voor sommige waarden van het product is dit argument voldoende om te zien dat er maar één ontbinding overblijft, zodat de betreffende combinatie niet geschrapt zal worden; bijvoorbeeld voor een product 112 moeten alle vier factoren 2 bijeen blijven om een factor 16 te vormen, en de resterende factor 7 kan zich niet bij hen voegen omdat er dan voor het andere getal geen priemfactor meer overblijft ($x=1$ is verboden), dus (7,16) is de unieke combinatie met product 112 en een som die in het lijstje voorkomt. Met eenzelfde argument kan men zien

Een combinatie waarvan het product slechts één priemfactor heeft die niet gelijk is aan 2, is zeker behouden.

S weet ook het antwoord

S zegt dan dat ook hij nu het antwoord weet. Dit betekent dat voor dat getal in het lijstje dat S kent, van alle combinaties er precies een is die behouden is. Voor ons is het voldoende voor elke som in het lijstje na te gaan welk van de drie mogelijkheden het geval is:

1. Alle combinaties met deze som kunnen geschrapt worden op grond van hun product;
2. Er is precies één combinatie die behouden is;
3. Er zijn ten minste twee combinaties met deze som die behouden zijn.

Als mogelijkheid 1 of 3 zich voordoet kan de som niet de goede zijn (bij mogelijkheid 1 zou S, na zelf gesproken te hebben, zelfs zeker kunnen weten dat P het antwoord nog steeds niet kon weten, terwijl het tegendeel het geval is; bij mogelijkheid 3 zou S, zelfs nadat P heeft verklaard het antwoord te weten, zelf nog steeds de oplossing niet kennen, terwijl in feite S die nu wel weet). Dus moet het gaan om een som die in het lijstje voorkomt en waarvoor mogelijkheid 2 zich voordoet. Hopelijk is er nu precies één zo'n som, zodat ook wij de oplossing kunnen kennen. Dat zal het geval blijken te zijn.

In feite blijkt mogelijkheid 1 zich nooit voor te doen, en meestal mogelijkheid 3. Dit komt onder meer omdat, door bovenvermelde regel, er tamelijk veel combinaties zijn die zeker behouden zijn. In onderstaande, onvolledige, tabel, zijn deze combinaties vet gedrukt.

Als men van alle mogelijke combinaties die horen bij deze sommen een tabel maakt krijgt men een tabel als volgt (de rijen worden steeds langer, en slechts een selectie is getoond):

Som
11	(2,9)	(3,8)	(4,7)	(5,6)
17	(2,15)	(3,14)	(4,13)	(5,12)	(6,11)	(7,10)	(8,9)
23	(2,21)	(3,20)	(4,19)	(5,18)	(6,17)	(7,16)	(8,15)	(9,14)	(10,13)	(11,12)
27	(2,25)	(3,24)	(4,23)	(5,22)	(6,21)	(7,20)	(8,19)	...
29	(2,27)	(3,26)	(4,25)	(5,24)	(6,23)	(7,22)	(8,21)	(9,20)	(10,19)	(11,18)	(12,17)	(13,16)	(14,15)
35	(2,33)	(3,32)	(4,31)	(5,30)	(6,29)	(7,28)	(8,27)	...	(16,19)	(15,18)
37	(2,35)	(3,34)	(4,33)	(5,32)	(6,31)	(7,30)	(8,29)	...
41	(2,39)	(3,38)	(4,37)	(5,36)	(6,35)	(7,34)	(8,33)	(9,32)	...	(16,25)	...
47	(2,45)	(3,44)	(4,43)	(5,42)	...	(16,31)
51	(2,49)	(3,48)	(4,47)	(5,42)	...	(8,43)	...
53	(2,51)	(3,50)	(4,49)	(5,48)	...	(16,37)	...	(21,32)	...

Elke rij bevat ten minste één vet gedrukt paar, dat dus zeker behouden is, zodat als gezegd bovengenoemde mogelijkheid 1 zich nooit voordoet. Op vier na hebben alle rijen zelfs twee vet gedrukte paren, zodat mogelijkheid 3 zich voordoet voor de rij, en die rij dus niet de gezochte oplossing bevat.

Voor de vier resterende sommen: 17, 29, 41, 53, moeten we de niet vetgedrukte combinaties bekijken of erbij zitten die toch behouden worden; tenslotte hebben we alleen die combinaties gemarkeerd die om een bijzonder eenvoudige reden behouden zijn, maar dat is niet de enige mogelijke reden. Zo geeft bijvoorbeeld de combinatie (4,25) in de rij voor som 29 een product 100, wat twee ontbindingen met een even en oneven factor toelaat: 100 = 4 × 25 = 5 × 20, maar 5 + 20 = 25, hoewel oneven, komt niet in het lijstje van sommen voor. Was het product dus 100, dan kon P weten dat het niet om (5,20) gaat, en alleen (4,25) geeft een som in het lijstje; dan kon P dus het antwoord kennen, en daarom zou S de combinatie (4,25) moeten behouden, evenals (13,16) (wat we al wisten). Daarom zouden we bij een som 29 dus toch in mogelijkheid 3 zijn (er zijn in feite nog meer combinaties die behouden zijn, maar het volstaat te weten dat er ten minste twee zijn). In de rij van 41 kan de combinatie (3,38) niet geschrapt worden: het product 3 × 38 = 114 is ook te ontbinden als 2 × 57 en als 6 × 19, maar noch 2 + 57 = 59 noch 6 + 19 = 25 komt in het lijstje $L$ voor, en die combinaties zijn dus (voor P) uitgesloten. In de rij van 53 is (5,48) de eerste combinatie die behouden is: het product 5 × 48 = 2×2×2×2×3×5 kan weliswaar ook als 3 × 80 en als 15 × 16 als product van een even en oneven getal worden geschreven, maar de bijbehorende sommen 83 en 31 komen niet in $L$ voor.

Resteert dus de rij van 17. Hier kunnen alle combinaties behalve de vetgedrukte (4,13) wel worden geschrapt, en doet dus bovengenoemde mogelijkheid 2 zich voor. Om te zien dat de overige combinaties geschrapt worden moeten we hun product steeds op een andere manier ontbinden in een paar waarvan de som in $L$ voorkomt.

• 2 × 15 = 30 = 5 × 6 en 5 + 6 = 11
• 3 × 14 = 42 = 2 × 21 en 2 + 21 = 23
• 5 × 12 = 60 = 3 × 20 en 3 + 20 = 23
• 6 × 11 = 66 = 2 × 33 en 2 + 33 = 35
• 7 × 10 = 70 = 2 × 35 en 2 + 35 = 37
• 8 × 9 = 72 = 3 × 24 en 3 + 24 = 27

De conclusie is dus dat alleen voor de som 17 mogelijkheid 2 zich voordoet, dus moet de som 17 zijn geweest. Voor die som was alleen de combinatie (4,13) niet geschrapt, dus was $x=4$ en $y=13$; het product was 52.

Zie ook

• Het moeilijkste raadsel aller tijden

Externe links

• (en) Puzzles
• (en) The Impossible Problem
• (en) Two Mathematicians Problem
• (en) Model Checking Sum and Product