Reklama
Polityka_blog_top_bill_desktop
Polityka_blog_top_bill_mobile_Adslot1
Polityka_blog_top_bill_mobile_Adslot2
Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko

6.06.2018
środa

Parka

6 czerwca 2018, środa,

W majowym numerze „Świata nauki” w artykule dotyczącym teorii (hipotezy) Goldbacha znalazło się zadanie silnie logiczne (i jeszcze silniej obliczeniowe), które można by uznać za klasyczne, ale też trochę zapomniane. Jego związek ze wspomnianą teorią wydaje się w pierwszej chwili wątpliwy, bo pojawia się dopiero w trakcie rozwiązywania i nie jest bezpośredni.
Przypominam hipotezę Goldbacha: każda liczba parzysta większa od 2 jest sumą dwóch liczb pierwszych.
Na szerszym forum zadanie gości rzadko, w różnej formie i zwykle budzi kontrowersje. Podejrzewam, że teraz też tak będzie. Oto ono:

Dwaj arcymistrzowie błyskawicznego liczenia i logicznego myślenia stoją przed wyzwaniem, polegającym na odgadnięciu dwu liczb całkowitych większych od jednego. Mistrz M(nożenie) zna tylko ich iloczyn, mistrz D(odawanie) – tylko sumę, która jest mniejsza niż sto. Obaj prowadzą krótki dialog.
M: Nie wiem, jakie to liczby.
D: Ja także nie wiem i wiedziałem, że nie będziesz wiedział.
M: Skoro tak, to ja teraz już odgadłem obie liczby.
D: W takim razie ja teraz również je odgadłem.
Jakie liczby były odgadywane?

Zakładamy, że czas między wypowiedziami był na tyle długi, że obaj mogli wszystko dogłębnie przemyśleć i policzyć.
Zwięzły i jasny opis sposobu rozwiązywania tego twardego (komputerowego?) orzecha, to także wyzwanie.

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 20

Dodaj komentarz »
  1. Na odgadnięciu dwóch różnych liczb? Czy niekoniecznie różnych?

    Moim zdaniem podawanie tej informacji nie jest konieczne.
    mp

  2. Z hipotezy Goldbacha (udowodnionej dla tak niewielkich liczb z jakimi mamy tu do czynienia) wynika, że suma nie może być liczbą parzystą, bo taką zawsze da się przedstawić jako iloczyn dwóch liczb pierwszych, a więc D nie mógłby powiedzieć: wiedziałem na pewno, że nie będziesz wiedział. Np. D ma 28, iloczyn mógłby być 23*5 = 115, jedyna możliwość, M wiedziałby od razu.
    Ale są liczby nieparzyste, które dają się przedstawić jako suma dwóch liczb pierwszych, z których jedną jest 2, np. 5, 7, 9. 11 już nie, potem 13 i 15 znów, a 17 nie. Suma na kartce D zatem musi być 11, 17, 23, 27, etc. Każdej z tych sum odpowiadają iloczyny, na przykład sumie 11 – 18, 24, 28, 30, sumie 17 – 30, 42, 52, 60, 66, 70, 72, etc. Możemy skonstruować taką tablicę sumy vs iloczyny. Teraz jeśli M będzie miał przykładowo 30, to nie będzie pewien, czy D ma sumę 11, czy 17, a więc czy chodzi o parę 15,2, czy 5,6. Iloczyn zatem musi być przypisany jednoznacznie do danej sumy. Pozwala to skreślić mnóstwo iloczynów. Ale taki iloczyn dla tej sumy powinien być jeden i tylko jeden, bo z kolei D mając 11 nie będzie pewien, czy M ma 18, 24, czy 28. Szukamy więc sumy, dla której zostanie jeden nieskreślony iloczyn. Okazuje się, że jest to tylko para 17-52, liczby zatem będą 4 i 13.
    Sprawdzenie: M widzi 52, myśli: mogę mieć 4 i 13 (suma 17) lub 2 i 26 (suma 28), nie wiem. D widzi 17, też nie wie, ale wie, że M nie mógł wiedzieć, bo 17 nie da się zapisać jako suma dwóch liczb pierwszych, i to oznajmia. M jest już w domu: suma na pewno nie jest 28, musi być 17, muszą być liczby 13 i 4, więc mówi: wiem. D myśli: gdybyś miał na przykład 30 (15*2), to nie byłbyś pewny, czy ja mam 17, czy 11 (5+6). Gdybyś miał 42, etc, z pominięciem 52, zawsze znalazłyby się co najmniej dwie pary, dające dopuszczalne sumy z listy sum. Musisz więc mieć 52, czyli ja teraz też wiem.

  3. Wyszło mi, że iloczyn to 52, a suma 17.
    Rozumowanie było takie:
    M: Nie wiem, jakie to liczby.
    – Czyli nie jest to iloczyn liczb pierwszych.
    D: Ja także nie wiem i wiedziałem, że nie będziesz wiedział.
    – Czyli nie jest to suma dwóch liczb pierwszych, bo wtedy nie mógłby mieć pewności. To ze zbioru sum eliminuje wszystkie liczby parzyste oraz nieparzyste będące sumą liczby 2 i liczby pierwszej. Do wzięcia pod uwagę zostały 24 liczby.
    Rozbiłam je na wszystkie na dwa składniki, a potem wymnożyłam te składniki. Otrzymałam pulę kilku setek iloczynów.
    M: Skoro tak, to ja teraz już odgadłem obie liczby.
    – Czyli iloczyn musi być unikatowy. W wyżej wspomnianej puli jest 341 unikatowych iloczynów.
    D: W takim razie ja teraz również je odgadłem.
    – Czyli istnieje tylko jedna* suma, którą można rozbić na dwa składniki takie, że po wymnożeniu dadzą unikatowy iloczyn.

    * Zapewne tylko jedna, przyznaję się, że nie sprawdzałam wszystkich 341 liczb, bo jest po godz. 21, już 2 godziny nad tym siedzę… no, późno jest… Iloczyn 52 wpadł mi w oko dość szybko i wydaje się pasować.
    52 = 2*26 = 4*13
    17 = 4 + 13

    Pani Olu, podziwiam i gratuluję, bo poza logiką liczenie tego na piechotę jest benedyktyńskie.
    mp

  4. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  5. Na piechotę? No nie, sumy i iloczyny Excel liczył. No chyba że Excel to piechota w porównaniu do tej tam lekkiej jazdy nowoczesnych programów, których nie znam 🙂

  6. Te liczby to 2 i 6.
    M : zna iloczyn =12, więc bierze pod uwagę 3 i 4 albo 2 i 6. Wnioskuje, że D ma liczbę 7 albo 8. Ma do wyboru dwie możliwości, więc mówi, że nie wie jakie to liczby.
    D : przypuśćmy, że ma 7,a 7=2+5=3+4. Gdyby to były liczby 2 i 5, to M miałby 2×5=10 . Ale wtedy M od razu wiedziałby jakie liczby są szukane, więc 2 i 5 D odrzuca, a gdyby 3 i 4 było dobrym rozwiązaniem , D powiedziałby, ze zna szukane liczby.
    D ma sumę 8. 8=2+6=4+4,czyli dwie możliwe odpowiedzi, więc mówi, że nie zna odp.
    M : wnioskuje, że D ma sumę 8 , bo gdyby miał 7 od razu znałby odpowiedź. M wie, że szukane liczby to 2 i 6 .
    D : też ustala, że to 2 i 6, że M ma iloczyn 12. 4 i 4 tez dają sumę 8, liczba 4×4=16 może być przedstawiona jako 2×8 albo 4×4 i M nie wiedziałby jakie jest rozwiązanie

  7. @logi
    Ale D mówi coś więcej niż to, że nie wie (co akurat nie dziwi specjalnie). Mówi iż już wcześniej wiedział, że M nie będzie wiedział od razu. Gdyby szukanymi liczbami były 2 i 6, to D widziałby tylko sumę 8, której jednym z rozkładów jest 3+5, który dyskretnie pominąłeś. Wtedy, wg wiedzy D, mistrz M mógłby widzieć iloczyn 3*5, który mógłby zgadnąć od razu, co jest sprzeczne z drugą częścią pierwszej wypowiedzi D. Wniosek: 2 i 6 nie jest rozwiązaniem.

  8. W skrócie, rozwiązanie to: I=52, S=17 => x=4, y=13 (lub odwrotnie).
    Czy jest ono jedyne? Raczej tak, zbadałem większość przypadków, ale nie wszystkie.
    Jest to jedyne rozwiązanie z iloczynem postaci I = (2^k)*p, gdzie p liczba pierwsza nieparzysta, k>1. Tylko taki iloczyn zawsze pozwala mistrzowi M odgadnąć rozwiązanie po pierwszej wymianie zadań. Jednak nie można z góry wykluczyć, że M widzi bardziej złożoną postać iloczynu.

    Założyłem, że mistrz M wie iż S < 100, choć nie zna jej dokładnej wartości. Sformułowanie zadania w tym punkcie nie jest jednoznaczne. Niestety problemy techniczne uniemożliwiają mi zamieszczenie tu opisu rozwiązania.

    Łatwo zbagatelizować to zadanie, podczas gdy wymaga ono mozolnego pochylenia się nad konkretnymi liczbami, co pozwala docenić D i M jako prawdziwych mistrzów ciętej riposty

  9. No to ja zgaduję, że szukanymi liczbami są 4 i 13.

    Rozwiązanie:
    D wie, że żeby M nie wiedział jaki jest iloczyn, to musi to być iloczyn liczb z których przynajmniej jedna nie jest pierwsza.

    Możemy wybrać takie sumy, których dowolny rozkład nie zawiera dwóch liczb pierwszych. Są to:
    Zs = 11, 27, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95 i 97

    Czyli M wie, że D zna jedną z tych sum.

    M rozkłada sobie poszczególne sumy na składniki, mnoży je, rozkłada na czynniki i szuka takich, które są jednoznaczne, tzn:
    dla ai = 2,3,4…
    S1 = ai+(S-ai),
    M = ai* (S-ai) = c*d,
    S2 = c+d -> jednoznacznie można wybrać rozwiązanie dla danej sumy.

    Myślałem, że jednoznacznie jest tylko wtedy gdy nie da się zrobić sumy S2 z S1 (tak, że S2 też należy do Zs), ale nie ma takich przypadków.

    Ciekawy przypadek jest natomiast dla sumy 17.
    można ją rozłożyć na:
    2+15 -> iloczyn = 30
    3+14 -> iloczyn = 42
    4+13 -> iloczyn = 52
    5+12 -> iloczyn = 60
    6+11 -> iloczyn = 66
    7+10 -> iloczyn = 70
    8+9 -> iloczyn = 72

    poszczególne iloczyny można rozłożyć na dwa sposoby (z różnymi sumami z Zs) oprócz 52.

    dlatego M jednoznacznie wskazuje 4 i 13 i D również ma możliwość wskazania tej pary.

    PS1> mocno zagmatwane ale jeśli trzeba to opisze dokładniej
    PS2> początek był prosty – liczenie kombinacji iloczynów i sum składników – tutaj komputer jest nieoceniony

  10. „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 ]]]

  11. 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ć).

  12. 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.

  13. 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)

  14. 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.

  15. Pozwolę sobie jeszcze umieścić odnośnik do całego wpisu bez podziału na poszczególne komentarze: https://pastebin.com/sEVmAHUs

    (powinienem to zrobić w pierwszym wpisie, ale nie pomyślałem zawczasu)

  16. I jeszcze drobne sprostowanie:
    Zakladalem, że M wie o tym, że SUM jest mniejsze od 100. Ale chyba ta wiedza nie jest mu potrzebna, bowiem dla większych sum każda suma pojawi się na liście (C) wiele razy… Nie sprawdzałem tego, ale wydaje mi się, że tak będzie…

  17. Liczby to: 4 i 13
    Zwięzły opis rozwiązania zrobię w wolnej chwili 🙂

  18. Dlaczego twierdzimy, że mistrzowie M i D nie mogli widzieć np. poniższych par liczb?

    I=100, S=29
    I=148, S=41
    I=154, S=79
    I=196; S=53
    I=208, S=29
    I=592, S=53

  19. @Markoniusz

    Podałeś przykłady, które wyjaśniają, dlaczego nie mogą być rozwiązaniami.

    Np.
    I=100, S=29
    I=208, S=29

    Gdyby było I=100 oraz S=29, to w (3) zdaniu M stwierdziłby, że zna rozwiązanie (którym są liczby 4 i 25).
    Gdyby było I=208 oraz S=29, to w (3) zdaniu M stwierdziłby, że zna rozwiązanie (którym są liczby 13 i 16).

    W obu powyższych sytuacjach, po wypowiedzi (3), D miałby dokładnie taki sam stan wiedzy, tzn.
    – S=29
    – M znalazł rozwiązanie

    Zatem D przed swoją wypowiedzią (4) nie miałby pewności, czy rozwiązaniem są liczby 4 i 25, czy 13 i 16 (bo D nie zna iloczynu I).

    Zatem S=29 nie może być rozwiązaniem, bowiem D w wypowiedzi (4) stwierdził, że teraz on już też wie jakie to są liczby!

    Podobnie jest dla S=53
    Gdyby S=53, to D przez wypowiedzią (4) miałby dwa możliwe rozwiązania: jedno dla I=196 (tym rozwiązaniem jest 4 i 49) oraz drugie dla I=592 (czyli 19 i 34). Zatem ponownie D nie mógłby stwierdzić tego co w (4), zatem suma S=53 odpada!

    Dla S=41 i S=79 należy znaleźć inne możliwe iloczyny – one w parach z wymienionymi przykładami przeczą możliwości takich sum.

  20. Fakt, tak zadane pytanie wręcz samo podsuwa odpowiedzi a rozwiązując trzeba się trochę naszukać samemu 🙂

css.php