szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 20 paź 2014, o 20:28 
Użytkownik
Avatar użytkownika

Posty: 572
Lokalizacja: Kraków
Ile jest ciągów n-elementowych składających się z 0 i 1, w których żadne 3 kolejne wyrazy nie są takie same?

Rozpisując sobie w 'drzewku' możliwości zaczynając od zera, mam wrażenie, że dla kolejnych n są one liczbami Fibonacciego, plus drugie tyle (zaczynamy od jedynki) i wynik którego się spodziewam to 2F _{n+1}. Ale nie potrafię tego formalnie wykazać :D
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 21 paź 2014, o 19:04 
Użytkownik

Posty: 70
Lokalizacja: Warszawa
hm... za każdym razem możliwości "dowolnego" ciągu będzie 2^n. Od tego odjąć trzeba wszystkie ciągi, które mają te trzy kolejne wyrazy takie same.
Wybieramy zatem trzy kolejne miejsca na n-2 sposobów. (bo dla n=3 jeden sposób (123), dla n=4: 123,234 itd.) Zauważmy, że wystarczy nam jedna trójka, żeby "zdyskwalifikować" dany ciąg, ale nie "tylko" jedna trójka. Może być ich więcej - nam to wszystko jedno.
Każdy taki ciąg trzeba pomnożyć razy 2 (bo dla 0 i dla 1) oraz przez 2^{n-3}, bo resztę (p=n-3) mozna przecież dobrać na 2^p sposobów.

Dalej trzeba byłoby poprzeliczać. :D
Góra
Mężczyzna Offline
PostNapisane: 21 paź 2014, o 21:47 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
Mają być ciągi zero-jedynkowe a tu widzę pojawiają się nagle ciągi

np: 1,2,3

może ktoś mi wytłumaczy to!


A poza tym skoro ciągi są zero-jedynkowe to jak wytłumaczyć że kolejne trzy wyrazy nie są takie same.
Załóżmy, że pierwszy wyraz będzie jeden drugi musi być zero a trzeci musi być równy któremuś
z dwóch poprzednich.
Wynika to nawet z zasady szufladkowej!!!
Góra
Mężczyzna Offline
PostNapisane: 21 paź 2014, o 21:54 
Użytkownik

Posty: 70
Lokalizacja: Warszawa
Piszac 234 chodzilo mi o miejsca w ciagu n-elementowym
Góra
Mężczyzna Offline
PostNapisane: 21 paź 2014, o 21:57 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
Samo sformułowanie zadania jest mało precyzyjne i niejednoznaczne.
Można dyskutować co autor miał na myśli!!!
Góra
Mężczyzna Offline
PostNapisane: 21 paź 2014, o 22:02 
Użytkownik

Posty: 70
Lokalizacja: Warszawa
No chodzilo im o to, zeby nie bylo trzech jedynek obok siebie lub trzech zer obok siebie.
"zadne trzy kolejne nie sa takie same". Moim zdaniem jest to sformułowane jasno
Góra
Mężczyzna Offline
PostNapisane: 21 paź 2014, o 23:18 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
teraz jest jasno

i będzie szło według Fibonacciego

a_{1}=2
a_{2}=4

a_{3}=6

a_{4}=10

itd...
dalej możesz indukcyjnie tam gdzie kończy się dwoma jedynkami lub dwoma zerami masz tylko jedną możliwość a tam gdzie się kończy 0,1 lub

1,0 masz dwie możliwości
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 ciagi ternarne  anakonda1234561  0
 Ciągi ternarne-rekurencja  stella17  1
 Ciągi ternrne  bolt24  2
 Sześć kul i ciągi  Natasha  1
 Trasy wycieczki, liczby, ciągi, kulki  Brzezin  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl