7090996912

16 W. Guzicki: Zadania z kombinatoryki

19.    Ile jest liczb od 1 do 1000 włącznie dających resztę 0 lub 1 przy dzieleniu przez 7?

Rozwiązanie. Zauważmy, że 994 = 7 • 142 oraz 1001 = 7 ■ 143. Zatem wśród liczb od 1 do 1000 włącznie znajdują się 142 liczby podzielne przez 7 i 143 liczby dające resztę 1 przy dzieleniu przez 7. Liczb, o które chodzi w zadaniu, jest zatem 142 + 143 = 285.

20.    Ile jest liczb od 1 do 1000 włącznie podzielnych przez 3 lub przez 5?

Rozwiązanie. W zbiorze liczb od 1 do 1000 włącznie wyróżnimy dwa podzbiory:

•    zbiór A składa się z liczb podzielnych przez 3,

•    zbiór B składa się z liczb podzielnych przez 5.

Wówczas — tak jak w zadaniu 1 — pokazujemy, że |,A| = 333 (gdyż 1000 = 3 ■ 333 + 1) oraz |R| = 200 (bo 1000 = 5 • 200). Następnie zauważamy, że zbiór A fi B składa się z liczb podzielnych przez 15 (bo liczby 3 i 5 są względnie pierwsze). Zatem \A fi B\ = 66 (bo 1000 = 15 ■ 66 + 10). Stąd wynika, że

\A\JB\ = \A\ + \B\ - \A n B\ = 333 + 200 - 66 = 467.

21.    Ile jest liczb od 1 do 1000 włącznie podzielnych przez 3 i jednocześnie niepodzielnych przez 5? Rozwiązanie. Niech zbiory A i B będą określone tak jak w poprzednim zadaniu. Wówczas A fi B C A, skąd wynika, że

\A \ B\ = \A \ {A D B)| = \A\ -\A n B\ = 333 - 66 = 267.

22.    Ile jest liczb od 1 do 1000 włącznie podzielnych przez 3, 5 lub 7?

Rozwiązanie. Tym razem wśród liczb od 1 do 1000 włącznie wyróżniamy trzy podzbiory:

•    zbiór A składa się z liczb podzielnych przez 3,

•    zbiór B składa się z liczb podzielnych przez 5,

•    zbiór C składa się z liczb podzielnych przez 7.

Tak jak poprzednio, |j4| = 333, |B| = 200 oraz \A fi B\ = 66. Następnie |C| = 142, \A Cl C\ — 47, \B fi C| = 28 oraz \ A D B fi C\ = 9. Zatem:

\AuBuC\ = |A| + |R| + \C\ - |i4nB| - \A n C\ - \B n C\ + \A U B U C\ =

= 333 + 200 + 142 - 66 - 47 - 28 + 9 = 675 - 141 + 9 = 543.

5. Reguła mnożenia

W tym rozdziale zajmiemy się zadaniami, w których wykorzystamy regułę mnożenia. Niektóre z tych zadań można rozwiązać inaczej, nas jednak interesują rozwiązania ilustrujące sposób użycia reguły mnożenia.

23.    Na ile sposobów można wybrać delegację parlamentu, w skład której ma wchodzić jeden poseł i jeden senator? Dla przypomnienia: Sejm składa się z 460 posłów, Senat ze 100 senatorów i żaden senator nie może jednocześnie być posłem.

Rozwiązanie. W rozwiązaniu tego zadania skorzystamy z reguły mnożenia. Zastosowanie reguły mnożenia będzie zazwyczaj polegało na pokazaniu, w jaki sposób za pomocą dobrze opisanych czynności można skonstruować wszystkie obiekty, które mamy zliczyć. Ze względów dydaktycznych bardzo pouczające jest wskazanie wyraźnie wszystkich tych czynności i zliczenie wyników każdej z nich.

W tym zadaniu delegację parlamentu wybieramy za pomocą dwóch czynności:

•    pierwsza czynność polega na wybraniu jednego posła; ta czynność kończy się jednym z 460 wyników,

•    druga czynność polega na wybraniu jednego senatora; ta czynność, niezależnie od wyniku pierwszej czynności, kończy się jednym ze 100 wyników.

Reguła mnożenia mówi teraz, że wykonanie obu tych czynności, jedna po drugiej, kończy się jednym z 460 • 100 = 46000 wyników. Tyle delegacji możemy utworzyć.

24.    Rzucamy kostką 2 razy, zapisując wyniki w kolejności rzutów. W ten sposób wynikiem doświadczenia jest para liczb od 1 do 6. Ile wyników tej postaci można uzyskać?

Rozwiązanie. Wykonujemy dwie czynności:

Warszawa, 19-20 października 2013 r.