Jako że dyskusja wokół zadanej przeze mnie zagadki wzięła i wygasła, czas przedstawić rozwiązanie – a przede wszystkim rozumowanie, które do niego prowadzi.

Przypomnijmy: Trurl i Klapaucjusz dostali, odpowiednio, iloczyn i sumę pewnych liczb naturalnych większych od 1 i mniejszych od 100, po czym przeprowadzili następujący dialog:

TRURL: Nie wiem, co to za liczby.
KLAPAUCJUSZ: Wiedziałem, że nie wiesz.
TRURL: Skoro tak, to już wiem.
KLAPAUCJUSZ: Zatem i ja już wiem.

Jak im się udało znaleźć te liczby? Aby do tego dojść, prześledźmy ich rozmowę krok po kroku:

TRURL: Nie wiem, co to za liczby.

Na pierwszy rzut oka oczywiste, ale nie do końca – gdyby bowiem Trurl dostał iloczyn dwóch liczb pierwszych, byłby w stanie jednoznacznie wskazać jego czynniki. Wiemy już zatem, że przynajmniej jedna z szukanych przez nas liczb nie jest pierwsza. Niewiele, ale dobre i to na początek.

Update: Jak słusznie zauważył IRem, możemy w tym miejscu odrzucić również przypadki skrajne (typu 99 * 99), iloczyny liczby pierwszej i jej kwadratu (8, 27, 64, 125…) oraz iloczyny, w których liczba pierwsza jest tak duża, że pomnożona przez którykolwiek czynnik liczby złożonej dałaby ponad sto (np. 83 * 4 albo 37 * 15). Nie ma to jednak wpływu na dalszy tok rozumowania.

KLAPAUCJUSZ: Wiedziałem, że nie wiesz.

Jak Klapaucjusz mógł do tego dojść? Biorąc pod uwagę spostrzeżenie z poprzedniego punktu, tylko w jeden sposób: liczba, którą dostał, musiała być niemożliwa do przedstawienia w postaci sumy dwóch liczb pierwszych. Pytanie, czy istnieją takie liczby, a jeśli tak, to ile ich jest? Cóż, parzyste od razu skreślamy – co prawda silna hipoteza Goldbacha pozostaje nierozstrzygnięta, ale w interesującym nas przedziale z całą pewnością nie znajdziemy kontrprzykładu. Co do liczb nieparzystych: zwróćmy uwagę, że każda taka liczba musi być sumą liczby parzystej i nieparzystej, a jedyną parzystą liczbą pierwszą jest 2. To oznacza, że nieparzysta liczba X może być przedstawiona jako suma dwóch liczb pierwszych wtedy i tylko wtedy, gdy X – 2 jest liczbą pierwszą. Zatem liczb pasujących do stwierdzenia Klapaucjusza będzie sporo.

Pierwsza z nich to 11. Sprawdźmy: 11 = 2 + 9 = 3 + 8 = 4 + 7 = 5 + 6. Pasuje.

Kolejne to 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59… W sumie aż 54 liczby, więc nadal jesteśmy w lesie. Idźmy dalej.

TRURL: Skoro tak, to już wiem.

Dzięki informacji od swojego kolegi Trurl mógł oczywiście mocno zawęzić liczbę rozwiązań, ale jak to się stało, że od razu zostało mu tylko jedno? Ano tak, że ze wszystkich możliwych czynników jego iloczynu, tylko jedna para dawała sumę spełniającą kryterium z poprzedniego punktu. Iloczynem tym mogło więc być np. 18, które można przedstawić jako 3 * 6 (w sumie 9, które na liście Klapaucjusza nie figuruje) albo 2 * 9 (w sumie 11, a więc sukces). Ale mogło to być także np. 24 lub 28 – natomiast nie 30, bo to można rozbić na 5 * 6 (w sumie 11) albo 2 * 15 (w sumie 17, druga pozycja na liście). Liczba możliwości mocno spada, ale jednoznacznego rozwiązania wciąż nie mamy.

KLAPAUCJUSZ: Zatem i ja już wiem.

Po raz kolejny pytamy: skąd? Przecież jeśli dostał np. 11, to wprawdzie mógł wywnioskować, że 5 i 6 odpada, z przyczyn opisanych w poprzednim punkcie, ale czym się różni 2 i 9 od 3 i 8 lub 4 i 7? Niczym – każda z tych par równie dobrze mogłaby być tą właściwą. A z tego wniosek, że Klapaucjusz dostał taką liczbę, dla której tylko jedna para substratów daje iloczyn pozwalający Trurlowi znaleźć rozwiązanie. Jak wskazać tę liczbę? Zła wiadomość jest taka, że chyba tylko sprawdzając po kolei, a przynajmniej ja nie znalazłem lepszego sposobu. Dobra wiadomość natomiast, że długo szukać nie będzie trzeba:

17 = 2 + 15 = 3 + 14 = 4 + 13 = 5 + 12 = 6 + 11 = 7 + 10 = 8 + 9

2 * 15 = 30 = 5 * 6 (w sumie 11)
3 * 14 = 42 = 2 * 21 (w sumie 23)
4 * 13 = 52
5 * 12 = 60 = 3 * 20 (w sumie 23)
6 * 11 = 66 = 2 * 33 (w sumie 35)
7 * 10 = 70 = 2 * 35 (w sumie 37)
8 * 9 = 72 = 3 * 24 (w sumie 27)

Jak widać, dla wszystkich par możemy otrzymać sumę z listy Klapaucjusza – z wyjątkiem 4 i 13. Mamy rozwiązanie!

Ale czy jedyne? Przecież zostało jeszcze ponad pół setki liczb do sprawdzenia, więc może znajdzie się tych rozwiązań więcej? Cóż, sprawdzanie wszystkiego ręcznie to robota na godziny, ale od czego komputery – napisany w pięć minut skrypt załatwia sprawę w ułamku sekundy, a wynik jest pozytywny: żadna liczba oprócz 17 nie daje jednego rozwiązania. Uff!

Sprawdzamy

Gdyby ktoś nie miał jeszcze pewności, albo nie do końca zrozumiał cały ten wywód, powtórzmy dialog jeszcze raz, dodając skrócony tok myślenia rozmówców:

TRURL: Nie wiem, co to za liczby. (dostałem 52, to może być 2 * 26 albo 4 * 13)
KLAPAUCJUSZ: Wiedziałem, że nie wiesz. (dostałem 17, nie da się tego rozbić na dwie liczby pierwsze)
TRURL: Skoro tak, to już wiem. (Klapaucjusz wiedział, że liczby pierwsze odpadają, czyli musiał dostać coś z listy: 11, 17, 23, 27, 29 itd. 2 + 26 = 28, a 4 + 13 = 17, więc mam rozwiązanie)
KLAPAUCJUSZ: Zatem i ja już wiem. (z iloczynów liczb, które mogą dać w sumie 17, tylko jeden, 4 * 13 = 52, mógł być jednoznacznie rozłożony przez Trurla, każdy inny pozostawiłby go jeszcze w niepewności – więc ja też mam rozwiązanie)

Mam nadzieję, że wszystko jest już wystarczająco jasne.

Bonus

Gdyby komuś jeszcze było mało, dodatkowa zagadka: jakie jeszcze pary liczb Trurl i Klapaucjusz mogliby rozszyfrować, prowadząc dialog złożony z wypowiedzi typu „wiem/nie wiem”? Od razu zastrzegam, że na to pytanie już nie znam odpowiedzi, a biorąc pod uwagę liczbę możliwych kombinacji, trzeba by było poświęcić sporo czasu na myślenie albo napisać program, który potrafiłby to zrobić automatycznie – o ile to w ogóle możliwe…