Matematyka dyskretna

[Thecreativ]

Prosił bym o pomoc w trzech zadaniach a mianowicie :

Zadnie 1. Na ile sposobów można rozłożyć 20 kul do 5 szufladek tak aby w pierwszej i ostatniej
było nie więcej
niż 6 kul?

Zadanie 2. Na zawodach sportowych grupa 70 zawodników strzelała po 5 razy do tarczy z polami
o numerach od 1 do 5, nie było żadnych niecelnych strzałów. Pokazać że co najmniej 4 z nich
uzyskało taki sam wynik. Czy można byłoby to stwiedzić gdyby zawodnicy pudłowali?

Zadanie 3. Ile jest liczb całkowitych dodatnich nie wiekszych niz 7000 które nie sa podzielne ani
przez 7, ani przez 10, ani przez 25?
• a) nie sa podzielne ani przez 7, ani przez 10
• b) nie sa podzielne ani przez 8, ani przez 10
• c) nie sa podzielne ani przez 7, ani przez 10, ani przez 25
• d) nie sa podzielne ani przez 8, ani przez 9, ani przez 25

[MrCommando]

1) Wynik zależy od tego, czy kulki rozróżniamy czy nie. Niech \(\displaystyle{ x_i}\) oznacza liczbę kulek w \(\displaystyle{ i}\)-tej szufladzie dla \(\displaystyle{ i\in[5]}\). Szukamy zatem liczby rozwiązań równania \(\displaystyle{ x_1+x_2+x_3+x_4+x_5=20}\) w liczbach całkowitych nieujemnych, przy czym zakładamy, że \(\displaystyle{ x_1, x_5 \leq 6}\). Drugi krok zostawiam Tobie. Podpowiem, że od wszystkich rozwiązań tego równania trzeba odjąć te, dla których co najmniej jedna z liczb \(\displaystyle{ x_1, x_5}\) jest większa od \(\displaystyle{ 6}\) (np. zasada włączeń i wyłączeń). Jeżeli kulki rozróżniamy, to wynik na koniec trzeba pomnożyć przez \(\displaystyle{ 20!}\).

2) Skoro każdy strzał był trafiony, to wynik każdego z zawodników jest liczbą naturalną nie mniejszą niż \(\displaystyle{ 5}\) i nie większą niż \(\displaystyle{ 25}\). Zatem mamy dokładnie \(\displaystyle{ 21}\) możliwych wyników. Gdyby co najwyżej \(\displaystyle{ 3}\) osoby uzyskały ten sam wynik, to wtedy liczba wszystkich osób byłaby nie większa niż \(\displaystyle{ 3\cdot21=65}\), tak jednak nie jest, stąd mamy sprzeczność. Można też powołać się na zasadę szufladkową Dirichleta - szufladkami będą możliwe wyniki, a kulkami zawodnicy. Umieszczamy \(\displaystyle{ 70}\) kulek w \(\displaystyle{ 21}\) szufladkach, zatem na mocy ZSD istnieje taka szufladka, w której jest \(\displaystyle{ \lceil\frac{70}{21}\rceil=4}\) kulek. Gdyby pudłowali, to sprawa wygląda trochę inaczej, wtedy wynik każdego z zawodników byłby jakąś liczbą nieujemną nie większą niż \(\displaystyle{ 25}\) (i co z tego wynika?).

3) Skorzystaj z zasady włączeń i wyłączeń i praw de Morgana dla zbiorów. Swoją drogą jakieś własne próby?