Delta mi!

Odpowiedź: nie.
Banalny kontrprzykład (jeden z wielu): ciąg Ciąg Fibonacciego - a raczej jego początkowy odcinek - zapisany modulo przedstawia się tak: Dalej reszty (mod ) powtarzają się cyklicznie, z okresem ; reszta jest w tym ciągu nieobecna.

Ponieważ to iloczyn wszystkich wyrazów ciągu nie zmienia się po wykonaniu ruchu. W szczególności każdy z wyrazów ciągu jest ograniczony z góry przez i ograniczony z dołu przez Ponadto w każdym ruchu, modyfikującym pewne wyrazy o indeksach liczba jest zamieniana na większą liczba zaś - na mniejszą Żaden wyraz ciągu nie może być nieskończenie wiele razy zmniejszany (jako ograniczony z dołu przez ) ani zwiększany (jako ograniczony z góry przez ). W takim razie każdy wyraz zostanie zmieniony skończenie wiele razy, czyli nie możemy wykonać nieskończenie wielu ruchów.

Istnieją takie ciągi. Jedna z możliwych konstrukcji:

Przyjmujemy Będziemy przedłużać zdefiniowany odcinek ciągu, dołączając po dwa wyrazy.

Ustalmy liczbę parzystą i przyjmijmy, że wyrazy są już określone. Najmniejsza dodatnia liczba całkowita, różna od będzie wyrazem (to gwarantuje, że w budowanym ciągu znajdą się wszystkie liczby całkowite dodatnie).

Określamy wyraz wzorem

gdzie jest liczbą całkowitą tak dobraną, by uzyskana liczba była dodatnia oraz różna od liczb i różna od (powstający ciąg będzie więc miał wszystkie wyrazy różne). Przy tym

Wymagane warunki podzielności są spełnione. Indukcyjnie powstaje ciąg nieskończony jakiego szukamy.

Będziemy korzystać - podobnie, jak w rozwiązaniach zadań 654 i 662 (Delta 5/2013, 9/2013) - z twierdzenia Stolza, które mówi, że jeśli jest ciągiem rosnącym do nieskończoności, wówczas równość

(1)

zachodzi dla każdego ciągu dla którego granica po prawej stronie istnieje. Ponieważ rosnąco, twierdzenie ma szanse zadziałać - warto zająć się ciągiem o wyrazach gdzie

Jeśli wykażemy, że wzór (1) (dla ) da wynik i zakończy rozwiązanie.

Ponownie użyjemy twierdzenia (1) (dla ); ciąg jest rosnący, więc rosnąco. Chcemy dowieść, że liczba 1 jest granicą ciągu o wyrazach

Wszystkie liczby są większe od 1 (oczywista indukcja); ich logarytmy są dodatnie, wobec czego ciąg jest rosnący - ma zatem granicę (skończoną lub nie). Granica skończona musiałaby być liczbą spełniającą równanie co nie jest możliwe. Tak więc ; co za tym idzie, Korzystając ze znanej relacji granicznej możemy teraz napisać

gdzie i przepisać wyrażenie (2) w postaci

(3)

Z nieco bardziej subtelnej relacji granicznej (przy ) możemy wywnioskować, że

a stąd Zatem cały pierwszy czynnik iloczynu po prawej stronie wzoru (3) dąży do 1. Pozostaje dowieść, że drugi czynnik też - czyli że

(4)

Jeszcze raz skorzystamy ze wzoru Stolza (1), tym razem biorąc Granica po lewej stronie (4) będzie równa granicy jeśli ta ostatnia istnieje. Skoro

zatem

(bo ). To dowodzi słuszności tezy (4), więc i tezy zadania.

Liczby, dla których najbliższym kwadratem jest mają postać

(1)

Suma wartości dla tych liczb wynosi Stąd

Dla liczb postaci (1) obliczamy:

Aby ujednolicić zapis, wprowadzamy parametr i wyznaczamy (dla w formie (1)):

(2)

Interesują nas wartości całkowite uzyskanego wyrażenia. Przekształcamy je do postaci

(3)

Dla oraz wychodzą wartości niecałkowite - można je zignorować, ograniczając zakres parametru do Wówczas

Różnica (2) jest więc liczbą całkowitą (równą ) wtedy i tylko wtedy, gdy zaś Gdy ostatni warunek jest spełniony dla trzech par mianowicie

Wniosek: dowolna liczba całkowita jest wartością wyrażenia jedynie dla gdzie zaś jest jedną z trzech powyższych par - czyli, po podstawieniu, dla

Oznaczmy Liczby są całkowite i większe od 1, czyli większe lub równe 2. Zatem

Z rekurencyjnego określenia ciągu wynika, że

Stąd

A skoro widzimy, że przy Jest to suma szeregu ; i oczywiście jest to liczba wymierna.

Mamy Oczywiście, dla każdego zachodzi a więc również W takim razie dla mamy

Z drugiej nierówności możemy przez łatwy dowód indukcyjny wyprowadzić własność dla Wówczas jednak pierwsza nierówność daje oszacowanie

Wartość jest osiągana przez dla ciągu określonego przez warunek dla Faktycznie wówczas

dla oraz

więc ciąg ten spełnia warunki zadania.

Zauważmy, że

gdzie w ostatniej nierówności skorzystaliśmy z tego, że ciągi  są malejące.

Takie ciągi istnieją. Oto jedna z możliwych konstrukcji. Zaczynamy od liczb  Przyjmijmy, że wyrazy  są już określone i tworzą ciąg rosnący długości  spełniający wymagany warunek. Oznaczmy dla wygody:  Określamy kolejne trzy wyrazy:

Jasne, że  Pozostaje sprawdzić, że iloczyn trzech wypisanych liczb, równy  dzieli się przez każdą z tych liczb, powiększoną o 1, czyli przez liczby ; a to jest oczywiste. Kontynuując, otrzymujemy nieskończony ciąg  o żądanych własnościach.

Jak w rozwiązaniu zadania 654, tak i teraz użyjemy wzoru Stolza:

dla każdego ciągu  rosnącego do nieskończoności, i dla każdego ciągu  dla którego granica po prawej stronie istnieje.

Dany w zadaniu iloraz piszemy w postaci

(1)

Zgodnie z wynikiem zadania 654, ; pozostaje zająć się drugim czynnikiem. We wzorze Stolza przyjmijmy :

(2)

jeśli tylko ta ostatnia granica istnieje.

W rozwiązaniu zadania 654 zostało użyte przekształcenie

oraz fragment rozwinięcia potęgowego

Zatem

W tym ostatnim iloczynie pierwszy czynnik dąży do (nieco dłuższy fragment rozwinięcia ). Drugi czynnik: licznik dąży do 4, mianownik do 1. Cały iloczyn dąży do  Tyle więc wynosi granica napisana po lewej stronie równości (2). Wracamy do równości (1), pamiętając, że  i otrzymujemy ostatecznie

Wszystkie wyrazy  są liczbami dodatnimi. Z nierówności (dla ) wynika, że ciąg  jest malejący – zatem zbieżny do granicy  Równanie  daje w granicy zależność  która nie zachodzi dla żadnej liczby dodatniej (w myśl tej samej nierówności). Zatem

Zastosujemy twierdzenie Stolza. Mówi ono, że jeśli  jest ciągiem rosnącym do nieskończoności, to

dla każdego ciągu  dla którego granica po prawej stronie istnieje.

Biorąc  mamy w mianowniku wyrażenia po prawej stronie jedynkę, a w liczniku:

Gdy (więc ), ten iloraz dąży do  widać to na przykład z początkowego fragmentu rozwinięcia potęgowego (przy ). Tak więc

czyli

Mamy dowieść, że  Dla  to prawda . Dalej przyjmujemy  Korzystamy ze wzoru  gdzie  Oznaczmy:

Wystarczy pokazać, że  czyli  A ponieważ  wystarczy dowieść, że

(1)

Iloraz w nawiasie szacujemy z dołu:

Stąd i z nierówności Bernoulliego

Nierówność (1) będzie udowodniona, jeśli wykażemy, że licznik tego ostatniego ilorazu przekracza  jest to równoważne nierówności

(2)

Podstawiając wartość stałej  sprawdzamy, że nierówność (2) zachodzi dla  Zachodzi więc dla wszystkich  bo wyrażenie po lewej stronie (2) przedstawia ciąg rosnący. To kończy dowód.

Liczby wewnątrz kwadratów oznaczają długości ich boków.

Pewną liczbę kwadratów o bokach równych początkowym wyrazom ciągu Fibonacciego ustawmy jak na rysunku , po kolei dobudowując kwadraty na przemian po prawej stronie i na dole. Na każdym etapie tej konstrukcji powstaje prostokąt, bo   – następny kwadrat „pasuje” do dwóch poprzednich.

(a)

Jeśli ostatni kwadrat dobudowano na dole i ma on bok długości  to cały prostokąt ma taką właśnie szerokość, a wysokość równą następnemu wyrazowi ciągu, czyli  Jednocześnie wysokość ta jest równa

(b)

Analogicznie, jeśli ostatni kwadrat ustawiono po prawej i ma bok długości  to prostokąt ma szerokość równą  i zarazem równą

(c)

Jeśli jako ostatni ustawiono kwadrat o boku długości  to prostokąt ma taką właśnie szerokość lub wysokość, a drugi z wymiarów równy  więc ma pole  Jednocześnie pole to jest równe

Cięcie chodnika długości n + k - 1 na części o długościach n oraz k - 1.

Ile spośród chodników o długości  takich jak opisano w poprzednim zadaniu, można rozciąć na chodnik o długości  (od lewej strony) oraz chodnik o długości  (po prawej stronie) bez rozcinania poszczególnych płyt (Rys. (a))? Takich chodników jest tyle, na ile sposobów można ułożyć po lewej stronie chodnik długości  a po prawej chodnik długości   Z poprzedniego zadania wiemy, że możliwości tych jest po lewej  po prawej  więc łącznie  Cięcie chodnika wymaga rozcinania płyty, gdy w miejscu podziału leży płyta  (Rys. (b)).

Takich chodników jest : układamy od lewej kolejno chodnik długości  następnie płytę  a po prawej chodnik długości   Wszystkich chodników, jak wiemy z poprzedniego zadania, jest  i każdy z nich da się rozciąć w opisany sposób lub nie, stąd

Niech  oznacza sumę po lewej stronie zależności, podanej na początku zadania, zaś  – ułamek po prawej stronie. Dla  mamy  zatem równość  wymusza wartość  Dalej,

Widać więc, że podana zależność jest spełniona dla wszystkich  wtedy i tylko wtedy, gdy

(1)

Jeżeli ciąg  spełniający ten warunek, miałby również spełniać rekurencję typu

(2)

(z   ), to dla  mielibyśmy

Pierwsza para równości to układ równań liniowych (z niewiadomymi  ) o wyznaczniku  więc mający dokładnie jedno rozwiązanie. Przy tym jest on spełniony dla  (co łatwo stwierdzić, korzystając z drugiej pary równości). Stąd wniosek, że jedynym kandydatem na postulowaną zależność rekurencyjną jest równanie

(3)

z warunkiem początkowym  Wprowadźmy oznaczenia:

i zauważmy, że (dla  )

skąd przez odjęcie stronami

(4)

Ponadto (wobec  ) mamy:

Wnioski: Jeżeli ciąg liczb całkowitych dodatnich  spełnia wyjściową zależność, czyli warunki (1), to dla wszystkich  mamy  więc prawa strona (4) ma stale wartość 0; przy tym  i ze wzoru (4) wynika, że  dla wszystkich  – mamy zależność (3).

Na odwrót, jeśli równanie (3) (z wyrazem początkowym  oraz dowolnym  ) jest dla wszystkich  spełnione, czyli wszystkie  są zerami, to wobec (4):  dla  przy tym  zatem  – a to jest zależność (1).

Ostatecznie więc, zadana na wstępie zależność jest równoważna rekurencji liniowej (2) z parametrami  – dowolna liczba naturalna.

Załóżmy nie wprost, że wielomian  o współczynnikach całkowitych ma cykl  długości  Mamy  Kluczowa będzie dla nas obserwacja, że dla dowolnych liczb całkowitych  i  zachodzi

Mamy bowiem ciąg podzielności

Wynika stąd, że

dla  (przyjmujemy, że ). Znak „–” jest wykluczony, gdyż liczby  są parami różne. Mamy więc  Oznacza to, że ciąg  jest arytmetyczny. Musi on być stały, co daje sprzeczność.

Wyrazy ciągu  są liczbami dodatnimi. Zapiszmy każdy z nich jako tangens pewnego kąta ostrego:

Wykażemy, że  Zaczynamy od oczywistej zależności

Przekształcamy mianownik ostatniego ułamka:

Po podstawieniu do poprzedniej równości otrzymujemy związek

i w konsekwencji  (obie liczby:  i   leżą w przedziale ). Tak więc  dla wszystkich ; a skoro  czyli  wnosimy stąd, że

Wystarczy teraz zauważyć, że  i skorzystać ze znanej relacji granicznej

Otrzymujemy odpowiedź:

Przyjmijmy oznaczenia:

Widać, że ;

Udowodnimy indukcyjnie dwie równości. Pierwsza z nich:

(1)

Dla  zgadza się. Przyjmijmy jej słuszność dla  Wtedy dla  mamy

stąd słuszność (1) dla wszystkich  Teraz druga z zapowiedzianych równości:

(2)

Znów, dla  zgadza się. Weźmy  i załóżmy, że równość analogiczna do (2) zachodzi dla :

Z określenia ciągu  wynika, że  Stąd oraz z (1):

co kończy dowód indukcyjny zależności (2).

Przepisujemy tę zależność w postaci

Liczba  jest dodatnia, więc iloraz w nawiasie jest liczbą o module mniejszym od 1. Wobec tego  Stąd, ostatecznie,