Kolokwium - dyskretna

[Paylinka07]

Nie ma pojęcia jak to zrobić, więc proszę o rozwiązania

1. Mamy 20 jednakowych lizaków i chcemy je rozdać czworgu dzieciom. Na ile sposobów możemy to uczynić? A jeśli chcemy, żeby każde dziecko dostało chociaż jednego lizaka

2. Ile liczb siedmiocyfrowych możemy utworzyć ze wszystkich cyfr ze zbioru \(\displaystyle{ \left\{1, 2,3, 4, 5, 6, 7 \right\}}\) tak, aby 3 i 6 stały obok siebie?

3. Ile musi być posiadaczy kart płatniczych, aby mieć pewność, że co najmniej 7 z nich ma karty chronione tym samym czterocyfrowym numerem PIN?

4. Podać kombinatoryczne uzasadnienie wzoru \(\displaystyle{ \sum_{k=0}^{l} {n \choose k} {m \choose l-k} = {n + m \choose l}}\)

5. Ile razy musimy rzucić trzema różnokolorowymi kostkami do gry, aby mieć pewność, że co najmniej 4 razy otrzymamy ten sam wynik? A jeśli kostki są takie same?

[justyskaf]

2. Parę uporządkowaną \(\displaystyle{ \{3,6\}}\) traktujemy jako jeden element. Mamy w takim razie \(\displaystyle{ 6!}\) permutacji. Mnożymy jeszcze to wszystko razy \(\displaystyle{ 2!}\) bo raz może stać pierwsza \(\displaystyle{ 3}\), a raz \(\displaystyle{ 6}\)

1. Możemy utworzyć bijekcję, dzieci traktować jako szuflady, a batoniki jako kule.
Zapisujemy \(\displaystyle{ 0|000||00|\cdots0|00}\)
|-rozdziela szuflady, liczba 0 pomiędzy |..| to liczba kul w szufladzie
Tworzymy w ten sposób ciągi o 20 zerach i 3 kreskach.
Takich ustawień jest tyle ile wyborów miejsc dla kresek bo wtedy wiemy gdzie wstawić kule (na pozostałe miejsca) czyli

\(\displaystyle{ {20+3 \choose 3} =\frac{21\cdot22\cdot23}{3!}}\)

w przypadku gdy nie dopuszczamy pudełek pustych (dzieci bez batonika) możemy zastosować liczby Stirlinga II rodzaju, czyli podział 20-zbioru na 4 bloki.

[Studentka1992]

A w drugim zadaniu nie powinno być przypadkiem tak, że liczby 3 i 6 możemy ustawić na \(\displaystyle{ 6\cdot 2}\) sposobów i trzeba jeszcze pomnożyć przez \(\displaystyle{ 5^{5}}\) bo na tyle sposobów możemy ustawić resztę liczb?

A co do zadania 3
Mamy \(\displaystyle{ 10^{4}}\) numerów PIN bo kolejność jest ważna. Zatem musi być co najmniej \(\displaystyle{ 6\cdot 10^{4}+1}\) posiadaczy żeby co najmniej 7 numerów się powtórzyło


\(\displaystyle{ \left\lceil \frac{x}{10^{4}}\right\rceil>7 \ \ \frac{x}{10^{4}}>6\ \{x>6\cdot 10^{4}}\ \{x=6\cdot 10^{4}+1}}\)

[justyskaf]

ale liczby mają być utworzone ze wszystkich cyfr więc będą permutacje, w sensie pomnożenie nie razy \(\displaystyle{ 5^5}\) tylko \(\displaystyle{ 5!}\) ale to jest to samo co napisałam wcześniej

[Vax]

4) Mamy \(\displaystyle{ n}\) mężczyzn i \(\displaystyle{ m}\) kobiet, chcemy spośród nich wybrać \(\displaystyle{ l}\) osób, które pójdą do kina. Z jednej strony można to zrobić na \(\displaystyle{ {m+n \choose l}}\) sposobów, a z drugiej strony, dla danej ilości mężczyzn (\(\displaystyle{ k}\)) które mają iść do kina musimy wybrać \(\displaystyle{ l-k}\) kobiet, więc możemy to zrobić na \(\displaystyle{ \sum_{k=0}^{l} {n \choose k}{m \choose l-k}}\) sposobów.

[kieubass]

Co do zadania pierwszego to zrobiłbym to inaczej...

Skorzystam z modelu Bolzano-Einsteina który mówi "na ile sposobów mogę rozmieszczać n-identycznych przedmiotów w k-szufladach". Zgodzisz się ze mną że dla dziecka każdy lizak jest identyczny i załóżmy też (niezbyt elegancko ), że buzie tych dzieciaczków będą tymi szufladami

Model Bolzano-Einsteina wyraża się wzorem:
\(\displaystyle{ \frac{\left( n+k-1\right)!}{n! \cdot \left( k-1\right)!}}\)

\(\displaystyle{ n}\)-liczba lizaków, \(\displaystyle{ k}\)-liczba dzieci.
\(\displaystyle{ n=20}\) \(\displaystyle{ k=4}\) i podstawiamy:

\(\displaystyle{ \frac{\left( 20+4-1\right)!}{20! \cdot \left( 4-1\right)!} = \frac{23!}{20! \cdot 3!} = \frac{21 \cdot 22 \cdot 23}{6} = \frac{21 \cdot 11 \cdot 23}{3} = 7 \cdot 11 \cdot 23=1771}\)

A teraz odpowiedź do drugiej części tego zadania:
Każde dziecko musi dostać co najmniej jednego lizaka. Więc tu żaden kłopot, jako dobry/a wujek/ciocia od razu dajemy każdemu dzieciaczkowi po lizaku coby smutno mu nie było I martwimy się resztą lizaków i tą resztę wykorzystujemy we wzorze Bolzano-Einsteina
zatem teraz \(\displaystyle{ 20-4=16=n}\), \(\displaystyle{ k=4}\) i podstawiamy:

\(\displaystyle{ \frac{\left( 16+4-1\right)!}{16! \cdot \left( 4-1\right)!} = \frac{19!}{16! \cdot 3!} = \frac{17 \cdot 18 \cdot 19}{6} = 17 \cdot 3 \cdot 19=969}\)

I oto koniec tego zadania
Pozdrawiam

[justyskaf]

co do pierwszej części tego zadania to tak samo zrobiłam, tylko nie napisałam że z tw B-E, tylko je po prostu wyprowadziłam ale o to samo chodzi

a w drugiej części rzeczywiście fajny pomysł, nie wpadłam na to

pozdrawiam