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}\).
indukcja i rekurencja
-
paulina95
- Użytkownik
- Posty: 25
- Rejestracja: 4 kwie 2015, o 12:26
- Płeć: Kobieta
- Lokalizacja: katowice
- Podziękował: 3 razy
indukcja i rekurencja
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 .
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
-
arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
indukcja i rekurencja
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!
\(\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
- Użytkownik
- Posty: 826
- Rejestracja: 8 wrz 2013, o 11:31
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 187 razy
indukcja i rekurencja
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.
"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
- Posty: 34239
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
indukcja i rekurencja
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.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.
JK