Dwa ciągi liczbowe i ich okres
-
- Użytkownik
- Posty: 32
- Rejestracja: 8 wrz 2015, o 19:21
- Płeć: Mężczyzna
- Lokalizacja: z daleka
- Podziękował: 1 raz
Dwa ciągi liczbowe i ich okres
Witam serdecznie,
Nie byłem pewny w jakim dziale umieścić temat. Ewentualnie proszę o przeniesienie.
Mam prośbę o dowód poprawności pewnego twierdzenia. Jeżeli nie jest prawidłowe to prośba dotyczy tego wytknięcia
Mamy ciąg liczbowy \(\displaystyle{ a_{i}}\), w którym zawsze występuje cykl. Przykładowo niech będzie to:
\(\displaystyle{ 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5...}\)
czyli:
\(\displaystyle{ a_{0} = 1 \\
a_{1} = 2 \\
a_{2} = 3 \\
a_{3} = 4 \\
a_{4} = 5 \\
a_{i} = a_{i \% 5}}\)
Na podstawie tego ciągu generujemy inny ciąg liczbowy \(\displaystyle{ n_{i}}\) według następującej reguły:
\(\displaystyle{ n_{0} = a_{x + k \cdot 0} \\
n_{1} = a_{x + k \cdot 1} \\
n_{2} = a_{x + k \cdot 2} \\
n_{i} = a_{x + k \cdot i}}\)
Dla przykładu weźmy \(\displaystyle{ x = 2}\) i \(\displaystyle{ k = 3}\):
\(\displaystyle{ n_{0} = a_{2 + 3 \cdot 0} = a_{2} = 3 \\
n_{1} = a_{2 + 3 \cdot 1} = a_{5} = 1 \\
n_{2} = a_{2 + 3 \cdot 2} = a_{8} = 4 \\
n_{3} = a_{2 + 3 \cdot 3} = a_{11} = 2 \\
n_{4} = a_{2 + 3 \cdot 4} = a_{14} = 5 \\
n_{5} = a_{2 + 3 \cdot 5} = a_{17} = 3 \\
n_{6} = a_{2 + 3 \cdot 6} = a_{20} = 1}\)
...
Udowodnić należy że ciąg \(\displaystyle{ n_{i}}\) także zawsze jest okresowy dla dowolnego ciągu wejściowego \(\displaystyle{ a_{i}}\) (także okresowego) i dowolnych zmiennych \(\displaystyle{ x}\) i \(\displaystyle{ k}\).
Mam nadzieję, że nigdzie się nie pomyliłem ale jednak jakiś błąd możliwy
Bardzo dziękuję za wszelką pomoc.
Nie byłem pewny w jakim dziale umieścić temat. Ewentualnie proszę o przeniesienie.
Mam prośbę o dowód poprawności pewnego twierdzenia. Jeżeli nie jest prawidłowe to prośba dotyczy tego wytknięcia
Mamy ciąg liczbowy \(\displaystyle{ a_{i}}\), w którym zawsze występuje cykl. Przykładowo niech będzie to:
\(\displaystyle{ 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5...}\)
czyli:
\(\displaystyle{ a_{0} = 1 \\
a_{1} = 2 \\
a_{2} = 3 \\
a_{3} = 4 \\
a_{4} = 5 \\
a_{i} = a_{i \% 5}}\)
Na podstawie tego ciągu generujemy inny ciąg liczbowy \(\displaystyle{ n_{i}}\) według następującej reguły:
\(\displaystyle{ n_{0} = a_{x + k \cdot 0} \\
n_{1} = a_{x + k \cdot 1} \\
n_{2} = a_{x + k \cdot 2} \\
n_{i} = a_{x + k \cdot i}}\)
Dla przykładu weźmy \(\displaystyle{ x = 2}\) i \(\displaystyle{ k = 3}\):
\(\displaystyle{ n_{0} = a_{2 + 3 \cdot 0} = a_{2} = 3 \\
n_{1} = a_{2 + 3 \cdot 1} = a_{5} = 1 \\
n_{2} = a_{2 + 3 \cdot 2} = a_{8} = 4 \\
n_{3} = a_{2 + 3 \cdot 3} = a_{11} = 2 \\
n_{4} = a_{2 + 3 \cdot 4} = a_{14} = 5 \\
n_{5} = a_{2 + 3 \cdot 5} = a_{17} = 3 \\
n_{6} = a_{2 + 3 \cdot 6} = a_{20} = 1}\)
...
Udowodnić należy że ciąg \(\displaystyle{ n_{i}}\) także zawsze jest okresowy dla dowolnego ciągu wejściowego \(\displaystyle{ a_{i}}\) (także okresowego) i dowolnych zmiennych \(\displaystyle{ x}\) i \(\displaystyle{ k}\).
Mam nadzieję, że nigdzie się nie pomyliłem ale jednak jakiś błąd możliwy
Bardzo dziękuję za wszelką pomoc.
Ostatnio zmieniony 15 wrz 2015, o 21:03 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- Medea 2
- Użytkownik
- Posty: 2491
- Rejestracja: 30 lis 2014, o 11:03
- Płeć: Kobieta
- Podziękował: 23 razy
- Pomógł: 479 razy
Dwa ciągi liczbowe i ich okres
Jeżeli ciąg \(\displaystyle{ a_i}\) jest okresowy i jego okres wynosi \(\displaystyle{ t}\), to okresem \(\displaystyle{ n_i}\) również jest \(\displaystyle{ t}\). Uzasadnienie:
\(\displaystyle{ n(i+t) = a(x+k(i+t)) = a(x+ki + kt) = a(x+ki) = n(i)}\).
\(\displaystyle{ n(i+t) = a(x+k(i+t)) = a(x+ki + kt) = a(x+ki) = n(i)}\).
Ostatnio zmieniony 15 wrz 2015, o 10:53 przez Medea 2, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 32
- Rejestracja: 8 wrz 2015, o 19:21
- Płeć: Mężczyzna
- Lokalizacja: z daleka
- Podziękował: 1 raz
Dwa ciągi liczbowe i ich okres
O kurcze - bardzo zwięźle
Ale czy oby dla każdego \(\displaystyle{ x}\) i \(\displaystyle{ k}\) okres \(\displaystyle{ n_{i}}\) będzie wynosił \(\displaystyle{ t}\) (tyle samo co dla \(\displaystyle{ a_{i}}\))?
Weźmy ciąg \(\displaystyle{ a_{i}}\) z pierwszego mojego postu w temacie.
Weźmy \(\displaystyle{ x = 1}\) i \(\displaystyle{ k = 5}\).
Wtedy ciąg \(\displaystyle{ n_{i}}\) będzie następujący: \(\displaystyle{ 2, 2, 2, 2...}\)
Rozmiar okresu = \(\displaystyle{ 1}\) i jest różny od rozmiaru okresu \(\displaystyle{ a_{i}}\).
PS. W dowodzie chodzi tylko o dowód, że istnieje okres \(\displaystyle{ n_{i}}\).
Ale czy oby dla każdego \(\displaystyle{ x}\) i \(\displaystyle{ k}\) okres \(\displaystyle{ n_{i}}\) będzie wynosił \(\displaystyle{ t}\) (tyle samo co dla \(\displaystyle{ a_{i}}\))?
Weźmy ciąg \(\displaystyle{ a_{i}}\) z pierwszego mojego postu w temacie.
Weźmy \(\displaystyle{ x = 1}\) i \(\displaystyle{ k = 5}\).
Wtedy ciąg \(\displaystyle{ n_{i}}\) będzie następujący: \(\displaystyle{ 2, 2, 2, 2...}\)
Rozmiar okresu = \(\displaystyle{ 1}\) i jest różny od rozmiaru okresu \(\displaystyle{ a_{i}}\).
PS. W dowodzie chodzi tylko o dowód, że istnieje okres \(\displaystyle{ n_{i}}\).
- Medea 2
- Użytkownik
- Posty: 2491
- Rejestracja: 30 lis 2014, o 11:03
- Płeć: Kobieta
- Podziękował: 23 razy
- Pomógł: 479 razy
Dwa ciągi liczbowe i ich okres
Właśnie. Aby udowodnić, że ciąg jest okresowy, wystarczy podać jego dowolny okres, nie trzeba skupiać się na okresie podstawowym (najmniejszym). Sytuacja przypomina trochę "grube" oszacowania, przykładowo: ciąg \(\displaystyle{ 2^n}\) jest nieograniczony (i rozbieżny do \(\displaystyle{ \infty}\)), bo \(\displaystyle{ 2^n > n}\)
-
- Użytkownik
- Posty: 32
- Rejestracja: 8 wrz 2015, o 19:21
- Płeć: Mężczyzna
- Lokalizacja: z daleka
- Podziękował: 1 raz
Dwa ciągi liczbowe i ich okres
Ah. Rozumiem.
Źle chyba jednak sformułowałem pytanie (myśląc tylko o okresie) :/
Chodziło mi raczej o dowód na to, że jeżeli mamy w ciągu \(\displaystyle{ n_{i}}\) wyraz powiedzmy pierwszy \(\displaystyle{ n_{0} = 1}\) i będziemy lecieć po kolejnych wyrazach aż do np. \(\displaystyle{ n_{10}}\), które okaże się także (jako pierwsze następne po \(\displaystyle{ n_{0}}\)) równe \(\displaystyle{ 1}\) to właśnie to będzie cyklem.
Jednym słowem niemożliwy jest cykl np. typu:
\(\displaystyle{ 1, 1, 2, 2, 1, 1, 2, 2...}\)
Zastanawiam się nad tym w kontekście pewnego programu komputerowego, który piszę.
Gdybyśmy mogli uzyskać przykładowo ciąg \(\displaystyle{ n_{i}}\): \(\displaystyle{ 1, 1, 2, 2, 1, 1, 2, 2...}\)
To mój program komputerowy przeszukiwanie zacząłby od \(\displaystyle{ 1}\) i skończył na kolejnej (drugiej) jedynce i na tym doszedł do wniosku, że odnalazł cykl, ponieważ jedynka się powtarza.
Dowód, który przedstawiłaś Medea 2 w drugim poście już jest bardzo pomocny, ponieważ teoretycznie wystarczyłoby, że sprawdziłbym tych \(\displaystyle{ t}\) wyrazów i tam byłby na 100% cykl i ewentualnie wyciągnął z tego mniejsze cykle.
Źle chyba jednak sformułowałem pytanie (myśląc tylko o okresie) :/
Chodziło mi raczej o dowód na to, że jeżeli mamy w ciągu \(\displaystyle{ n_{i}}\) wyraz powiedzmy pierwszy \(\displaystyle{ n_{0} = 1}\) i będziemy lecieć po kolejnych wyrazach aż do np. \(\displaystyle{ n_{10}}\), które okaże się także (jako pierwsze następne po \(\displaystyle{ n_{0}}\)) równe \(\displaystyle{ 1}\) to właśnie to będzie cyklem.
Jednym słowem niemożliwy jest cykl np. typu:
\(\displaystyle{ 1, 1, 2, 2, 1, 1, 2, 2...}\)
Zastanawiam się nad tym w kontekście pewnego programu komputerowego, który piszę.
Gdybyśmy mogli uzyskać przykładowo ciąg \(\displaystyle{ n_{i}}\): \(\displaystyle{ 1, 1, 2, 2, 1, 1, 2, 2...}\)
To mój program komputerowy przeszukiwanie zacząłby od \(\displaystyle{ 1}\) i skończył na kolejnej (drugiej) jedynce i na tym doszedł do wniosku, że odnalazł cykl, ponieważ jedynka się powtarza.
Dowód, który przedstawiłaś Medea 2 w drugim poście już jest bardzo pomocny, ponieważ teoretycznie wystarczyłoby, że sprawdziłbym tych \(\displaystyle{ t}\) wyrazów i tam byłby na 100% cykl i ewentualnie wyciągnął z tego mniejsze cykle.
-
- Użytkownik
- Posty: 22173
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3748 razy
Dwa ciągi liczbowe i ich okres
Zobacz, co się stanie jak zaczniesz np od ciagu okresowego \(\displaystyle{ 1,1,1,1,1,2,1,1,1,1,1,2,1,1,1,1,1,2,...}\)
Ostatnio zmieniony 15 wrz 2015, o 21:04 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 32
- Rejestracja: 8 wrz 2015, o 19:21
- Płeć: Mężczyzna
- Lokalizacja: z daleka
- Podziękował: 1 raz
Dwa ciągi liczbowe i ich okres
Nie, nie. W ciągu początkowym \(\displaystyle{ a_{i}}\) w samym okresie nie mogą powtarzać się wartości wyrazów więc coś takiego odpada. Zapomniałem o tym napisać za co przepraszam.
\(\displaystyle{ 1, 1, 2, 1, 1, 2...}\) - nie może wystąpić taki ciąg \(\displaystyle{ a_{i}}\),
\(\displaystyle{ 1, 2, 3, 1, 2, 3...}\) - ten jako ciąg \(\displaystyle{ a_{i}}\) jest ok.
Już wiemy, że ciąg wynikowy \(\displaystyle{ n_{i}}\) jest okresowy najmarniej z takim samym okresem jak \(\displaystyle{ a_{i}}\) (post drugi Medea 2).
Muszę jednak wiedzieć czy w okresie podstawowym (najmniejszym) ciągu wynikowego \(\displaystyle{ n_{i}}\) wartości wyrazów także się nie powtarzają.
\(\displaystyle{ 1, 1, 2, 1, 1, 2...}\) - nie może wystąpić taki ciąg \(\displaystyle{ a_{i}}\),
\(\displaystyle{ 1, 2, 3, 1, 2, 3...}\) - ten jako ciąg \(\displaystyle{ a_{i}}\) jest ok.
Już wiemy, że ciąg wynikowy \(\displaystyle{ n_{i}}\) jest okresowy najmarniej z takim samym okresem jak \(\displaystyle{ a_{i}}\) (post drugi Medea 2).
Muszę jednak wiedzieć czy w okresie podstawowym (najmniejszym) ciągu wynikowego \(\displaystyle{ n_{i}}\) wartości wyrazów także się nie powtarzają.
- Medea 2
- Użytkownik
- Posty: 2491
- Rejestracja: 30 lis 2014, o 11:03
- Płeć: Kobieta
- Podziękował: 23 razy
- Pomógł: 479 razy
Dwa ciągi liczbowe i ich okres
Można ograniczyć poszukiwania do dzielników \(\displaystyle{ t}\). Spójrzmy jeszcze raz na moją równość, ale załóżmy teraz, że \(\displaystyle{ u}\) jest najmniejszym okresem dla \(\displaystyle{ n}\). Wtedy
\(\displaystyle{ n(i+u) = a(x+k(i+u)) = a(x+ki + ku) \stackrel{=}{?} a(x+ki) = n(i)}\).
Aby \(\displaystyle{ u}\) było minimalnym okresem, \(\displaystyle{ ku}\) musi być równe \(\displaystyle{ t}\) (lub jego wielokrotności).
\(\displaystyle{ n(i+u) = a(x+k(i+u)) = a(x+ki + ku) \stackrel{=}{?} a(x+ki) = n(i)}\).
Aby \(\displaystyle{ u}\) było minimalnym okresem, \(\displaystyle{ ku}\) musi być równe \(\displaystyle{ t}\) (lub jego wielokrotności).
-
- Użytkownik
- Posty: 32
- Rejestracja: 8 wrz 2015, o 19:21
- Płeć: Mężczyzna
- Lokalizacja: z daleka
- Podziękował: 1 raz
Dwa ciągi liczbowe i ich okres
Medea 2 - dziękuję.
A mógłby może ktoś udowodnić (lub temu zaprzeczyć), że w okresie podstawowym (najmniejszym) ciągu wynikowego \(\displaystyle{ n_{i}}\) wartości wyrazów nie powtarzają się?
Wydaje mi się bardzo prawdopodobne, że jest to prawdą (ale potrzebuję pewności).
A mógłby może ktoś udowodnić (lub temu zaprzeczyć), że w okresie podstawowym (najmniejszym) ciągu wynikowego \(\displaystyle{ n_{i}}\) wartości wyrazów nie powtarzają się?
Wydaje mi się bardzo prawdopodobne, że jest to prawdą (ale potrzebuję pewności).