Krzyżowanie bliźniaków
Postanowiłem nawiązać do poprzedniego wpisu, a pretekstem do tego jest osobliwa dyskusja, która wywiązała się w komentarzach. Przypomnę: zadanie polegało na podaniu dowodu, że jeśli pomnożymy liczby tworzące dowolną parę liczb pierwszych bliźniaczych, a następnie dodamy cyfry otrzymanego iloczynu i ewentualnie cyfry powstałej i każdej następnej sumy – aż do otrzymania jednocyfrowego wyniku (tzw. osc, czyli ostatecznej sumy cyfr) – to osc zawsze będzie równe osiem.
Elementarna wersja dowodu zaczyna się od zauważenia, że z trzech kolejnych liczb naturalnych przynajmniej jedna musi być podzielna przez 2 i dokładnie jedna przez 3. Jeśli z tych trzech liczb pierwsza i trzecia są liczbami pierwszymi (bliźniaczymi) – a więc niepodzielnymi ani przez 2, ani przez 3 – to podzielna przez 2 i przez 3, czyli przez 6, musi być liczba środkowa. Zatem pierwsza z liczb bliźniaczych wyraża się wzorem 6n-1, a druga 6n+1, zaś iloczyn liczb bliźniaczych to 36n2-1; 36n2 jest podzielne przez 9, czyli suma cyfr tej liczby równa jest 9, a po odjęciu 1 zostaje 8.
Ku nie tylko mojemu zdziwieniu Mauro Rossi z góry zanegował dowód – nie podając go i uznając za hipotezę, co uzasadniał hipotezą liczb pierwszych bliźniaczych, o których nie wiadomo, czy tworzą ciąg skończony, czy nie. Mam nadzieję, że adwersarz zmienił zdanie, choć warto dodać, że w sieci można znaleźć informację świadczącą na jego korzyść – towarzyszy ona ciągowi A136050 w Encyklopedii ciągów (OEIS). Proszę zwrócić uwagę na podane tam „Conjecture”, czyli hipotezę (przypuszczenie). Wytłumaczenie jest proste. Choć OEIS firmuje ceniony matematyk Neil Sloane, to zwykle bezpośrednio obsługują ją jego podopieczni i błędów w niej nie brakuje. W tym przypadku słowo „Conjecture” należałoby usunąć, bo poprzedza „True”.
Kończąc bliźniaczy temat proponuję ułożyć krzyżówkę 3×3 z sześciu 3-cyfrowych bliźniaków wybranych z 54 wszystkich 3-cyfrowych podanych obok diagramu.
Analogiczna krzyżówka 2×2 jest tylko jedna (poziomo: 11, 73; pionowo: 17, 13). Ile jest „bliźniaczych” krzyżówek 3×3 – to zadanie dla komputerowców. Jedną można jednak utworzyć bez większego trudu i w znacznym stopniu na logikę.
Komentarze z prawidłowym rozwiązaniem ujawniane są wieczorem w przeddzień kolejnego wpisu (z błędnym zwykle od razu). Wpisy pojawiają się co 7 dni.
Komentarze
Na logikę mam już 12, nie licząc symetrii, podam pierwszy:
Krzyżówka jest do bani, gdyż nie występują w niej pary bliźniaków, lecz swobodne bliźniaki bez pary. Wprawdzie w przykładowej krzyżówce 2×2 jest bliźniak 11 i 13, ale dalej są niepowiązane 17 i 73.
W krzyżówce 3×3 podobnie – mogłyby być trzy pary bliźniaków, ale da się – zdaje się, że może być najwyżej jedna para.
W sumie jest 118 rozwiązań, w tym połowa lustrzane, więc tak jakby było 59. Nie wiem, które jest najpiękniejsze, więc nie podam żadnego.
Dzień dobry:
jedno (a raczej dwa) rozwiązania znalezione na piechotę to:
281
829
31(1|3)
Rozwiązaniu pomaga zauważenie, że dolna liczba musi zaczynać się na 1 lub 3. Eliminowanie parzystych, zer i siódemek też przyspiesza szukanie.
Komputer mówi, że takich krzyżówek jest 72 (36 i ich odbicia symetryczne).
(bardzo nieefektywne rozwiązanie tu: https://github.com/tomasz-bosak/lamiblogSolutions/tree/main/krzyzowanieBlizniakow)
Pozdrawiam,
„Czy są papużki nierozłączki? Są. To poproszę jedną”. Taki żart mi się przypomniał, gdy po usiłowaniach ułożenia krzyżówki z 3 par bliźniaków doszłam do wniosku, że się nie da. Z dowolnie wybranych liczb z listy może być taka:
283
421
191
Mam mały problem, bo nie wiem, które rozwiązanie jest tak wyraźnie wyróżnione: moja metoda polega na wypełnieniu najpierw 3-go wiersza i 3-ciej kolumny, nie ma tu wielu możliwości, na przykład 193 i 313, no i uzupełnia się pozostałe cyfry na podstawie listy bliźniaków. Tu jest zaskakująco dużo możliwości:
241
829
313
421
349
313
431
619
313
811
859
313
Wydaje mi się, że wszystkie rozwiązania da radę znaleźć „na piechotę”, mam zamiar sprawdzić jeszcze parę 191-311 zamiast 193 i 313, i może jeszcze coś się znajdzie, a więc cdn.
Oczywiście wszystko co pasuje do 193-313 pasuje też do 191-311 🙂 to byłoby na razie 8 rozwiązań, przy czym trzeba zrobić zastrzeżenie, że właściwie to 16, ze względu na symetrię poziomo vs pionowo. Przykład 2×2 miałby drugie rozwiązanie 17 i 13 poziomo. Cdn.
Jeszcze kilka rozwiązań, kolejno dla par w 3-ciej kolumnie i 3-cim wierszu (lub odwrotnie) 139-199, 137-197 (niepodane, bo analogiczne z powyższym), 139-179, 179-199. Nie wiem, czy w trzech wpisach podałem wszystkie rozwiązania, rozwiązując „na piechotę” można coś przeoczyć, ale jest ich znalezionych do wyboru, do koloru, mnie najbardziej podoba się to jedno tylko z „0”. No a metoda działa.
181
523
199
431
643
199
461
313
199
821
823
199
881
103
199 (jedynak z 0 wśród bliźniaków)
(jedynakiem jest ten z 3 w centrum – vide komentarz bubki 111 mp)
821
823
179
661
413
179
881
229
179
1 8 1
5 2 3
1 7 9
***
181
523
179
***
431
643
179
***
461
313
179
***
821
823
179
***
181
523
199
***
431
643
199
***
461
313
199
***
821
823
199
***
881
103
199
***
641
617
199
***
821
137
199
***
821
827
199
***
881
107
199
***
881
227
199
***
241
829
311
***
281
829
311
***
421
349
311
***
461
349
311
***
811
809
311
***
811
859
311
***
881
229
311
***
881
829
311
***
241
829
313
***
281
829
313
***
421
349
313
***
431
619
313
***
461
349
313
***
811
809
313
***
811
859
313
***
881
229
313
***
881
829
313
***
181
523
197
***
431
643
197
***
461
313
197
***
821
823
197
***
881
103
197
@tomash
Mnie również wyskoczyły 72 rozwiązania, a więc z ciekawości sprawdziłem Twój skrypt. Ten drugi – lepszy (new_better_solution()) – jest ok. 4× szybszy od mojego (przepisałem Twój skrypt na python i porównałem oba algorytmy).
Ciekawostka jest taka, że zanim zacząłem to pisać, to porównałem *na szybko* dwie liczby: 9^9 (ok. 400 mln) oraz kombinacje 9-elementowe z 54 czyli 9C54 = ok. 5,3 mld. Byłem trochę zaskoczony, bo intuicja podpowiadała, aby szukać od strony kombinacji, ale poszedłem za rozumem, a nie sercem. W związku z tym napisałem skrypt, który szuka tych rozwiązań od strony pojedynczych cyfr, czyli ten teoretycznie mniej złożony. Ku mojemu zdziwieniu, Ty szukasz wśród 54 liczb, a jednak robisz to szybciej.
Okazało się, że zrobiłem czeski błąd i sprawdziłem kombinacje 9-elementowe zamiast 6-elementowych. 6C54 = ok. 26 mln, więc jest to o wiele mniej sprawdzeń, niż mi się pierwotnie wydawało.
No i faktycznie – tego rodzaju algorytm jest nie tylko krótszy, ale przede wszystkim szybszy.
Oba te rozwiązania (moje i Twoje-przepisane) są tu:
https://github.com/ersonasolidna/lamiblogswiatnauki/blob/main/2022_07_22_Lamiblog_Krzyzowanie_blizniakow.py
Ręcznie zacząłem sprawdzać rozwiązanie z zerem w środku, bo wydawało mi się to eleganckie i zabawne (bo to zero nigdzie indziej być nie może). I po minucie zaniechałem, bo musiałem się zająć czymś innym, a trzeba było to pociągnąć, bo jak się okazuje, o to rozwiązanie chodziło MP 🙂
Wnioski są dwa: trzeba być uważniejszym, gdy się coś liczy i warto czasami dokończyć to, co się zaczęło:)
@ersonasolidna 🙂
Można jeszcze trochę przyspieszyć (np: separując do osobnego zbioru liczby, które mogą być w ostatniej linii/kolumnie) 🙂
– ale teraz jest i tak już wystarczająco szybko.
Zastanawiam się nad rozwiązaniem @xswedc – ciekawe czy 118 to rezultat dopuszczenia powtórzeń wśród bliźniaków czy jednak coś innego?
Pozdrawiam,
@tomash
https://images91.fotosik.pl/607/57e9430c562ab9cf.jpg
Na niebiesko przykładowe dwa lustrzane rozwiązania.
@xswedc
Dzięki – widzę też, że np. drugie ma powtórzonego bliźniaka (139) – więc pewnie dlatego jest 118 krzyżówek 🙂
Pozdrawiam,
@tomash
Zgadza się, drobny błąd w indeksach zmiennych spowodował, że w ostatnich wierszu i kolumnie mogły pojawić się te same liczby. Po poprawce uzyskałem również 72 rozwiązania.
„Elementarna wersja dowodu zaczyna się od zauważenia, że z trzech kolejnych liczb naturalnych przynajmniej jedna musi być podzielna przez 2 i dokładnie jedna przez 3”.
Nie zgadzam się. Do elementarnej wersji dowodu wystarczy podzielność przez 3. Parzystość jest oczywista, ale do dowodu zbędna.
Od biedy racja, tylko że wtedy dla pary bliźniaków otrzymuje się wzory 3n-1 i 3n+1, a to nie jest prawda.
mp
@tomash
Najszybszy z algorytmów, który zdarza mi się stosować, to backtracking (https://en.wikipedia.org/wiki/Backtracking).
Jest idealny do takich zadań, jak w łamiblogu z 23 lipca, gdzie trzeba znaleźć JEDNO rozwiązanie osobliwego, nietypowego sudoku. Tak prawdę mówiąc, to w lipcowym numerze Świata Nauki są 2 zadania, na które backtracking jest idealnym orężem (pierwsze i trzecie). Nie ma bowiem szans, aby tak złożone zadanie rozwiązać tradycyjnymi pętlami.
Backtracking jest niezwykle szybki, bo porzuca niepoprawne rozwiązania od razu, gdy tylko wiadomo, że one nie zadziałają – podobnie jak człowiek. Ale ma wady: znajduje tylko pierwsze rozwiązanie (no chyba że ręcznie je wykluczysz w warunkach), jest tam rekurencja, a to trochę utrudnia szukanie błędów, a poza tym jakoś zawsze długo mi schodzi, zanim poprawnie napiszę taki skrypt. Jest to zapewne jednak wyłącznie kwestia wprawy.
@mp
W dowodzie do poprzedniego zadania (Ośmioraczki) pokazałem, że liczby bliźniacze muszą mieć postać 6n+5 i 6n+7 dla n>=0 (lub 6n-1 i 6n+1 dla n>=1). Więc nie jest potrzebne dodatkowe założenie o parzystości.
Ależ prawda, właśnie tak, dla pary bliźniaków otrzymuje się 3n-1 i 3n+1, wszak wszystkie bliźniaki (oprócz 3 i 5) takie właśnie są: różnią się plus/minus 1 od liczby podzielnej przez 3. Oczywiście mnóstwo par liczb złożonych także różni się plus/minus 1 od liczby podzielnej przez 3, bliźniaki są tylko ich podzbiorem.
Ale co miałoby dać użycie 6 zamiast 3? Z 6 jest identycznie: mnóstwo par liczb złożonych różni się plus/minus 1 od liczby podzielnej przez 6, bliźniaki są tylko ich podzbiorem.
Oczywiście,z tą nieprawdą trochę „przegiąłem pałkę”.
mp
Trochę się tam poprzejęzyczałam, ale wiadomo, o co mi chodziło 🙂
Wiadomo, że bliźniaki nie są podzbiorem liczb złożonych, tylko podzbiorem wszystkich par liczb różniących się plus/minus 1 od 3 bądź od 6.
@OlaGM
„Ale co miałoby dać użycie 6 zamiast 3”?
Napisałem wcześniej dowód (no, może szkic dowodu), że wszystkie liczby bliźniacze (za wyjątkiem 3 i 5 – tu wskazałem przyczynę) muszą być w postaci 6n-1 i 6n +1 dla n>=1 (alternatywnie, co jest bardziej logiczne w tym dowodzie 6n+5 i 6n +7 dla n>=0). Nie była tam używana cecha podzielności przez 2, więc zastosowanie 6 zamiast 3 jest poprawne. Dziwne wydaje się, że nikt (w tym Pani oraz Gospodarz) tego nie przeczytał i dyskusja toczy się nadal wokół wzorów 3n-1 i 3n +1…
Ja przeczytałem, uznałem za słuszne i dyskusja chyba dobiegła końca. Formy 6n-1 i 6n+1 preferuję, bo są one standardowymi w przypadku liczb bliźniaczych, ale 3n-1 i 3n+1 także w tym przypadku pasują. Oto przykład zgody polsko-polskiej 🙂
mp