szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 4 kwi 2015, o 13:01 
Użytkownik

Posty: 25
Lokalizacja: katowice
zad1
Wykaż błąd w następującym rozumowaniu. Teza: wszystkie kobiety mają ten sam kolor oczu.
Dowód indukcyjny: dla n = 1 teza jest oczywista. Ustalmy n i załóżmy, że dla dowolnego n-osobowego zbioru kobiet wszystkie mają ten sam kolor oczu. Rozważmy teraz zbiór (n + 1) kobiet i przyjmijmy, że dwie z nich to Ala i Basia. Bez Ali zbiór ten jest 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 (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 2 \times n za pomocą kwadratów 1 \times 1 oraz 2 \times 2;
b) (∗) wieżę o wymiarach 2 \times 2 \times n z klocków o wymiarach 2 \times 2 \times 1?

zad3
Oznaczmy przez d_n liczbę wszystkich ciągów długości n o wyrazach ze zbioru \{0, 1, 2\}, w których nie występują ani dwie jedynki pod rząd, ani dwie dwójki pod rząd. Np. d_3 = 17, gdyż żądanymi ciągami są 000, 001, 002, 010, 012, 020, 021, ***, 101, 102, 120, 121, ***, ***, 202, 210, *** (uzupełnij brakujące ciągi ***). Wyznacz wzór na wyraz ogólny ciągu d_n.
Góra
Mężczyzna Offline
PostNapisane: 4 kwi 2015, o 15:20 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
W zadaniu drugim zauważ:

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

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

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

a_{3}=3

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

lub dwa duże...

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 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 n=1 masz jedną możliwość (na płasko)
Ale w przypadku n=2 masz już trzy możliwości...
itd...



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

to ilość się ich potraja w stopniu 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 d_{n}

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

Reasumując te spostrzeżenia otrzymasz:

d_{n+2}=2d_{n+1}+d_{n},

dla:

d_{1}=3, d_{2}=7

Jak widać:

d_{3}=2 \cdot 7+3=17

d_{4}=41

i masz:

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

ciągi typu:

\left\{ 1,0,0,0\right\}-4

\left\{ 2,0,0,0\right\}-4

\left\{ 1,2,0,0\right\}-12

\left\{ 1,1,0,0\right\}-3

\left\{ 2,2,0,0\right\}-3

\left\{ 1,1,2,0\right\}-6

\left\{ 1,2,2,0\right\}-6

\left\{ 1,1,2,2\right\}-2

Razem: 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!
Góra
Mężczyzna Offline
PostNapisane: 4 kwi 2015, o 17:21 
Moderator

Posty: 812
Lokalizacja: Zabrze
Co do 1.: krok indukcyjny nie działa dla n=1 (dlaczego?).
Góra
Mężczyzna Offline
PostNapisane: 4 kwi 2015, o 17:42 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
działa
Góra
Mężczyzna Offline
PostNapisane: 4 kwi 2015, o 18:00 
Moderator

Posty: 812
Lokalizacja: Zabrze
W takim razie zacytuję go podstawiając za 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 n=1 nie ma miejsca.
Góra
Mężczyzna Offline
PostNapisane: 4 kwi 2015, o 19:10 
Administrator

Posty: 22728
Lokalizacja: Wrocław
Kaf napisał(a):
W takim razie zacytuję go podstawiając za 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 n=1 nie ma miejsca.

Istotnie tu załamuje się indukcja, ale nie jest to krok n=1 tylko krok 1 \rightarrow 2. Krok początkowy n=1 działa.

JK
Góra
Mężczyzna Offline
PostNapisane: 5 kwi 2015, o 10:25 
Moderator

Posty: 812
Lokalizacja: Zabrze
To też miałem na myślisz, przepraszam za niefortunne sformułowanie.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Indukcja i rekurencja  ast3rot  6
 Rekurencja linowa...  pawelekk  4
 Rekurencja z dwoma zmiennymi.  KaerbEmEvig  2
 rekurencja z funkcją tworzącą  nedroxn  3
 Rekurencja liniowa rzędu I  MenosGrandes  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl