Lwy w klatkach
-
- Użytkownik
- Posty: 10
- Rejestracja: 7 lut 2015, o 11:06
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 6 razy
Lwy w klatkach
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 \(\displaystyle{ n}\) klatek, to \(\displaystyle{ \frac{n}{2}}\) jest pustych, więc pozostaje w sumie \(\displaystyle{ \frac{n}{2}}\) klatek pełnych (z jednym, lub dwoma lwami), lub pustych. Teraz każdą klatkę możemy rozdzielić na \(\displaystyle{ 2}\) miejsca, więc mamy \(\displaystyle{ n}\) miejsc. Lwów jest nie więcej niż miejsc, więc jest ich co najwyżej \(\displaystyle{ n}\). Teraz musimy zsumować wszystkie możliwości zależne od liczby lwów, a tych jest \(\displaystyle{ \sum_{i=0}^{n} {n+i-1 \choose i}}\). Czy mój tok rozumowania jest dobry, czy robię gdzieś błąd?
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 \(\displaystyle{ n}\) klatek, to \(\displaystyle{ \frac{n}{2}}\) jest pustych, więc pozostaje w sumie \(\displaystyle{ \frac{n}{2}}\) klatek pełnych (z jednym, lub dwoma lwami), lub pustych. Teraz każdą klatkę możemy rozdzielić na \(\displaystyle{ 2}\) miejsca, więc mamy \(\displaystyle{ n}\) miejsc. Lwów jest nie więcej niż miejsc, więc jest ich co najwyżej \(\displaystyle{ n}\). Teraz musimy zsumować wszystkie możliwości zależne od liczby lwów, a tych jest \(\displaystyle{ \sum_{i=0}^{n} {n+i-1 \choose i}}\). Czy mój tok rozumowania jest dobry, czy robię gdzieś błąd?
Ostatnio zmieniony 7 lut 2015, o 15:14 przez Vxst, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Lwy w klatkach
Skąd wnioskujesz, że jest \(\displaystyle{ n}\) lwów?
Tak samo nie widzę uzasadnienia dla tezy, że \(\displaystyle{ n}\) jest liczbą parzystą.
Tak samo nie widzę uzasadnienia dla tezy, że \(\displaystyle{ n}\) jest liczbą parzystą.
-
- Użytkownik
- Posty: 10
- Rejestracja: 7 lut 2015, o 11:06
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 6 razy
Lwy w klatkach
Lwów jest \(\displaystyle{ i}\), gdzie \(\displaystyle{ i \in N}\), oraz \(\displaystyle{ i<=n}\). Ja wnioskuje, że jest n miejsc, dla lwów w \(\displaystyle{ \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.
-
- Użytkownik
- Posty: 10
- Rejestracja: 7 lut 2015, o 11:06
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 6 razy
Lwy w klatkach
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 \(\displaystyle{ \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ż \(\displaystyle{ n}\).
-
- Użytkownik
- Posty: 939
- Rejestracja: 26 gru 2009, o 17:38
- Płeć: Mężczyzna
- Lokalizacja: Mazowsze
- Podziękował: 5 razy
- Pomógł: 228 razy
Lwy w klatkach
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?
-
- Użytkownik
- Posty: 10
- Rejestracja: 7 lut 2015, o 11:06
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 6 razy
Lwy w klatkach
Masz rację, ale nie mam pomysłu jak poprawić to zadanie. Może powinienem rozważyć 2 przypadki, dla parzystej liczby klatek i nieparzystej?
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Lwy w klatkach
Ja bym zaczął od wymyślenia jakiegoś wzoru rekurencyjnego, na przykład \(\displaystyle{ 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 \(\displaystyle{ n.}\) Póki co w Twoim uzasadnieniu nie rozumiem nic. Na przykład dlaczego w klatkach masz jakieś dwa rozróżnialne miejsca?
-
- Użytkownik
- Posty: 10
- Rejestracja: 7 lut 2015, o 11:06
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 6 razy
Lwy w klatkach
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.
-
- Użytkownik
- Posty: 10
- Rejestracja: 7 lut 2015, o 11:06
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 6 razy
Lwy w klatkach
Rozpisałem to sobie wszystko, ale i tak mi nic nie wychodzi. Mógłbyś rozwiązać to zadanie?
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Lwy w klatkach
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?