zadanie do matury

[Feniks]

Mając do dyspozycji n klatek ustawionych szeregowo, chcemy rozmieścić k nierozróżnialnych lwów tak, by w każdej klatce był co najwyżej jeden lew i by żadne lwy nie sąsiadowały ze sobą. Niech g(n,k) bedzie liczbą sposobów rozmieszczania lwów zgodnie z podanymi warunkami. Udowodnic ze
(1) g(2k - 1,k) = 1
(2) g(n,k) = 0 gdy n < 2k - 1
(3) g(n,1) = n
(4) g(n,k) = g(n - 2,k - 1) + g(n - 1,k), dla k 2
(5) g(6,3) = 4
(6) g(2k,k) = k + 1


moze ma ktos jakas sugestię jak to rozwiazac
z gory dzieki

[Sylwek]

1) Zaczynając rozmieszczenie od pierwszej klatki "najciaśniejsze" rozmieszczenie lwów to umieszczenie ich w klatkach: 1,3,5, ..., 2k-1, ale że klatek jest dokładnie 2k-1, to jest to jedyne możliwe rozmieszczenie

2) Analogicznie jak wyżej, tylko braknie klatek

3) Jednego lwa możemy umieścić w każdej z n klatek, gdyż nie przeczy to warunkom zadania.

4) Nie wiem dla jakiego k...

5) Niech klatki będą oznaczone ABCDEF. Jeśli w klatce B jest lew, to pozostałe musimy umieścić w klatkach D i F. Jeśli w klatce E jest lew, to pozostałe musimy umieścić w klatkach A i C. Jeśli w klatkach B i E nie ma lwów, to muszą być w klatkach A i F. Trzeciego lwa możemy umieścić w C lub D. Łącznie 4 możliwości.

6) Rozpatrzmy ustawienia od lewej strony. Pierwsze z ustawień to: 1,3,5, ..., 2k-1. Niech ruchem będzie możliwość przesunięcia lwa w prawą stronę. Dla danego ustawienia nie będącego ustawieniem przedstawiającym ustawieniem lwów skrajnie od prawej strony możemy zrobić tylko jeden ruch. Czyli możemy zrobić k ruchów. Dołączając początkowe ustawienie mamy k+1.

[bosz]

5 wynika z 6 dla k = 3 wiec nie warto sobie glowy zawracac 5.
6 rozwiazales dobrze.. ale mysle ze bwrdziej poglodowo jest
gdy zamiast umieszczac lwy w klatkach .. umiescimy klatki miedzy lwami.

A wiec stawiamy k klatek z k lwami.. pomiedzy nie musimy wstawic k-1 klatek
zostaje mam owa ostatnia..
poniewaz klatki sa nierozroznialne i lwy tez.. wiec mona dodatkowa klatke postawic przed pierwszym lwem , przed drugim.. itd.. az do k.. albo mozna tez za k lwem stad mamy k+1 sposobow.

[UNIX_admin]

sugeruje korzystac z opcji "Szukaj". takie zadanie bylo juz rozwiazywane, chyba nawet wielokrotnie, a poza tym problem jest "standardowy" wiec rozwiazanie mozna znalezc w wielu miejscach.