indukcja i rekurencja

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
paulina95
Użytkownik
Użytkownik
Posty: 25
Rejestracja: 4 kwie 2015, o 12:26
Płeć: Kobieta
Lokalizacja: katowice

indukcja i rekurencja

Post autor: paulina95 » 4 kwie 2015, o 13:01

zad1
Wykaż błąd w następującym rozumowaniu. Teza: wszystkie kobiety mają ten sam kolor oczu.
Dowód indukcyjny: dla \(\displaystyle{ n = 1}\) teza jest oczywista. Ustalmy \(\displaystyle{ n}\) i załóżmy, że dla dowolnego \(\displaystyle{ n}\)-osobowego zbioru kobiet wszystkie mają ten sam kolor oczu. Rozważmy teraz zbiór \(\displaystyle{ (n + 1)}\) kobiet i przyjmijmy, że dwie z nich to Ala i Basia. Bez Ali zbiór ten jest \(\displaystyle{ n}\) elementowy, więc z założenia indukcyjnego Basia ma ten sam kolor oczu co pozostałe dziewczyny. Podobnie (bez Basi) wnioskujemy, że Ala ma ten sam kolor oczu co reszta. Zatem wszystkie \(\displaystyle{ (n + 1)}\) kobiet ma ten sam kolor oczu, co kończy indukcję i cały dowód.

zad2
Na ile sposobów można zbudować:
a) prostokąt \(\displaystyle{ 2 \times n}\) za pomocą kwadratów \(\displaystyle{ 1 \times 1}\) oraz \(\displaystyle{ 2 \times 2}\);
b) (∗) wieżę o wymiarach \(\displaystyle{ 2 \times 2 \times n}\) z klocków o wymiarach \(\displaystyle{ 2 \times 2 \times 1}\)?

zad3
Oznaczmy przez \(\displaystyle{ d_n}\) liczbę wszystkich ciągów długości n o wyrazach ze zbioru \(\displaystyle{ \{0, 1, 2\}}\), w których nie występują ani dwie jedynki pod rząd, ani dwie dwójki pod rząd. Np. \(\displaystyle{ d_3 = 17}\), gdyż żądanymi ciągami są \(\displaystyle{ 000, 001, 002, 010, 012, 020, 021, ***, 101, 102, 120, 121, ***, ***, 202, 210, ***}\) (uzupełnij brakujące ciągi \(\displaystyle{ ***}\)). Wyznacz wzór na wyraz ogólny ciągu \(\displaystyle{ d_n}\).
Ostatnio zmieniony 4 kwie 2015, o 19:08 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3707
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko

indukcja i rekurencja

Post autor: arek1357 » 4 kwie 2015, o 15:20

W zadaniu drugim zauważ:

\(\displaystyle{ n=1}\) jedna tylko możliwość dwa małe kwadraciki \(\displaystyle{ a_{1}=1}\)

\(\displaystyle{ n=2}\) dwie tylko możliwość cztery małe kwadraciki, lub jeden duży \(\displaystyle{ a_{2}=2}\)

\(\displaystyle{ n=3}\) trzy tylko możliwość sześć małych kwadracików, lub po dwa: jeden duży, dwa małe

\(\displaystyle{ a_{3}=3}\)

\(\displaystyle{ n=4}\) pięć tylko możliwość osiem małych kwadracików, lub trzy: jeden duży, cztery małe,

lub dwa duże...

\(\displaystyle{ a_{4}=5}\)...

Jak widać możliwości te co łatwo zauważyć tworzą ciąg Fibonacciego!

Podobnie jest w b) zadaniu tylko masz ten sam przypadek na \(\displaystyle{ 3D}\)

Wskazówka:
Klocki w tym przypadku możesz układać: na boku kwadratowym dwa na dwa,(na płasko)
Lub na boku prostokątnym tym dwa na jeden) albo od lewej do prawej lub od góry do dołu.
Czyli w przypadku \(\displaystyle{ n=1}\) masz jedną możliwość (na płasko)
Ale w przypadku \(\displaystyle{ n=2}\) masz już trzy możliwości...
itd...



W zadaniu trzecim zauważ, że ciągi, które kończą zerem w stopniu \(\displaystyle{ d_{n}}\),

to ilość się ich potraja w stopniu \(\displaystyle{ d_{n+1}}\),

A pozostałych się tylko podwaja to znaczy tych, które kończą się jedynką lub dwójką.

Łatwo zauważyć, że ilość ciągów kończących się zerem w wyrazie \(\displaystyle{ d_{n}}\)

Jest tyle samo ile wszystkich ciągów w wyrazie \(\displaystyle{ d_{n-1}}\)

Reasumując te spostrzeżenia otrzymasz:

\(\displaystyle{ d_{n+2}=2d_{n+1}+d_{n}}\),

dla:

\(\displaystyle{ d_{1}=3, d_{2}=7}\)

Jak widać:

\(\displaystyle{ d_{3}=2 \cdot 7+3=17}\)

\(\displaystyle{ d_{4}=41}\)

i masz:

jeden ciąg złożony z samych zer \(\displaystyle{ \left\{ 0,0,0,0\right\}-1}\)

ciągi typu:

\(\displaystyle{ \left\{ 1,0,0,0\right\}-4}\)

\(\displaystyle{ \left\{ 2,0,0,0\right\}-4}\)

\(\displaystyle{ \left\{ 1,2,0,0\right\}-12}\)

\(\displaystyle{ \left\{ 1,1,0,0\right\}-3}\)

\(\displaystyle{ \left\{ 2,2,0,0\right\}-3}\)

\(\displaystyle{ \left\{ 1,1,2,0\right\}-6}\)

\(\displaystyle{ \left\{ 1,2,2,0\right\}-6}\)

\(\displaystyle{ \left\{ 1,1,2,2\right\}-2}\)

Razem: \(\displaystyle{ 41}\)

Przepraszam pomyłka poprawiłem!

Co zgadza się ze wzorem!

Co do zadania pierwszego to się przychylam w przypadku gdy np. trzy razy się przewrócę idąc drogą,
to stosując prawa Murphy’ego na pewno się przewrócę czwarty a nawet piąty raz.

W powyższym zdarzeniu i w wielu podobnych gdzie wszystko działa na naszą niekorzyść taka indukcja jest prawdziwa! Potwierdzona prawem Murphy’ego!

Lecz na pewno się ona nie zdarzy gdy znajdę np. na ulicy stówę to na pewno drugiej lub trzeciej nie znajdę i wtedy indukcja nie zadziała!

Kaf
Gość Specjalny
Gość Specjalny
Posty: 817
Rejestracja: 8 wrz 2013, o 11:31
Płeć: Mężczyzna
Lokalizacja: Wrocław

indukcja i rekurencja

Post autor: Kaf » 4 kwie 2015, o 17:21

Co do 1.: krok indukcyjny nie działa dla \(\displaystyle{ n=1}\) (dlaczego?).

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3707
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko

indukcja i rekurencja

Post autor: arek1357 » 4 kwie 2015, o 17:42

działa

Kaf
Gość Specjalny
Gość Specjalny
Posty: 817
Rejestracja: 8 wrz 2013, o 11:31
Płeć: Mężczyzna
Lokalizacja: Wrocław

indukcja i rekurencja

Post autor: Kaf » 4 kwie 2015, o 18:00

W takim razie zacytuję go podstawiając za \(\displaystyle{ n}\) jeden:
"załóżmy, że dla dowolnego 1-osobowego zbioru kobiet wszystkie mają ten sam kolor oczu. Rozważmy teraz zbiór 2 kobiet i przyjmijmy, że dwie z nich to Ala i Basia. Bez Ali zbiór ten jest 1 elementowy, więc z założenia indukcyjnego Basia ma ten sam kolor oczu co pozostałe dziewczyny. Podobnie (bez Basi) wnioskujemy, że Ala ma ten sam kolor oczu co reszta. Zatem wszystkie 2 kobiet ma ten sam kolor oczu, co kończy indukcję i cały dowód."
Niezbyt działa, bo korzystamy z tego, że prócz Ali i Basi są jeszcze jakieś inne kobiety w tym zbiorze, co dla \(\displaystyle{ n=1}\) nie ma miejsca.

Jan Kraszewski
Administrator
Administrator
Posty: 24938
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław

indukcja i rekurencja

Post autor: Jan Kraszewski » 4 kwie 2015, o 19:10

Kaf pisze:W takim razie zacytuję go podstawiając za \(\displaystyle{ n}\) jeden:
"załóżmy, że dla dowolnego 1-osobowego zbioru kobiet wszystkie mają ten sam kolor oczu. Rozważmy teraz zbiór 2 kobiet i przyjmijmy, że dwie z nich to Ala i Basia. Bez Ali zbiór ten jest 1 elementowy, więc z założenia indukcyjnego Basia ma ten sam kolor oczu co pozostałe dziewczyny. Podobnie (bez Basi) wnioskujemy, że Ala ma ten sam kolor oczu co reszta. Zatem wszystkie 2 kobiet ma ten sam kolor oczu, co kończy indukcję i cały dowód."
Niezbyt działa, bo korzystamy z tego, że prócz Ali i Basi są jeszcze jakieś inne kobiety w tym zbiorze, co dla \(\displaystyle{ n=1}\) nie ma miejsca.
Istotnie tu załamuje się indukcja, ale nie jest to krok \(\displaystyle{ n=1}\) tylko krok \(\displaystyle{ 1 \rightarrow 2}\). Krok początkowy \(\displaystyle{ n=1}\) działa.

JK

Kaf
Gość Specjalny
Gość Specjalny
Posty: 817
Rejestracja: 8 wrz 2013, o 11:31
Płeć: Mężczyzna
Lokalizacja: Wrocław

indukcja i rekurencja

Post autor: Kaf » 5 kwie 2015, o 10:25

To też miałem na myślisz, przepraszam za niefortunne sformułowanie.

ODPOWIEDZ