Rozkładem liczby \(\displaystyle{ n}\) nazywamy jej przedstawienie jako sumę i różnicę pewnych liczb Fibonacciego (niekoniecznie różnych). Rozkład jest optymalny, jeżeli zawiera minimalną możliwą liczbę liczb Fibonacciego.
Udowodnij, że istnieje optymalny rozkład, w którym nie istnieją 2 liczby Fibonacciego, których indeksy różnią się co najwyżej o 2.
[Ciągi] Fibonacci zapożyczony z OIa i przerobiony przez Swistaka
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
-
szw1710
[Ciągi] Fibonacci zapożyczony z OIa i przerobiony przez Swistaka
Podaj jeszcze, czym jest indeks liczby Fibonacciego? Numer w ciągu Fibonacciego?
-
michal_z
- Użytkownik
- Posty: 29
- Rejestracja: 14 sty 2006, o 15:17
- Płeć: Mężczyzna
- Lokalizacja: małopolska
- Pomógł: 4 razy
[Ciągi] Fibonacci zapożyczony z OIa i przerobiony przez Swistaka
Dla ambitnych, podpunkt b) : Wykazać, że istnieje optymalny rozkład, zawierający liczbę \(\displaystyle{ F_k}\), która jest najbliższą liczbie \(\displaystyle{ n}\) liczbą Fibonacciego (jeśli istnieją dwie, to \(\displaystyle{ F_k}\) jest dowolną).
[Ciągi] Fibonacci zapożyczony z OIa i przerobiony przez Swistaka
Przez \(\displaystyle{ f_{i}}\) oznaczam liczbę Fibonacciego o indeksie i.
Obserwacje:
(1) \(\displaystyle{ f_{i} + f_{i+3} + f_{i+5} = f_{i+6} - f_{i+1}}\)
(2) \(\displaystyle{ f_{i} + f_{i+2} = f_{i+3} - f_{i-1}}\)
(3) \(\displaystyle{ f_{i} + f_{i+1} = f_{i+2}}\)
Rozłóżmy liczbę naturalną n na sumę liczb Fibonacciego, w ten sposób:
1. Weźmy największą liczbę Fibonacciego mniejszą równą n i dodaj ją do rozkładu.
2. Odejmijmy od n tę liczbę Fibonacciego.
3. Jeżeli \(\displaystyle{ n>0}\) to idź do kroku jeden.
W ten sposób otrzymamy rozkład liczby n, w którym nie istnieją 2 liczby Fibonacciego, których indeksy różnią się co najwyżej o 1. Teraz zapiszmy ten rozkład w kolejności rosnącej i przejrzyjmy go od liczby najmniejszej do największej. Podczas przeglądania zawsze gdy to możliwe używajmy obserwacji (1), (2) i (3). Teraz zauważmy, że przeglądając ten rozkład, to gdy pozostawiamy "za sobą" jakąś liczbę Fibonacciego to różnica jej indeksu i indeksu następnej liczby Fibonacciego wynosi co najmniej 4, a gdy następnie wykorzystamy obserwację (2), to może ona sprawić, że różnica indeksów liczb pozostawionych za sobą zmniejszy się do 3. Z tego wynika, że gdy przejrzymy już cały rozkład, różnica wszystkich liczb Fibonacciego tam umieszczonych wynosi co najmniej 3, czyli w tym rozkładzie nie istnieją takie 2 liczby Fibonacciego, że różnica ich indeksów wynosi co najwyżej 2.
Ten rozkład jest rozkładem poszukiwanym w zadaniu.
Wiem, że to raczej mało matematyczny dowód, ale na lepszy mnie nie stać.
Obserwacje:
(1) \(\displaystyle{ f_{i} + f_{i+3} + f_{i+5} = f_{i+6} - f_{i+1}}\)
(2) \(\displaystyle{ f_{i} + f_{i+2} = f_{i+3} - f_{i-1}}\)
(3) \(\displaystyle{ f_{i} + f_{i+1} = f_{i+2}}\)
Rozłóżmy liczbę naturalną n na sumę liczb Fibonacciego, w ten sposób:
1. Weźmy największą liczbę Fibonacciego mniejszą równą n i dodaj ją do rozkładu.
2. Odejmijmy od n tę liczbę Fibonacciego.
3. Jeżeli \(\displaystyle{ n>0}\) to idź do kroku jeden.
W ten sposób otrzymamy rozkład liczby n, w którym nie istnieją 2 liczby Fibonacciego, których indeksy różnią się co najwyżej o 1. Teraz zapiszmy ten rozkład w kolejności rosnącej i przejrzyjmy go od liczby najmniejszej do największej. Podczas przeglądania zawsze gdy to możliwe używajmy obserwacji (1), (2) i (3). Teraz zauważmy, że przeglądając ten rozkład, to gdy pozostawiamy "za sobą" jakąś liczbę Fibonacciego to różnica jej indeksu i indeksu następnej liczby Fibonacciego wynosi co najmniej 4, a gdy następnie wykorzystamy obserwację (2), to może ona sprawić, że różnica indeksów liczb pozostawionych za sobą zmniejszy się do 3. Z tego wynika, że gdy przejrzymy już cały rozkład, różnica wszystkich liczb Fibonacciego tam umieszczonych wynosi co najmniej 3, czyli w tym rozkładzie nie istnieją takie 2 liczby Fibonacciego, że różnica ich indeksów wynosi co najwyżej 2.
Ten rozkład jest rozkładem poszukiwanym w zadaniu.
Wiem, że to raczej mało matematyczny dowód, ale na lepszy mnie nie stać.