Matematyka.pl

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

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.