Matematyka dyskretna

alekksis · Post autor: **alekksis** » 11 cze 2012, o 12:45

1. W pudełku mamy dziesięć ponumerowanych kul. Z pudełka tego wyjmujemy trzy kule, po czym wrzucamy je z powrotem. Ile razy musimy powtorzyc tę czynność, aby mieć pewność , że co najmniej trzy razy wyciągneliśmy kule z tymi samymi numerami?

2. Jak kombinatorycznie uzasadnić zależność rekurencyjną dla współczynnika dwumianowego. Rozumiem o co w niej chodzi, wiem, że jeżeli ustalimy pewien element zbioru n-elementowego to przy wyborze k-elem. podzbiorów tego zbioru mamy ich dwie kategorie, w jednym przypadku element może być z danym podzbiorze, a w drugim nie. Ale mam problem z uzasadnieniem treścią jakiegoś przykładu kombinatorycznego.

Proszę o pomoc !

silvaran · Post autor: **silvaran** » 11 cze 2012, o 13:16

1. Zakładam, że trzy razy wyciągnęliśmy kule z tymi samymi numerami oznacza, że w jednym losowaniu trzeci raz mamy trzy te same numery.

Więc najpierw policz na ile sposobów można wybrać trzy kule z dziesięciu

Wyjdzie Ci jakaś liczba n. Teraz zobacz, że jeśli n razy będziesz losował, to może się jakaś trójka powtórzyć, a może być tak, że wszystkie będą różne. Więc będziesz musiał wylosować jeszcze raz, żeby mieć pewność że przynajmniej jedna trójka powtórzyła się przynajmniej dwa razy. I zastosuj to do swojego przypadku

alekksis · Post autor: **alekksis** » 11 cze 2012, o 14:04

Czyli mam 120 sposobów wybrania tej trójki.
Żebym miała 3 razy tą samą trójkę muszę to powtarzać minimum 3 razy, przy szczęściu, że wyciągnę to samo, ale co dalej? Nie widzę jakoś innych opcji,

norwimaj · Post autor: **norwimaj** » 12 cze 2012, o 14:28

alekksis pisze: Żebym miała 3 razy tą samą trójkę muszę to powtarzać minimum 3 razy, przy szczęściu, że wyciągnę to samo, ale co dalej?

Ale interesuje Cię tu przypadek pesymistyczny a nie optymistyczny. Możesz nawet \(\displaystyle{ 120}\) razy losować i za każdym razem wyciągnąć inną trójkę. Ale jak wylosujesz \(\displaystyle{ 121}\) razy, to któraś trójka się powtórzy, o czym mówi zasada szufladkowa. A ile razy trzeba wylosować, żeby jakaś trójka musiała być co najmniej trzy razy?

W drugim nie bardzo rozumiem, w czym problem. Masz klasę złożoną z \(\displaystyle{ n-1}\) uczniów i jednej uczennicy. Na ile sposobów można spośród nich wytypować osoby, które otrzymają promocję do następnej klasy, jeśli ministerstwo zaleca zachować odsetek zdających równy \(\displaystyle{ \frac kn}\)?