1. Na polce stoi 12 ksiazek. Na ile sposobow mozna wybrac 5 ksiazek z polki tak, aby nie zabierac zadnych dwoch stojacych wczesniej obok siebie.
2. Przy Okraglym stole siedzi 12 Rycerzy. W czasie obrad kazdych dwoch siedzacych obok siebie poklocilo sie. Krol Artur musi poslac w misje 5 Rycerzy. Na ile sposobow moze to zrobic, jesli nie chce, aby wsrod wyslanych byli jacys klocacy sie Rycerze?
Bede zniezmiernie wdzieczna za rozwiazanie ktoregos chociaz z tych dwoch zadan. Oczywiscie nie pogardzilabym jakimis komentarzami co sie skad wzielo
ustawienia ksiazek i ludzi
-
jovante
- Użytkownik
- Posty: 204
- Rejestracja: 23 cze 2007, o 14:32
- Płeć: Mężczyzna
- Lokalizacja: Siedlce
- Pomógł: 56 razy
ustawienia ksiazek i ludzi
Ad.1.
Z powodów, które staną się jasne przy rozwiązywaniu podpunktu 2 pozwolę sobie nieco uogólnić to zadanie, mianowicie: mamy n obiektów (książek) i wybieramy k z nich tak, aby nie wziąć żadnych dwóch stojących obok siebie.
Skonstruujmy następujący ciąg zerojedynkowy:
1. Ustawiamy k jedynek: \(\displaystyle{ 1,1,...,1}\)
2. Pomiędzy te jedynki wstawiamy k-1 zer: \(\displaystyle{ 1,0,1,0,...,0,1}\)
3. Pozostało nam n-2k+1 elementów, które możemy wstawić w dowolne miejsce symbolizowane przez zera jak również na początku i końcu na \(\displaystyle{ {n-k+1}\choose{n-2k+1}}\) sposobów, co stanowi wynik (w naszym konkretnym przypadku równy 56).
Ad.2.
Ponieważ mamy okrągłą półkę z książkami, to musimy tylko wyeliminować z ad.1. ciągi, które rozpoczynają się i kończą jedynką. Prowadzi to do wzoru:
\(\displaystyle{ {{n-k+1}\choose{n-2k+1}}-{{n-k-1}\choose{n-2k+1}}={{n-k}\choose{k}}\frac{n}{n-k}}\)
W naszym konkretnym przypadku otrzymujemy wynik 36.
Z powodów, które staną się jasne przy rozwiązywaniu podpunktu 2 pozwolę sobie nieco uogólnić to zadanie, mianowicie: mamy n obiektów (książek) i wybieramy k z nich tak, aby nie wziąć żadnych dwóch stojących obok siebie.
Skonstruujmy następujący ciąg zerojedynkowy:
1. Ustawiamy k jedynek: \(\displaystyle{ 1,1,...,1}\)
2. Pomiędzy te jedynki wstawiamy k-1 zer: \(\displaystyle{ 1,0,1,0,...,0,1}\)
3. Pozostało nam n-2k+1 elementów, które możemy wstawić w dowolne miejsce symbolizowane przez zera jak również na początku i końcu na \(\displaystyle{ {n-k+1}\choose{n-2k+1}}\) sposobów, co stanowi wynik (w naszym konkretnym przypadku równy 56).
Ad.2.
Ponieważ mamy okrągłą półkę z książkami, to musimy tylko wyeliminować z ad.1. ciągi, które rozpoczynają się i kończą jedynką. Prowadzi to do wzoru:
\(\displaystyle{ {{n-k+1}\choose{n-2k+1}}-{{n-k-1}\choose{n-2k+1}}={{n-k}\choose{k}}\frac{n}{n-k}}\)
W naszym konkretnym przypadku otrzymujemy wynik 36.