"Zwięzły i jasny opis sposobu rozwiązywania tego twardego (komputerowego?) orzecha, to także wyzwanie."

Zwięźle nie będzie, ale mam nadzieję, że będzie jasno!!!

Zacznę od rozwiązania: szukane liczby to 4 i 13 oraz od wyjaśnienia drobnej nieścisłości pojawiającej się w treści zadania.
Mianowicie: arcymistrzowie wiedzą, że obie szukane liczby są większe od 1, ale czy wiedzą, że ich suma jest mniejsza niż 100? Oczywiście D zna tę sumę, więc wie, że jest ona mniejsza niż 100. Ale informacja o tym, że suma szukanych liczb jest mniejsza niż 100 jest podana w treści zadania w sposób nieprecyzyjny, tzn. nie jest jednoznaczne czy M wie o tym, czy nie wie.
W dalszej części zakładam, że M wie o tym, że suma szukanych liczb jest mniejsza niż 100.

Przyjęte oznaczenia:
 - x, y - szukane liczby
 - ILO = x * y - wartość znana arcymistrzowi M
 - SUM = x + y - wartość znana arcymistrzowi D

Analizujemy krok po kroku wypowiedzi arcymistrzów:

[[[ pozwolę sobie rozbić wpis na kilka mniejszych, aby blog nie uciął czegoś istotnego ]]]


1. "M: Nie wiem, jakie to liczby."

Zastanówmy się, w jakiej sytuacji M mógłby znać liczby x i y (oznaczamy tę sytuację przez (A) - i pamiętamy, że (A) opisuje sytuację, która nie występuje!).
Gdyby ILO było iloczynem dwóch liczb pierwszych (powiedzmy p i q), to wtedy wiedziałby, że x=p oraz y=q (lub odwrotnie, co oczywiście nie ma znaczenia w kontekście zadania).
A zatem w takiej sytuacji M od razu stwierdziłby, że zna obie szukane liczby.

Ponieważ tak nie jest, więc możemy założyć, że ILO jest iloczynem conajmniej trzech liczb pierwszych (oczywiście każda liczba pierwsza może się w tym iloczynie powtarzać).



2. "D: Ja także nie wiem i wiedziałem, że nie będziesz wiedział."

Informacja o tym, że D nie zna liczb x i y jest mało przydatna. Wyklucza bowiem jako rozwiązania jedynie pary (2, 2) oraz (2, 3) (czyli S=4 oraz S=5). W pozostałych przypadkach D ma przynajmniej dwie możliwości, które mogą prowadzić do różnych rozwiązań.

Ciekawszą informacją jest "D: wiedziałem, że nie będziesz wiedział."

To oznacza, że D wie o tym, że nie może zachodzić żaden przypadek (A).
Ponieważa (A) zostało już omówione, jako sytuacja, w której ILO jest iloczynem dwóch liczb pierwszych, więc to oznacza, że wartość SUM = x + y znana przez D nie może prowadzić do sytuacji, w której obie liczby x i y są pierwsze.

Przykłady:
Gdyby D znał wartość SUM = 8, to mogłoby być SUM = 3 + 5, wtedy ILO = 3 * 5 = 15, i w takim układzie D nie mógłby stwierdzić tego, co stwierdził.
Gdyby D znał wartość SUM = 36, to mógłby przypuszczać, że SUM = 17 + 19, wtedy ILO = 17 * 19, i w takim układzie M znałby obie szukane liczby, zatem SUM = 36 również odpada.
Gdyby D znał wartość SUM = 49, to mógłby przypuszczać, że SUM = 2 + 47, wtedy ILO = 2 * 47, i również w tym przypadku M znałby obie szukane liczby.

Zatem wypowiedź D informuje wszystkich (a w szczególności arcymistrza M), że SUM nie może być sumą dwóch liczb pierwszych - w tym miejscu ocieramy się o hipoteze Goldbacha. Wnioskujemy zatem, że gdyby SUM było liczbą parzystą, to wtedy byłoby sumą dwóch liczb pierwszych SUM = p + q, a wtedy wystąpiłoby (A), które nie wystąpiło.
W praktyce oznacza to, że spośród wszystkich możliwych sum: {4, 5, ..., 99} wykluczamy te, które są sumą dwóch liczb pierwszych.

A zatem zbiór wszystkich możliwych SUM ograniczamy do 24 elementów (ten etap wykonałem jeszcze ręcznie):
S = {11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95, 97}

Nazwijmy ten warunek jako (B) - tzn. że SUM należy do zbioru S.
I jeszcze przypomnijmy: warunek (A) nie był spełniony, natomiast warunek (B) jest spełniony.

I jeszcze raz wyjaśnienie: w zbiorze potancjalnych wartości SUM brakuje elementów parzystych, bo każdy element parzysty mniejszy od 100 jest sumą pewnych dwóch licz"Zwięzły i jasny opis sposobu rozwiązywania tego twardego (komputerowego?) orzecha, to także wyzwanie."

Zwięźle nie będzie, ale mam nadzieję, że będzie jasno!!!

Zacznę od rozwiązania: szukane liczby to 4 i 13 oraz od wyjaśnienia drobnej nieścisłości pojawiającej się w treści zadania.
Mianowicie: arcymistrzowie wiedzą, że obie szukane liczby są większe od 1, ale czy wiedzą, że ich suma jest mniejsza niż 100? Oczywiście D zna tę sumę, więc wie, że jest ona mniejsza niż 100. Ale informacja o tym, że suma szukanych liczb jest mniejsza niż 100 jest podana w treści zadania w sposób nieprecyzyjny, tzn. nie jest jednoznaczne czy M wie o tym, czy nie wie.
W dalszej części zakładam, że M wie o tym, że suma szukanych liczb jest mniejsza niż 100.

Przyjęte oznaczenia:
 - x, y - szukane liczby
 - ILO = x * y - wartość znana arcymistrzowi M
 - SUM = x + y - wartość znana arcymistrzowi D

Analizujemy krok po kroku wypowiedzi arcymistrzów:

[[[ pozwolę sobie rozbić wpis na kilka mniejszych, aby blog nie uciął czegoś istotnego ]]]


1. "M: Nie wiem, jakie to liczby."

Zastanówmy się, w jakiej sytuacji M mógłby znać liczby x i y (oznaczamy tę sytuację przez (A) - i pamiętamy, że (A) opisuje sytuację, która nie występuje!).
Gdyby ILO było iloczynem dwóch liczb pierwszych (powiedzmy p i q), to wtedy wiedziałby, że x=p oraz y=q (lub odwrotnie, co oczywiście nie ma znaczenia w kontekście zadania).
A zatem w takiej sytuacji M od razu stwierdziłby, że zna obie szukane liczby.

Ponieważ tak nie jest, więc możemy założyć, że ILO jest iloczynem conajmniej trzech liczb pierwszych (oczywiście każda liczba pierwsza może się w tym iloczynie powtarzać).



2. "D: Ja także nie wiem i wiedziałem, że nie będziesz wiedział."

Informacja o tym, że D nie zna liczb x i y jest mało przydatna. Wyklucza bowiem jako rozwiązania jedynie pary (2, 2) oraz (2, 3) (czyli S=4 oraz S=5). W pozostałych przypadkach D ma przynajmniej dwie możliwości, które mogą prowadzić do różnych rozwiązań.

Ciekawszą informacją jest "D: wiedziałem, że nie będziesz wiedział."

To oznacza, że D wie o tym, że nie może zachodzić żaden przypadek (A).
Ponieważa (A) zostało już omówione, jako sytuacja, w której ILO jest iloczynem dwóch liczb pierwszych, więc to oznacza, że wartość SUM = x + y znana przez D nie może prowadzić do sytuacji, w której obie liczby x i y są pierwsze.

Przykłady:
Gdyby D znał wartość SUM = 8, to mogłoby być SUM = 3 + 5, wtedy ILO = 3 * 5 = 15, i w takim układzie D nie mógłby stwierdzić tego, co stwierdził.
Gdyby D znał wartość SUM = 36, to mógłby przypuszczać, że SUM = 17 + 19, wtedy ILO = 17 * 19, i w takim układzie M znałby obie szukane liczby, zatem SUM = 36 również odpada.
Gdyby D znał wartość SUM = 49, to mógłby przypuszczać, że SUM = 2 + 47, wtedy ILO = 2 * 47, i również w tym przypadku M znałby obie szukane liczby.

Zatem wypowiedź D informuje wszystkich (a w szczególności arcymistrza M), że SUM nie może być sumą dwóch liczb pierwszych - w tym miejscu ocieramy się o hipoteze Goldbacha. Wnioskujemy zatem, że gdyby SUM było liczbą parzystą, to wtedy byłoby sumą dwóch liczb pierwszych SUM = p + q, a wtedy wystąpiłoby (A), które nie wystąpiło.
W praktyce oznacza to, że spośród wszystkich możliwych sum: {4, 5, ..., 99} wykluczamy te, które są sumą dwóch liczb pierwszych.

A zatem zbiór wszystkich możliwych SUM ograniczamy do 24 elementów (ten etap wykonałem jeszcze ręcznie):
S = {11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95, 97}

Nazwijmy ten warunek jako (B) - tzn. że SUM należy do zbioru S.
I jeszcze przypomnijmy: warunek (A) nie był spełniony, natomiast warunek (B) jest spełniony.

I jeszcze raz wyjaśnienie: w zbiorze potancjalnych wartości SUM brakuje elementów parzystych, bo każdy element parzysty mniejszy od 100 jest sumą pewnych dwóch liczb pierwszych (a wtedy zachodziłoby (A)).
Z pozostałych liczb nieparzystych pozostały tylko te, które są o 2 większe od liczby nieparzystej złożonej (bowiem gdyby liczba nieparzysta była sumą dwóch liczb pierwszych, to jednym ze składników musiała by być liczba 2).

Najważniejsze z punktu widzenia dalszej części rozwiązania jest to, że M mógł przeprowadzić całą powyższą analizę wszystkich możliwości na podstawie informacji, które otrzymał od D.



3. "M: Skoro tak, to ja teraz już odgadłem obie liczby."

Co oznacza wypowiedź M?
Załóżmy, że znana przez niego wartość to ILO = p_1 * p_2 * p_3 * ... (mamy przynajmniej 3 czynniki pierwsze w iloczynie).
Wypowiedź M oznacza, że rozważając wszystkie możliwe podziały znanych mu wartości p_i pomiędzy liczby x i y tylko jeden z nich daje liczbę x+y należącą do zbioru S (który to zbiór jest już znany M).

W tym miejscu zaprzągłem do pracy komputer, aby dla każdej możliwej wartości ILO znalazł wszystkie możliwe pary x i y, takie że ILO = x * y. Następnie dla każdej potencjalnej pary x i y policzył ich sumę x + y. I dalej jeśli dwie różne sumy uzyskane w ten sposób należały do zbioru S - to oznacza, że rozpatrywana wartość ILO nie jest dobra - bo wtedy M nie mógłby powiedzieć tego, co powiedział w (3). A jeśli dostaniemy tylko jedną sumę należącą do S, to zapisujemy sobie na kartce parę (sum, ilo). Oczywiście dla każdego ilo dostaniemy tylko jedno sum (piszę sum i ilo z małych liter, bo to jest tylko kandydat na rozwiązanie zadania!)

Okazuje się, że w ten sposób dostajemy sporo możliwych wartości ilo, a dla każdej z tych wartości jedną sumę.

Przykład dla ilo = 24 = 2 * 2 * 2 * 3
- może być x=2, y=12, sum = 14 -> błędna
- może być x=3, y=8, sum = 11 -> ok
- może być x=4, y=6, sum = 10 -> błędna

Dla ilo = 24 mamy 3 przypadki, z których tylko jeden daje sumę należącą do zbioru S. Ten przypadek ilo daje nam globalny wpis (sum, ilo) = (11, 24).

Przykład dla ilo = 28 = 2 * 2 * 7
- może być x=2, y=14, sum = 16 -> błędna
- może być x=4, y=7, sum = 11 -> ok

Dla ilo = 28 mamy 2 przypadki, z których tylko jeden daje sumę należącą do zbioru S. Ten przypadek ilo daje nam globalny wpis (sum, ilo) = (11, 28).

Przykład dla ilo = 52 = 2 * 2 * 13
- może być x=2, y=26, sum = 28 -> błędna
- może być x=4, y=13, sum = 17 -> ok

Dla ilo = 52 mamy 2 przypadki, z których tylko jeden daje sumę należącą do zbioru S. Ten przypadek ilo daje nam globalny wpis (sum, ilo) = (17, 52).

Przykład dla ilo = 60 = 2 * 2 * 3 * 5
- może być x=3, y=20, sum = 23 -> ok
- może być x=5, y=12, sum = 17 -> ok

Zatem dla ilo = 60 mamy dwa przypadki, w których sum należy do zbioru S, zatem ilo = 60 nie może występować.

W wyniku wypowiedzi (3) otrzymaliśmy listę par liczb postaci (sum, ilo), przy czym każdy iloczyn ilo występuje na tej liście dokładnie jeden raz - natomiast wartości sum mogą się powtarzać. Niech ta lista par zostanie oznaczona jako (C)



4. "D: W takim razie ja teraz również je odgadłem."

D odgadł rozwiązanie. To znaczy, że suma SUM, którą zna, na liście (C) występuje dokładnie jeden raz! Bo gdyby występowała więcej niż jeden raz, to wtedy możliwe byłyby conajmniej 2 wartości ilo, a to prowadziłoby do dwóch różnych rozwiązań x i y, a wtedy D nie mógłby powiedzieć tego, co powiedział w (4).

Cała trudność obliczeniowa tego zadania sprowadza się zatem do wyznaczenia listy (C) - ten krok pozwoliłem sobie wykonać komputerowo. Na tej liście wszystkie wartości sum (poza 17) występowały co najmniej 2 razy (w przykładach podanych do punktu (3) można znaleźć dwa wpisy dla sum = 11, z ilo=24 oraz ilo=28 - to dyskwalifikuje sum=11 jako rozwiązanie, bo wtedy D nie mógłby stwierdzić tego co stwierdził w (4)).

Natomiast para (sum, ilo) = (17, 52) jest jedyną parą na liście (C), w której sum=17. Zatem jest to jedyne rozwiązanie zagadki, które oczywiście daje nam x=4 oraz y=13.
b pierwszych (a wtedy zachodziłoby (A)).
Z pozostałych liczb nieparzystych pozostały tylko te, które są o 2 większe od liczby nieparzystej złożonej (bowiem gdyby liczba nieparzysta była sumą dwóch liczb pierwszych, to jednym ze składników musiała by być liczba 2).

Najważniejsze z punktu widzenia dalszej części rozwiązania jest to, że M mógł przeprowadzić całą powyższą analizę wszystkich możliwości na podstawie informacji, które otrzymał od D.



3. "M: Skoro tak, to ja teraz już odgadłem obie liczby."

Co oznacza wypowiedź M?
Załóżmy, że znana przez niego wartość to ILO = p_1 * p_2 * p_3 * ... (mamy przynajmniej 3 czynniki pierwsze w iloczynie).
Wypowiedź M oznacza, że rozważając wszystkie możliwe podziały znanych mu wartości p_i pomiędzy liczby x i y tylko jeden z nich daje liczbę x+y należącą do zbioru S (który to zbiór jest już znany M).

W tym miejscu zaprzągłem do pracy komputer, aby dla każdej możliwej wartości ILO znalazł wszystkie możliwe pary x i y, takie że ILO = x * y. Następnie dla każdej potencjalnej pary x i y policzył ich sumę x + y. I dalej jeśli dwie różne sumy uzyskane w ten sposób należały do zbioru S - to oznacza, że rozpatrywana wartość ILO nie jest dobra - bo wtedy M nie mógłby powiedzieć tego, co powiedział w (3). A jeśli dostaniemy tylko jedną sumę należącą do S, to zapisujemy sobie na kartce parę (sum, ilo). Oczywiście dla każdego ilo dostaniemy tylko jedno sum (piszę sum i ilo z małych liter, bo to jest tylko kandydat na rozwiązanie zadania!)

Okazuje się, że w ten sposób dostajemy sporo możliwych wartości ilo, a dla każdej z tych wartości jedną sumę.

Przykład dla ilo = 24 = 2 * 2 * 2 * 3
- może być x=2, y=12, sum = 14 -> błędna
- może być x=3, y=8, sum = 11 -> ok
- może być x=4, y=6, sum = 10 -> błędna

Dla ilo = 24 mamy 3 przypadki, z których tylko jeden daje sumę należącą do zbioru S. Ten przypadek ilo daje nam globalny wpis (sum, ilo) = (11, 24).

Przykład dla ilo = 28 = 2 * 2 * 7
- może być x=2, y=14, sum = 16 -> błędna
- może być x=4, y=7, sum = 11 -> ok

Dla ilo = 28 mamy 2 przypadki, z których tylko jeden daje sumę należącą do zbioru S. Ten przypadek ilo daje nam globalny wpis (sum, ilo) = (11, 28).

Przykład dla ilo = 52 = 2 * 2 * 13
- może być x=2, y=26, sum = 28 -> błędna
- może być x=4, y=13, sum = 17 -> ok

Dla ilo = 52 mamy 2 przypadki, z których tylko jeden daje sumę należącą do zbioru S. Ten przypadek ilo daje nam globalny wpis (sum, ilo) = (17, 52).

Przykład dla ilo = 60 = 2 * 2 * 3 * 5
- może być x=3, y=20, sum = 23 -> ok
- może być x=5, y=12, sum = 17 -> ok

Zatem dla ilo = 60 mamy dwa przypadki, w których sum należy do zbioru S, zatem ilo = 60 nie może występować.

W wyniku wypowiedzi (3) otrzymaliśmy listę par liczb postaci (sum, ilo), przy czym każdy iloczyn ilo występuje na tej liście dokładnie jeden raz - natomiast wartości sum mogą się powtarzać. Niech ta lista par zostanie oznaczona jako (C)



4. "D: W takim razie ja teraz również je odgadłem."

D odgadł rozwiązanie. To znaczy, że suma SUM, którą zna, na liście (C) występuje dokładnie jeden raz! Bo gdyby występowała więcej niż jeden raz, to wtedy możliwe byłyby conajmniej 2 wartości ilo, a to prowadziłoby do dwóch różnych rozwiązań x i y, a wtedy D nie mógłby powiedzieć tego, co powiedział w (4).

Cała trudność obliczeniowa tego zadania sprowadza się zatem do wyznaczenia listy (C) - ten krok pozwoliłem sobie wykonać komputerowo. Na tej liście wszystkie wartości sum (poza 17) występowały co najmniej 2 razy (w przykładach podanych do punktu (3) można znaleźć dwa wpisy dla sum = 11, z ilo=24 oraz ilo=28 - to dyskwalifikuje sum=11 jako rozwiązanie, bo wtedy D nie mógłby stwierdzić tego co stwierdził w (4)).

Natomiast para (sum, ilo) = (17, 52) jest jedyną parą na liście (C), w której sum=17. Zatem jest to jedyne rozwiązanie zagadki, które oczywiście daje nam x=4 oraz y=13.