szukanie zaawansowane
 [ Posty: 13 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Lwy w klatkach
PostNapisane: 7 lut 2015, o 12:25 
Użytkownik

Posty: 10
Lokalizacja: Warszawa
Mam problem z poniższym zadaniem:
Wyznaczyć liczbę sposobów, na jakie można rozmieścić lwy w n klatkach ustawionych w rzędzie przy założeniach, iż w jednej klatce mogą być co najwyżej dwa lwy oraz że żadne dwie kolejne klatki nie mogą jednocześnie zawierać lwów.

Mój pomysł jest taki, że jak mamy n klatek, to \frac{n}{2} jest pustych, więc pozostaje w sumie \frac{n}{2} klatek pełnych (z jednym, lub dwoma lwami), lub pustych. Teraz każdą klatkę możemy rozdzielić na 2 miejsca, więc mamy n miejsc. Lwów jest nie więcej niż miejsc, więc jest ich co najwyżej n. Teraz musimy zsumować wszystkie możliwości zależne od liczby lwów, a tych jest \sum_{i=0}^{n} {n+i-1 \choose i}. Czy mój tok rozumowania jest dobry, czy robię gdzieś błąd?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
 Tytuł: Lwy w klatkach
PostNapisane: 7 lut 2015, o 12:30 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Skąd wnioskujesz, że jest n lwów?

Tak samo nie widzę uzasadnienia dla tezy, że n jest liczbą parzystą.
Góra
Mężczyzna Offline
 Tytuł: Lwy w klatkach
PostNapisane: 7 lut 2015, o 12:41 
Użytkownik

Posty: 10
Lokalizacja: Warszawa
Lwów jest i, gdzie i \in N, oraz i<=n. Ja wnioskuje, że jest n miejsc, dla lwów w \frac{n}{2} klatkach. Wydaje mi się, że to czy na początku mamy parzystą, czy nieparzystą liczbę klatek, w tym przypadku akurat nie ma znaczenia, ponieważ nieparzysta liczba klatek, i tak daje nam parzystą liczbę miejsc.
Góra
Mężczyzna Offline
 Tytuł: Lwy w klatkach
PostNapisane: 7 lut 2015, o 16:57 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
A czy nie zakładasz implicite, że dwie kolejne klatki nie mogą być puste?
Góra
Mężczyzna Offline
 Tytuł: Lwy w klatkach
PostNapisane: 7 lut 2015, o 17:07 
Użytkownik

Posty: 10
Lokalizacja: Warszawa
Ja zakładam, że jak pomiędzy dwoma klatkami z lwami są dwie, lub więcej pustych to i tak usuwam tylko jedną z nich i tak pozostaje mi \frac{n}{2} klatek z lwami bądź bez. Następnie pozostałe klatki dzielę na miejsca i rozmieszczam lwy, których jest nie więcej niż n.
Góra
Mężczyzna Offline
 Tytuł: Lwy w klatkach
PostNapisane: 7 lut 2015, o 17:30 
Użytkownik

Posty: 954
Lokalizacja: Mazowsze
Jest to nieprawda że lwów jest nie więcej niż klatek. Bo co jak są trzy klatki, w pierwszej i trzeciej są po dwa lwy, a druga jest pusta?
Góra
Mężczyzna Offline
 Tytuł: Lwy w klatkach
PostNapisane: 7 lut 2015, o 17:34 
Użytkownik

Posty: 10
Lokalizacja: Warszawa
Masz rację, ale nie mam pomysłu jak poprawić to zadanie. Może powinienem rozważyć 2 przypadki, dla parzystej liczby klatek i nieparzystej?
Góra
Mężczyzna Offline
 Tytuł: Lwy w klatkach
PostNapisane: 7 lut 2015, o 17:35 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Ja bym zaczął od wymyślenia jakiegoś wzoru rekurencyjnego, na przykład a_n=a_{n-1}+2a_{n-2}. A jeśli chcesz sprawdzić, czy Twój wzór jest dobry, to sprawdź dla małych n. Póki co w Twoim uzasadnieniu nie rozumiem nic. Na przykład dlaczego w klatkach masz jakieś dwa rozróżnialne miejsca?
Góra
Mężczyzna Offline
 Tytuł: Lwy w klatkach
PostNapisane: 7 lut 2015, o 17:43 
Użytkownik

Posty: 10
Lokalizacja: Warszawa
Rzeczywiście wszystko to co napisałem, jest niepoprawne... Mógłbyś dać jakąś podpowiedź co do tego wzoru rekurencyjnego, bo nie mam żadnego pomysłu.
Góra
Mężczyzna Offline
 Tytuł: Lwy w klatkach
PostNapisane: 7 lut 2015, o 17:54 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Albo ostatnia klatka jest pusta, albo wkładamy do niej jednego lub dwa lwy.
Góra
Mężczyzna Offline
 Tytuł: Lwy w klatkach
PostNapisane: 7 lut 2015, o 18:40 
Użytkownik

Posty: 10
Lokalizacja: Warszawa
Rozpisałem to sobie wszystko, ale i tak mi nic nie wychodzi. Mógłbyś rozwiązać to zadanie?
Góra
Mężczyzna Offline
 Tytuł: Lwy w klatkach
PostNapisane: 7 lut 2015, o 18:47 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Mógłbym, ale nie chcę. Jeśli ostatnia klatka jest pusta, to ile jest możliwości rozmieszczania lwów we wcześniejszych klatkach?
Góra
Mężczyzna Offline
 Tytuł: Lwy w klatkach
PostNapisane: 7 lut 2015, o 19:06 
Użytkownik

Posty: 10
Lokalizacja: Warszawa
Dzięki, już umiem dokończyć to zadanie.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 13 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Umieszczanie drapieżników w klatkach.  Carlj28  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl