Rękopis
Zafrasowałem się okrutnie takim oto fragmentem komentarza apsa:
…niektóre zadania z weekendowych dodatków do GW trzeba przyznać są trudne i trzeba się uciec do pomocy komputera, np. to bardzo skądinąd ciekawe z rękopisem i sumami częściowymi ciągów.
Zgoda, że trafiają się trudniejsze zadania, ale czy rzeczywiście aż tak, aby nie dało się ich rozgryźć bez komputera i czy takim jest to, o którym wspomina aps? Przypomnę je:
Rękopis poematu liczy X (5<X<100) ponumerowanych stron i podzielony jest na dwie części. Suma numerów stron pierwszej części równa jest sumie numerów stron drugiej. Ile równa się X?
Właściwie sedno sprawy sprowadza się do zauważenia, że trzeba liczyć sumy wyrazów ciągu liczb naturalnych. A ściślej, chodzi o znalezienie dwu sum wyrazów tego ciągu – od 1 do X i od 1 do Y (5<Y<X<100) – takich, z których jedna jest dwukrotnie większa od drugiej. Wzór, który można napisać, jest istotnie mało sympatyczny i niezbyt obiecujący. Łatwo, szybko i schematycznie dochodzi się jednak do rozwiązania, wypisując kolejne sumy, czyli tworząc tzw. ciąg liczb trójkątnych:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105…
dotąd, aż wyskoczy suma dwukrotnie większa od jakiejś sumy, która pojawiła się wcześniej. Droga jest niedługa, bo dwudziesty wyraz (210) okazuje się podwojeniem czternastego. Trudne?
Komputer przydałby się natomiast do znalezienia rozwiązania dla najmniejszego i każdego kolejnego X>100.
A gdyby rękopis poematu podzielono na trzy części i suma numerów stron każdej części byłaby taka sama, to ile liczyłby on wówczas stron? Obawiam się, że w tym przypadku nawet komputer okaże się bezradny.
Komentarze
Żadnych rozwiązań dla rękopisów poniżej 500 milionów stron – o ile oczywiście nie popełniłem gdzieś błędu.
Zresztą bardzo prawdopodobne, że rozwiązania w ogóle nie ma, jak to bywa z równaniami diofantycznymi.
„…w tym przypadku nawet komputer okaże się bezradny.”
Chciałbym zauważyć, że zaprogramowanie komputera tak, aby znalazł rozwiązanie podanego zadania jest stosunkowo proste. Wystarczy zapisać kilka prostych warunków i sprawdzać kolejne wartości…
Jedyny problem polega na tym, że szukanie rozwiązania może trwać bardzo długo… być może zabraknie nam naszego życia…
Czy to jednak upoważnia nas do nazwania komputera bezradnym? On jest nieśmiertelny, fakt, że prędzej czy później się zepsuje, lecz wtedy jego pracę będzie mógł kontynuować inny komputer, potem jeszcze inny. Któryś z nich prędzej czy później znajdzie rozwiązanie.
No chyba, że rozwiązanie nie istnieje… Wtedy żaden komputer nie da rady… 😉
bezradny = niemogący sobie z czymś poradzić (w tym przypadku upersonifikowany komputer).
mp
Jeżeli poemat nie może mieć więcej niż miliard stron, to rozwiązania nie ma.
Ale narobiłem 🙂 Było tak, że zadanie postanowiłem sobie rozwiązać, jak to się mówi, do poduszki, i też wpadłem na to, by sprawdzać kolejne sumy, ale jak sobie pomyślałem, że być może przyjdzie sprawdzać aż do 100, a numerki zaczynały tańczyć przed oczami, to może można zrobić to jakoś inaczej. Napisałem równanie z dwiema niewiadomymi i w pewnym momencie pomyślałem nawet, że „to nie może być”, próbowałem więc udowodnić, iż nie będzie takich liczb, co oczywiście się nie udało. Następnego dnia użyłem „komputera” w sensie, tu chyba byłem nieprecyzyjny, popularnego arkusza kalkulacyjnego, de facto więc byłaby to wspomagana metoda rozwiązania Pana Redaktora (acz trochę inaczej, o czym jeszcze napiszę). „Trudność” moim zdaniem polegała więc na tym, że trzeba dość żmudnie sprawdzić kilkanaście przypadków, a wcześniej nastawić się na kilkadziesiąt (i w każdym kolejnym będzie więcej sprawdzania), co nie w każdych warunkach jest łatwe. I to nawet nie z przysłowiową kartką i długopisem, tylko, ze wstydem przyznam, z dodatkiem do GW i długopisem, mam nieładny zwyczaj pisania na marginesach i tam gdzie jest miejsce – zbyt ograniczone jak na to zadanie. A może to co napisałem wynika też z intuicyjnego przekonania, że stopień trudności i żmudności rozwiązania zadania powinien się zmniejszać w kolejności Łamiblog – Omnibus – Na Pamięć, odwrotnie proporcjonalnie do liczby osób, które mają kontakt z zadaniem? Może gdyby jako górną granicę liczby stron podać nie 100, a powiedzmy 25, czy nawet 30, „efekt zniechęcający” do sprawdzania na piechotę byłby mniejszy? To oczywiście moje zupełnie jednostkowe refleksje, i mój problem, którego być może nie mieli inni, bardzo proszę więc z tego nie wyciągać daleko idących wniosków, zadania są Bardzo Dobre 🙂
Bardzo dobrze apsie (apsiku:)) narobiłeś, bo był temat do popisania.
Nawiasem mówiąc, nie brak osób, które uważają, że większość zadań matematycznych w „Na pamięć” to Himalaje – i trudno z tym dyskutować, bo trzeba by użyć mało merytorycznych i niezbyt sympatycznych argumentów.
mp
Przy pomocy excela znalazłem trzy kolejne rozwiązania:
1-84; 85-119 (sumy obu części to 3570)
1-492; 493-696 (sumy to 121278)
1-2870; 2871-4059 (sumy to 4119885)
więcej sum zakładając wielkość poematu <=10000 stron nie znalazłem.
Co do podziału na trzy części nie udało się znaleźć żadnego rozwiązania aż do wielkości poematu 100000 stron. Z dalszych poszukiwań zrezygnowałem.
Metodologia: Podzielenie każdej kolejnej liczby trójkątnej przez 3 a następnie jeśli iloraz jest liczbą całkowitą to odszukanie jej we wcześniejszych wyrazach ciągu liczb trójkątnych. W momencie odnalezienia liczby sprawdzenie, czy jej dwukrotność również jest liczbą trójkątną. Stutysięczna liczba trójkątna to 5000050000. Ręczne liczenie zatem absolutnie odpada.
Gdy x=119 to wtedy I-część to strony od 1÷84 (suma 7140) II-część to 85÷119 (ta sama suma 7140) wystarczył zwykły kalkulator, ołówek i kartka papieru …
Niech S(n) = 1 + 2 + … + n
Szukamy rozwiązań, w których rękopis da się podzielić na dwie części, tak aby pierwsza zawierała a_n stron, a cały rękopis b_n stron. Oczywiście w takim układzie S(b_n) = 2 * S(a_n).
Komputer znalazł początkowe wyrazy ciągów:
a_n = 2, 14, 84, 492, 2870, …
b_n = 3, 20, 119, 696, 4095, …
Znalazł więcej wyrazów, na podstawie których udało mi się wywnioskować poniższą zależność rekurencyjną:
a_n = 6 * a_(n-1) – a_(n-2) + 2
Identyczna zależność zachodzi w ciągu b_n.
Kolejny program komputerowy sprawdził, że dla wielu początkowych wyrazów ciągu rzeczywiście zachodzi związek S(b_n) = 2 * S(a_n).
Prawdopodobnie udałoby się udowodnić ten fakt formalnie (czego nie robiłem).
Podobnie postąpiłem z problemem podziału rękopisu na dwie części, z których pierwsza ma dwukrotnie mniejszą sumę stron niż druga, tzn. jeżeli c oznacza liczbę stron pierwszej części, a d liczbę stron całego rękopisu, to S(d) = 3 * S(c).
Na tej podstawie definiujemy ciągi c_n i d_n, o początkowych wyrazach:
c_n = 1, 5, 20, 76, 285, 1065, …
d_n = 2, 9, 35, 132, 494, 1845, …
I podobnie zauważamy zależność rekurencyjną:
c_n = 4 * c_(n-1) – c_(n-2) + 1
Co dalej? Chcemy odpowiedzieć na pytanie, czy przy tak zdefiniowanych ciągach, dla pewnych indeksów i, j, zachodzi a_i = c_j?
Jeśli tak, to w rękopisie zawierającym d_j stron, pierwsze a_i mają taką samą sumę, jak strony od a_i+1 do b_i, oraz taką samą sumę jak strony od b_i+1 do d_j
Kolejny program generuje kolejne wartości ciągów a_n oraz c_n i szuka elementu występującego w obu tych ciągach. Obecnie udało się przeanalizować wszystkie wyrazy ciągów składające się z liczb maksymalnie 320000 cyfrowych – rozwiązania jeszcze się nie pojawiły. Ciekawe, czy w ogóle się pojawią, a jeśli tak, to czy nastąpi to zanim zwątpię i nie przerwę działania programu 😀
Dla zadania dotyczącego podziału rękopisu na dwie części, dla X<10^9, komputer w rozsądnym czasie znalazł takie wartości:
[liczba stron rękopisu (suma numerów), liczba stron pierwszej części (suma numerów jednej części)]:
3 (6), 2 (3)
20 (210), 14 (105)
119 (7140), 84 (3570)
696 (242556), 492 (121278)
4059 (8239770), 2870 (4119885)
23660 (279909630), 16730 (139954815)
137903 (9508687656), 97512 (4754343828)
803760 (323015470680), 568344 (161507735340)
4684659 (10973017315470), 3312554 (5486508657735)
27304196 (372759573255306), 19306982 (186379786627653)
159140519 (12662852473364940), 112529340 (6331426236682470)
927538920 (430164224521152660), 655869060 (215082112260576330)
Okazało się, że na https://oeis.org/A001652 można znaleźć ten ciąg. Jeden z kilku jego opisów mówi, że to liczba rozwiązań naturalnych równania a(a+1)=2b(b+1), czyli też a(a+1)/2=2*b(b+1)/2, co pasuje do naszego problemu.
Jeśli chodzi o rozwiązanie dla rękopisu podzielonego na 3,4 lub 5 części, to w badanym zakresie nie ma rozwiązania.
Następne w miarę sensowne ilości stron rękopisu to:
119 (1+..84, 85+..+119)
696 (492)
4059 (2870)
Kolejne, które raczej nie pasują
23660, 137903, 803760, 4684659, 27304196, 159140519, 927538920, 5406093003, 31509019100 itd.
Zadanie programistyczne raczej banalne. Na wyniki do jakiejś założonej granicy np 40000000000 nie trzeba czekać zbyt długo. Sprawdzany jest tylko tylko jeden warunek, czy liczba trójkątna B=A*2 jest liczbą trójkątna. Ten warunek wygląda tak (1+8*B)^(1/2). A=105, B=210 dla przypadku z wpisu.
Ale zamiast tych wszystkich kombinacji należy zajrzeć do OEIS i tam znaleźć ciąg
A001652 o wyrazie ogólnym a(n) = 6*a(n-1) – a(n-2) + 2 dla a(0) = 0, a(1) = 3.
Można łatwo udowodnić, że równanie m(m+1) = 2n(n+1) ma nieskończenie wiele rozwiązań w liczbach naturalnych. Jest ono równoważne r-u
[D(2n+1) – (2m+1)][D(2n+1) + (2m+1)] = 1
gdzie D = sqrt(2).
Teraz patrzymy w wiki na hasło równanie Pella. W analogiczny sposób dowodzimy, że mając jakieś rozwiązanie (n,m), np. n = 2, m=3, inne rozwiązania otrzymujemy, rozwiązując trywialne równanie
D(2n’+1) + (2m’+1) = [D(2n+1) + (2m+1)]^k, gdzie k jest nieparzyste, k=3,5,7…
Dla n=2, m=3, k=3 mamy
D(2n’+1) + (2m’+1) = [5D+7]^3, skąd n’=492 i m’ = 696.
Sprawdzamy: 492*493 = 242556, 696*697=485112 = 2*242556, zgadza się.
Dla k=5 mamy n’=97512, m’=137903.
Dla k=7 mamy n’=19306982, m’=27304196
Dla k=51 szalejemy w maximie i otrzymujemy n’=6487910758929628328468776595770934305612354458258501762372, m’=9175291386744600366963785564232332871431908791334263227496.
Komputer znajduje następujące rozwiązania, wszystkie wśród liczb mniejszych od miliarda:
2 -> 3 3 -> 6
14 -> 105 20 -> 210
84 -> 3570 119 -> 7140
492 -> 121278 696 -> 242556
2870 -> 4119885 4059 -> 8239770
16730 -> 139954815 23660 -> 279909630
97512 -> 4754343828 137903 -> 9508687656
568344 -> 161507735340 803760 -> 323015470680
3312554 -> 5486508657735 4684659 -> 10973017315470
19306982 -> 186379786627653 27304196 -> 372759573255306
112529340 -> 6331426236682470 159140519 -> 12662852473364940
655869060 -> 215082112260576330 927538920 -> 430164224521152660
Powyższa metoda algebraiczna nie generuje więc wszystkich rozwiązań, choć wydaje się, że generuje co trzecie. Nie sprawdzałem, ale prawdopodobnie wszystkie rozwiązania „komputerowe” da się wygenerować z trzech pierwszych.
W analogiczny sposób można podejść do równania m(m+1) = 3n(n+1). Na pewno da się znaleźć kilka „generatorów” i szybko wygenerować ciągi rozwiązań, najlepiej w jakimś pakiecie do teorii liczb. Jeżeli gdzieś znajdzie się rozwiązanie pokrywające się z rozwiązaniem problemu m(m+1) = 2n(n+1), jesteśmy w domu. Niestety, nie mam czasu na taką zabawę.
Dla ułatwienia, dla trójki [m(m+1) = 3n(n+1)] komputer generuje następujące rozwiązania mniejsze od miliarda:
1 -> 1 2 -> 3
5 -> 15 9 -> 45
20 -> 210 35 -> 630
76 -> 2926 132 -> 8778
285 -> 40755 494 -> 122265
1065 -> 567645 1845 -> 1702935
3976 -> 7906276 6887 -> 23718828
14840 -> 110120220 25704 -> 330360660
55385 -> 1533776805 95930 -> 4601330415
206701 -> 21362755051 358017 -> 64088265153
771420 -> 297544793910 1336139 -> 892634381730
2878980 -> 4144264359690 4986540 -> 12432793079070
10744501 -> 57722156241751 18610022 -> 173166468725253
40099025 -> 803965923024825 69453549 -> 2411897769074475
149651600 -> 11197800766105800 259204175 -> 33593402298317400
558507376 -> 155965244802456376 967363152 -> 467895734407369128
Ciekawe, jak system zarządzania blogiem sformatuje ten wpis.
The path is clear
Though no eyes can see
The course laid down long before.
Tak na marginesie – internet jest niesamowity. O równaniach Diofantycznych słyszałem ostatnio może na fakultecie w liceum, może przeczytałem o nich w „Delcie”, którą wówczas można było kupić w zwykłym kiosku. Zajrzałem wiec w Wiki do hasła „równania Diofantyczne”, stamtąd wszedłem na równanie Pella, o którym nigdy wcześniej nie słyszałem, potem niecałe 2 godziny i w zasadzie
posprzątane. Bez internetu i wolnego dostępu do informacji – rzecz nie do pomyślenia.
🙂 Jeszcze tylko dodam, jak znalazłem w końcu kilka pierwszych rozwiązań na (pół)-piechotę: otóż postanowiłem rozwiązać równanie n(n+1)=2k(k+1) np. ze względu na n, wychodzi równanie kwadratowe, i mamy deltę równą 1+8k(k+1). Teraz można szybko sprawdzić w excelu, dla których k pierwiastek z delty jest liczbą całkowitą, i właściwie tyle, znalezienie n dla k jest już proste, a jeszcze lepiej rozwiązywać ze względu na k, bo w delcie będzie n, i wyjdzie od razu. Podobne delty otrzymamy, jeśli dwójkę zastąpimy inną liczbą, ale właśnie jak zostało pokazane, uzgodnienie czegoś w ramach dwóch par (k,n) i drugiej gdzie n jest w roli k z jeszcze inną liczbą p (akurat tak to widziałem, nie k raz z dwójką raz z trójką, tylko (n, p) z 3/2), może się bardzo długo nie udawać. A przy tym całym rozwiązywaniu jeszcze jedną rzecz zauważyłem, której dotychczas nie byłem świadom, mianowicie: kwadrat liczby nieparzystej przy dzieleniu przez 8 zawsze daje resztę 1. Dowód jest prosty.
Mój program ciągle szuka rozwiązań. Obecnie przeanalizował wszystkie wyrazy zdefiniowanych przeze mnie ciągów składające się z co najmniej 3800000 cyfr dziesiętnych… i nic nie znalazł.
Zostawiam program uruchomiony, może za dzień, tydzień, miesiąc, …(*) coś znajdzie.
(*) – niepotrzebne skreślić / wpisać własne ograniczenie czasowe 😉
Podejrzewam, ze jakiś teoretyk liczb już się tym „bawił”. Może nawet udowodnił, że rozwiązań nie ma. Problem tylko w tym, jak do efektów tej zabawy dotrzeć.
mp
dla 3n(n+1) = 2m(m+1)
komputer znalazł
0 -> 0 0 -> 0
4 -> 10 5 -> 30
44 -> 990 54 -> 2970
440 -> 97020 539 -> 291060
4360 -> 9506980 5340 -> 28520940
43164 -> 931587030 52865 -> 2794761090
427284 -> 91286021970 523314 -> 273858065910
4229680 -> 8945098566040 5180279 -> 26835295698120
41869520 -> 876528373449960 51279480 -> 2629585120349880
414465524 -> 85890835499530050 507614525 -> 257672506498590150
Łatwo wykazać, że m i n dzielą się przez 5 lub dają resztę 4 przy dzieleniu przez 5,
a więc suma numerów stron książki musi być wielokrotnością 5.
To może minimalnie zawęzić krąg poszukiwań.
Można też szybko wykazać podobną właściwość dla siódemki: n(n+1)
musi dzielić się przez 7, ale trzeba wziąć wszystkie 3 równania i badać reszty.
Korzystając dodatkowo z informacji zawartych w rekurencjach
da się dowieść podzielności przez 11.
Byłoby cudownie, gdyby dało się dowieść, że w ciągach generowanych rekurencjami
występują wyłącznie liczby niepodzielne przez jakąś pierwszą liczbę p, można by się tego
uchwycić do dowodu braku rozwiązań.
Niestety, wygląda na to, że jeżeli takie p istnieje, to p > 11.
Metoda r-a Pella dla powyższego równania zdaje się nie działać.
A105038 i A200993.
Można przypuszczać, że gdyby istniało rozwiązanie dla 3-częściowego rękopisu, to przy tych ciągach byłaby wzmianka na ten temat.
mp
takiej liczby p, o której przed chwilą pisałem, nie ma, bo n=0 jest rozwiązaniem a ciągi reszt z ciągów rekurencyjnych są cykliczne. Można więc pewnie wykazać podzielność n(n+1) przez kilka innych MAŁYCH liczb pierwszych i to wszystko.