Lwy w klatkach

Vxst · Post autor: **Vxst** » 7 lut 2015, o 11:25

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?

norwimaj · Post autor: **norwimaj** » 7 lut 2015, o 11:30

Skąd wnioskujesz, że jest \(\displaystyle{ n}\) lwów?

Tak samo nie widzę uzasadnienia dla tezy, że \(\displaystyle{ n}\) jest liczbą parzystą.

Vxst · Post autor: **Vxst** » 7 lut 2015, o 11:41

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.

norwimaj · Post autor: **norwimaj** » 7 lut 2015, o 15:57

A czy nie zakładasz implicite, że dwie kolejne klatki nie mogą być puste?

Vxst · Post autor: **Vxst** » 7 lut 2015, o 16:07

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}\).

jarek4700 · Post autor: **jarek4700** » 7 lut 2015, o 16:30

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?

Vxst · Post autor: **Vxst** » 7 lut 2015, o 16:34

Masz rację, ale nie mam pomysłu jak poprawić to zadanie. Może powinienem rozważyć 2 przypadki, dla parzystej liczby klatek i nieparzystej?

norwimaj · Post autor: **norwimaj** » 7 lut 2015, o 16:35

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?

Vxst · Post autor: **Vxst** » 7 lut 2015, o 16:43

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.

norwimaj · Post autor: **norwimaj** » 7 lut 2015, o 16:54

Albo ostatnia klatka jest pusta, albo wkładamy do niej jednego lub dwa lwy.

Vxst · Post autor: **Vxst** » 7 lut 2015, o 17:40

Rozpisałem to sobie wszystko, ale i tak mi nic nie wychodzi. Mógłbyś rozwiązać to zadanie?

norwimaj · Post autor: **norwimaj** » 7 lut 2015, o 17:47

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?

Vxst · Post autor: **Vxst** » 7 lut 2015, o 18:06

Dzięki, już umiem dokończyć to zadanie.