Rok Tri-, rok Fi-
W bodaj najsłynniejszym ciągu matematycznym – Fibonacciego, każdy wyraz (oprócz pary początkowych jedynek) jest sumą dwu poprzednich wyrazów:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,…
Jego mniej znany kuzyn, ciąg Tribonacciego, do trzeciego wyrazu wygląda tak samo, a dalej każdy wyraz jest sumą trzech poprzednich:
1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705,…
(jak widać preferuję dawny zapis bez zer na początku, które wskoczyły do ciągów – moim zdaniem niepotrzebnie – w latach 70.).
Stosunek dwu kolejnych wyrazów ciągu Fibonacciego – F(n+1)/F(n) – zmierza, wraz ze wzrostem n, do tzw. złotej liczby fi, która jest podstawą złotego podziału.
fi = (1+sqrt5)/2 = 1,61803…
Liczba fi jest także pierwiastkiem wielomianu x^2 – x – 1. Jeśli wielomian ten potraktować jako wzór na ciąg: a(n) = n^2 – n – 1, to dla n = 1, 2, 3… powstanie ciąg wielomianowy Fibonacciego:
-1, 1, 5, 11, 19, 29, 41, 55, 71, 89, 109, 131, 155, 181, 209,…
Analogicznie stosunek dwu kolejnych wyrazów ciągu Tribonacciego zmierza do stałej Tribonacciego równej 1,83929…, która jest też pierwiastkiem wielomianu x^3 – x^2 – x – 1.
Ciąg wielomianowy Tribonacciego rośnie oczywiście znacznie szybciej niż odpowiedni ciąg Fibonacciego, a jego trzynastym wyrazem jest – FANFARY!!! – 2014, czyli:
13^3 – 13^2 – 13^1 – 13^0 = 2014
W klasycznych ciągach Fibonacciego i Tribonacciego liczba 2014 nie pojawia się, ale w „wariacjach na temat” i owszem. Wariacje polegają w przypadku ciągu Fibonacciego na zadaniu dowolnej pary wyrazów początkowych. Chodzi przy tym o wybór takiej pary, aby 2014 pojawiło się jak najpóźniej. Trywialnym wariantem jest ciąg, w którym bieżący rok występuje natychmiast, np. 1, 2013, 2014,… Można jednak ulokować go znacznie lepiej – na dziesiątym miejscu: 2, 58, 60, 118, 178, 296, 474, 770, 1244, 2014,… Ale może być jeszcze lepiej, czyli dalej – jakimi dwoma liczbami (całkowitymi, dodatnimi) będzie się wówczas zaczynał ciąg?
Komentarze
Zacznijmy od prostej obserwacji, dzięki której możemy bez większych problemów wydłużyć podany ciąg.
Wystarczy zacząć od wartości 56 i 2, dalej otrzymamy 58 i resztę wartości, które pojawiają się w zaproponowanym rozwiązaniu.
Uzyskujemy ciąg składający się z 11 wyrazów, ale da się jeszcze lepiej 😉
Niech F(n) będzie klasycznym ciągiem Fibonacciego, tzn. F(1)=1, F(2)=1, F(3)=2, F(4)=3, itd.
Szukany ciąg określmy jako f(1)=a, f(2)=b, f(3)=a+b, …, f(k-1)=x, f(k)=2014, dla pewnych dodatnich liczb całkowitych a i b.
Powyższy ciąg jest rosnący (być może z wyjątkiem pierwszych dwóch wyrazów), zatem 0 < x 0 i g(2n+1)>0
lub
g(2n+1)>0 i g(2n+2)>0
Pierwszy przypadek daje nam nierówności:
F(2n-1)*x > F(2n-2)*2014
F(2n-1)*2014 > F(2n)*x
czyli:
2014 * F(2n-2)/F(2n-1) < x F(2n)*x
F(2n+1)*x > F(2n)*2014
czyli:
2014 * F(2n)/F(2n+1) < x < 2014 * F(2n-1)/F(2n)
W obu przypadkach wartość x znajduje się pomiędzy liczbami postaci
x1 = 2014 * F(n-2)/F(n-1)
oraz
x2 = 2014 * F(n-1)/F(n)
Liczymy kolejno wartości x1 i x2 dla kolejnych wartości n i szukamy takiej pary, dla której części całkowite liczb x1 i x2 różnią się.
Oczywiście wraz ze wzrostem n, wartości x1 i x2 zbiegają do wartości 2014/fi, która w przybliżeniu wynosi 1244,720…
Zatem, gdy wartości x1 i x2 zbliżą się dostatecznie do tej granicy, to możemy przerwać obliczenia.
Tu z pomocą przychodzi komputer, który pomaga stwierdzić, że ostatnią parą, dla której części całkowite różnią się, są wartości dla n=11. Wtedy
x1 = 1245,018…
x2 = 1244,606…
Teraz wystarczy odtworzyć ciąg g, przyjmując x=1245. Otrzymujemy:
2014, 1245, 769, 476, 293, 183, 110, 73, 37, 36, 1, 35, -34
w którym dopiero trzynasty wyraz jest ujemny.
I oczywiście odwracając wyrazy ciągu g uzyskujemy najlepsze rozwiązanie, czyli ciąg 12-wyrazowy spełniający warunki zadania:
35, 1, 36, 37, 73, 110, 183, 293, 476, 769, 1245, 2014
Mam nadzieję, że nie pomyliłem się przy ręcznym przepisywaniu wartości ani wzorów 😉
Widzę, żę blog ma problem z poprawnym wyświetleniem mojego komentarza (usuwa formatowanie, obcina część wpisu).
Dlatego umieszczam kolejny komentarz z linkiem do pliku z pełną zawartością:
http://www.gg.pl/dysk/kQCIR2Ux9rlQkACIR2Ux5pA/rok%20tri%20rok%20fi.txt
Zacznijmy od prostej obserwacji, dzięki której możemy bez większych problemów wydłużyć podany ciąg.
Wystarczy zacząć od wartości 56 i 2, dalej otrzymamy 58 i resztę wartości, które pojawiają się w zaproponowanym rozwiązaniu.
Uzyskujemy ciąg składający się z 11 wyrazów, ale da się jeszcze lepiej 😉
Niech F(n) będzie klasycznym ciągiem Fibonacciego, tzn. F(1)=1, F(2)=1, F(3)=2, F(4)=3, itd.
Szukany ciąg określmy jako f(1)=a, f(2)=b, f(3)=a+b, …, f(k-1)=x, f(k)=2014, dla pewnych dodatnich liczb całkowitych a i b.
Powyższy ciąg jest rosnący (być może z wyjątkiem pierwszych dwóch wyrazów),
zatem 0 < x 0 i g(2n+1)>0
lub
g(2n+1)>0 i g(2n+2)>0
Pierwszy przypadek daje nam nierówności:
F(2n-1)*x > F(2n-2)*2014
F(2n-1)*2014 > F(2n)*x
czyli:
2014 * F(2n-2)/F(2n-1) < x F(2n)*x
F(2n+1)*x > F(2n)*2014
czyli:
2014 * F(2n)/F(2n+1) < x < 2014 * F(2n-1)/F(2n)
W obu przypadkach wartość x znajduje się pomiędzy liczbami postaci
x1 = 2014 * F(n-2)/F(n-1)
oraz
x2 = 2014 * F(n-1)/F(n)
Liczymy kolejno wartości x1 i x2 dla kolejnych wartości n i szukamy takiej pary, dla której części całkowite liczb x1 i x2 różnią się.
Oczywiście wraz ze wzrostem n, wartości x1 i x2 zbiegają do wartości 2014/fi, która w przybliżeniu wynosi 1244,720…
Zatem, gdy wartości x1 i x2 zbliżą się dostatecznie do tej granicy, to możemy przerwać obliczenia.
Tu z pomocą przychodzi komputer, który pomaga stwierdzić, że ostatnią parą, dla której części całkowite różnią się, są wartości dla n=11. Wtedy
x1 = 1245,018…
x2 = 1244,606…
Teraz wystarczy odtworzyć ciąg g, przyjmując x=1245. Otrzymujemy:
2014, 1245, 769, 476, 293, 183, 110, 73, 37, 36, 1, 35, -34
w którym dopiero trzynasty wyraz jest ujemny.
I oczywiście odwracając wyrazy ciągu g uzyskujemy najlepsze rozwiązanie, czyli ciąg 12-wyrazowy spełniający warunki zadania:
35, 1, 36, 37, 73, 110, 183, 293, 476, 769, 1245, 2014
Mam nadzieję, że nie pomyliłem się przy ręcznym przepisywaniu wartości ani wzorów 😉
2014 w „zmodyfikowanym” ciągu Fibonacciego może pojawić się najpóźniej na 12 miejscu. Dwa pierwsze wyrazy to 35 i 1.
Cały ciąg przedstawia się następująco:
1. 35
2. 1
3. 36
4. 37
5. 73
6. 110
7. 183
8. 293
9. 476
10. 769
11. 1245
12. 2014
Pozdrawiam 🙂
Jestem ciekawy, jakimi sposobami rozwiążą to zadanie pozostali łamiblogobywalcy. Mnie się udało, że się tak wyrażę, analitycznie.
1,36,37,73,110,183,293,476,769,1245,2014
Nie najlepiej, ale jednak prawie, prawie…, więc nie ujawniam od razu.
mp
56, 2, …
Dla złotego podziału zaokrągliłem przedostatni wyraz (przed 2014) do 1245 co dało 11 pozycje zaczynając od 1,36,….
Ale jeśli ciąg nie musi być rosnący, wszak zaczynać mamy od dwóch dowolnych liczb, to wcisnę przed 1 liczbę 35. W tym wypadku zaczynając od 35,1,… mamy 2014 na 12 pozycji.
P.S. mam nadzieję, że dowolne liczby nie oznaczają liczb ujemnych, bo w tym wypadku można ciągnąć i ciągnąc ten ciąg.
Jasne, dlatego napisałem w nawiasie „dodatnie”.
mp
Ten problem najłatwiej rozwiązać od tyłu: liczbą poprzedzającą 2014 jest
„mniej więcej” 2014/fi czyli 1245, a stąd już leci cały ciąg… od tyłu:
2014 1245 769 476 293 183 110 73 37 36 1 35
Co więcej, rozwiązanie gospodarza można „wzmocnić”, wpisując na początku jego ciągu liczbę 56
2014 jest DWUNASTYM wyrazem dla x1=35 i x2=1
1 i 36
Widzę, że blog ma problem z poprawnym wyświetleniem mojego komentarza (usuwa formatowanie, obcina część wpisu).
Dlatego umieszczam wpis jeszcze raz, mając nadzieję, że tym razem wyświetli się poprawnie 😉
Zacznijmy od prostej obserwacji, dzięki której możemy bez większych problemów wydłużyć podany ciąg.
Wystarczy zacząć od wartości 56 i 2, dalej otrzymamy 58 i resztę wartości, które pojawiają się w zaproponowanym rozwiązaniu.
Uzyskujemy ciąg składający się z 11 wyrazów, ale da się jeszcze lepiej 😉
Niech F(n) będzie klasycznym ciągiem Fibonacciego, tzn. F(1)=1, F(2)=1, F(3)=2, F(4)=3, itd.
Szukany ciąg określmy jako f(1)=a, f(2)=b, f(3)=a+b, …, f(k-1)=x, f(k)=2014, dla pewnych dodatnich liczb całkowitych a i b.
Powyższy ciąg jest rosnący (być może z wyjątkiem pierwszych dwóch wyrazów),
zatem 0 < x < 2014
Zróbmy kolejny ciąg g, który od powyższego będzie różnił się tylko kolejnością wyrazów, tzn.:
g(1)=2014, g(2)=x, …, g(k-1)=b, g(k)=a.
Oczywiście w ciągu g zachodzi warunek g(n) = g(n-2) – g(n-1)
Liczymy zatem:
g(3) = 2014-x
g(4) = x – (2014-x) = 2x-2014
g(5) = 2014-x – (2x-2014) = 2*2014-3x
g(6) = 2x-2014 – (2*2014-3x) = 5x-3*2014
g(7) = 2*2014-3x – (5x-3*2014) = 5*2014-8x
itd…
Wprawny obserwator zauważy, że zachodzą następujące wzory (dowód jest indukcyjny i dość prosty do przeprowadzenia, dlatego go pomijam):
g(2n) = F(2n-1)*x – F(2n-2)*2014
g(2n+1) = F(2n-1)*2014 – F(2n)*x
Chcemy dobrać wartość x tak, aby
0 < g(2n) i 0 < g(2n+1)
lub
0 < g(2n+1) i 0 < g(2n+2)
Pierwszy przypadek daje nam nierówności:
F(2n-2)*2014 < F(2n-1)*x
F(2n)*x < F(2n-1)*2014
czyli:
2014 * F(2n-2)/F(2n-1) < x < 2014 * F(2n-1)/F(2n)
Drugi przypadek daje nierówności:
F(2n)*x < F(2n-1)*2014
F(2n)*2014 < F(2n+1)*x
czyli:
2014 * F(2n)/F(2n+1) < x < 2014 * F(2n-1)/F(2n)
W obu przypadkach wartość x znajduje się pomiędzy liczbami postaci
x1 = 2014 * F(n-2)/F(n-1)
oraz
x2 = 2014 * F(n-1)/F(n)
Liczymy kolejno wartości x1 i x2 dla kolejnych wartości n i szukamy takiej pary, dla której części całkowite liczb x1 i x2 różnią się.
Oczywiście wraz ze wzrostem n, wartości x1 i x2 zbiegają do wartości 2014/fi, która w przybliżeniu wynosi 1244,720…
Zatem, gdy wartości x1 i x2 zbliżą się dostatecznie do tej granicy, to możemy przerwać obliczenia.
Tu z pomocą przychodzi komputer, który pomaga stwierdzić, że ostatnią parą, dla której części całkowite różnią się, są wartości dla n=11. Wtedy
x1 = 1245,018…
x2 = 1244,606…
Teraz wystarczy odtworzyć ciąg g, przyjmując x=1245. Otrzymujemy:
2014, 1245, 769, 476, 293, 183, 110, 73, 37, 36, 1, 35, -34
w którym dopiero trzynasty wyraz jest ujemny.
I oczywiście odwracając wyrazy ciągu g uzyskujemy najlepsze rozwiązanie, czyli ciąg 12-wyrazowy spełniający warunki zadania:
35, 1, 36, 37, 73, 110, 183, 293, 476, 769, 1245, 2014
Mam nadzieję, że nie pomyliłem się przy ręcznym przepisywaniu wartości ani wzorów 😉
Sukces – ostatni wpis wygląda prawidłowo!
Problemem były znaczki mniejszości i większości umieszczane w komentarzu. Prawdopodobnie przy próbie ich wyświetlenia przeglądarka traktowała je jako fragment htmla do wyświetlenia i ukrywała część komentarza jako tag htmlowy. Rozwiązanie było odwrócenie wszystkich nierówności, tak aby we wpisie znajdowały się znaczki tylko jednego rodzaju. Słabe to, może warto zgłosić ten problem administratorom bloga?
Pozdrawiam
1,36,37,73,110,183,293,476,769,1245,2014,…
Gdyby pierwszy wyraz ciągu mógł być większy od drugiego, byłyby jeszcze dwa:
56,2,58,60,118,178,296,474,770,1244,2014,…
35,1,36,37,73,110,183,293,476,769,1245,2014,…
@gpsE
Nie wiem, co w tym przypadku będzie oznaczać „analitycznie”, ale jestem ciekaw. To bardzo interesujący pomysł z tymi „powariowanymi” (a może można by je nazwać: uogólnionymi?) ciągami Fibonacciego. Jestem o krok od rozwiązania typu „na piechotę”, zauważyłem jedną ciekawą rzecz: jeśli ciąg zaczyna się od wyrazów m, n, zaczynamy sprawdzanie od n=m i potem m+1, m+2, m+3, m+k, etc, to kolejne wyrazy np. a(12) takich ciągów przy rosnącym k tworzą ciąg arytmetyczny, z różnicą, która też nie jest byle jaka, a ma coś wspólnego z Fibonaccim.
To charakterystyczne dla ciągu Fibonacciego, tzn. przy rozpatrywaniu różnych jego własności często jak królik z kapelusza nagle wyskakuje taki sam ciąg-dziecko Fibonacciego – przypomina to klonowanie.
mp
Prawidłowy ciąg to
35 1 36 37 73 110 183 293 476 769 1245 2014. Założyłem przy pierwszym komentarzu, że każda następna liczba ciągu jest większa lub równa poprzedniej (jak w ciągu Fibonacciego)
@aps
quasi-analitycznie można podejść do problemu tak, że ciąg Fibonacciego można zredukować do problemu algebraicznego z macierzą 2*2, w którym kolejne wartości ciągu generuje się poprzez mnożenie dotychczasowego rozwiązania (para liczb) przez tę macierz. To równanie kwadratowe, o którym pisze gospodarz, to tzw. wielomian charakterystyczny tej macierzy, a jego pierwiastki to wartości własne macierzy. W odpowiedniej bazie ta macierz jest diagonalna z wartościami własnymi na diagonali. Jak się to podniesie do dużej potęgi, to większa wartość własna wygrywa z mniejszą. Czyli jeżeli ciąg Fibo ma mieć dużo wyrazów, to zawsze zobaczymy w nim fi, czyli złoty podział, czyli pierwiastek tego wielomianu charakterystycznego.
O tych macierzach można *trochę* poczytać na wiki w haśle Ciąg Fibonacciego. W wersji angielskiej jest dużo więcej.
Z Tri jest dokładnie tak samo, tylko macierz jest 3 na 3.
Powyższe pozwala „zgadnąć” rozwiązanie, potem tylko trzeba jakoś sprawdzić, czy jest jedyne i czy „obok” nie ma lepszych.
Pierwszy wyraz jest równy 35, a drugi to 1. Wtedy liczba 2014 znajdzie się na 12. pozycji.
@ccp @aps:
Widzę, że pomysłów jest więcej, wobec tego opisuję mój tok rozumowania:
Najpierw oszacowalem na ktorym miejscu najpozniej moze znalezc sie liczba 2014. Dzielac 2014 na 2 oraz powtarzajac te operacje az do uzyskania liczby ok. 0,9…. ktora mozna zaokraglic do 1 doszedlem do wniosku, ze 2014 powinno znalezc sie na 12 miejscu. Nastepnie napisalem rownania na kolejne wyrazy ciągu zaczynajac od ostatniego:
12. 2014
11. x
10. 2014 – x
9. 2x – 2014
…
2. -55x + 34 × 2014
1. 89x – 55 × 2014
0. – 144x + 89 × 2014 (zerowy wyraz wpisalem dla sprawdzenia czy przypadkiem sie nie pomylilem zgadujac na ktorym miejscu najpozniej moze sie pojawic liczba 2014 – wszystko sie zgadza, wychodzi liczba ujemna).
A teraz nalezy zgadnac x. Nie jest to trudne, gdyz 55 × 2014 = 110 770
110 770/89 = 1244 z hakiem.
Sprawdzamy pierwszy mozliwy x = 1245, ktory okazuje sie tym szukanym. Napisane przeze mnie rownania mozna wykorzystac do znalezienia ciagu podanego w przykladzie: 2, 58,…
Wystarczy zalozyc, ze 2014 ma sie pojawic na 10 miejscu, a nastepnie postepowac analogicznie.
Pozdrawiam 🙂
@cpp
Dzięki. Bo też i ciekawie jest, tak ogólnie, gdy oprócz rozwiązania podane jest, jak rozwiązujący do niego doszedł, i bardzo często mogłoby się okazać, że ilu rozwiązujących, tyle pomysłów. Mnie na przykład wyszła para początkowa (1,36) i wyraz a(11), tak więc o 1 lepiej niż (2,58) i niczego lepszego, albo równie dobrego, nie znalazłem. Zaryzykowałbym nawet twierdzenie, że nie ma – o ile się nie pomyliłem. Algorytm postępowania jest taki, że sprawdzamy kolejne a(n), poczynając od n=17 (dla „zwykłego” ciągu Fibonacciego jest to 1597, i rychło można się przekonać, że nic tu nie zwojujemy, podobnie dla n=16, 15… im mniejsze n, tym więcej sprawdzania, bo trzeba brać pod uwagę więcej par początkowych wyrazów, (2,58) dla a(10) robi wrażenie). W tym miejscu można zauważyć to, o czym pisałem: gdy założymy, że pierwszym wyrazem jest 1, to różnica pomiędzy kolejnymi a(11) dla drugiego wyrazu 1, 2, 3, etc., jest równa 55, co skądinąd jest 10-tym wyrazem w zwykłym ciągu Fibonacciego. I w ten sposób dochodzimy do ciągu 1, 36, 37, 73, 110, 183, 293, 476, 769, 1245, 2014. Różnica ta dla a(11) i każdego a(n) jest ta sama, gdy pierwszym wyrazem jest 2, 3, etc. A wszystko to, przyznam, w Excelu, w którym te ciągi bardzo łatwo uzyskuje się przez _przeciąganie_.
Na 11. miejscu:
1,36,37,73,110,183,293,476,769,1245,2014
a nawet na 12 🙂
35,1,36,37,73,110,183,293,476,769,1245,2014
Jeszcze o sposobie jaki zastosowałem.
Aby znaleźć liczbę poprzedzającą 2014, wystarczy obliczyć 2014/fi i zaokrąglić. Dalej już tylko odejmowanie.
1, 36, 37, 73, 110, 183, 293, 476, 769, 1245, 2014
1, 36 – 2014 na 11 m-cu
@Andrzej, ale ciąg chyba z definicji powinien być nie malejący (również dla pierwszych dwóch elementów)
Zaniemówiłam z wrażenia… Cóż za blog, cóż za pasjonaci, cóż za mądrzy pojętni ludzie … Ja z cyferkami jestem raczej na bakier, wolę jednak literki.
Matematycznym intelektom kłaniam się jednak w pas bo nawet ładna kaligrafia opiera się na matematycznych proporcjach stosunku szerokości stalówki do wysokości litery.
Witam nostalgicznie, bo przypomniałem sobie, że w zamierzchłych czasach, studiując na poligrafii, uczęszczałem na ASP na wykłady z liternictwa, które prowadził Roman Tomaszewski. Było to wprawdzie liternictwo drukarskie, a nie kaligrafia, ale też ładne 🙂
mp
Ojej, a zatem okazało się, ze gdy zastosujemy wybieg w postaci zapodania na dwóch pierwszych miejscach liczb 35 i 1 (w tej kolejności), to uzyskujemy wynik lepszy niż „zwykłe” 1, 36… Wypada pogodzić się z porażką, choć estetycznie sympatyzuję z rozwiązaniem własnym i wszystkich purystów co uważają, że a(1) nie powinno być większe od a(2), a co najwyżej równe 🙂
@cpp, @miodziu i @gpsE – bardzo ciekawe rozwiązania.