Podzbiory zbioru skończonego (treść podstawowa)

W tym rozdziale zajmiemy się podzbiorami zbioru skończonego.

Podzbiory dwuelementowe zbioru skończonego

Przykład 1

Obliczymy, na ile sposobów można wybrać dwóch graczy spośród 7 zawodników.
Oznaczmy zawodników przez z1,z2,z3,z4,z5,z6,z7.

  • sposób I

Wypisujemy wszystkie możliwe do wybrania pary graczy, czyli dwuelementowe podzbiory siedmioelementowego zbioru z1,z2,z3,z4,z5,z6,z7. Zapisujemy je tak, aby wskaźnik pierwszego wypisanego zawodnika był mniejszy od wskaźnika drugiego z nich (w ten sposób unikniemy powtórzeń).
Wtedy

  • zawodnika z1 przypiszemy do sześciu zawodników: {z1, z2}, {z1, z3}, {z1, z4}, {z1, z5}, {z1, z6},{z1, z7},

  • zawodnika z2 przypiszemy do pięciu zawodników: {z2, z3}, {z2, z4}, {z2, z5}, {z2, z6},{z2, z7},

  • zawodnika z3 przypiszemy do czterech zawodników: {z3, z4}, {z3, z5}, {z3, z6},{z3, z7},

  • zawodnika z4 przypiszemy do trzech zawodników: {z4, z5}, {z4, z6},{z4, z7},

  • zawodnika z5 przypiszemy do dwóch zawodników: {z5, z6},{z5, z7},

  • zawodnika z6 przypiszemy do jednego zawodnika: {z6, z7}.

Zatem wszystkich możliwych par jest 6+5+4+3+2+1=21.

  • sposób II

Wypiszmy pary zawodników, stosując metodę tabeli. Odrzucamy pola, które nie opisują takiej pary.

Tabela. Dane
z1
z2
z3
z4
z5
z6
z7
z1
{z1, z2}
{z1, z3} 
z1, z4}
{z1, z5}
{z1, z6}
{z1, z7}
z2
{z1, z2}
{z2, z3}
{z2, z4}
{z2, z5}
{z2, z6}
{z2, z7}
z3
{z1, z3}
{z2, z3}
{z3, z4}
{z3, z5}
{z3, z6}
{z3, z7}
z4
{z1, z4}
{z2, z4}
{z3, z4}
{z4, z5}
{z4, z6}
{z4, z7}
z5
{z1, z5}
{z2, z5}
{z3, z5}
{z4, z5}
{z5, z6}
{z5, z7}
z6
{z1, z6}
{z2, z6}
{z3, z6}
{z4, z6}
{z5, z6}
{z6, z7}
z7
{z1, z7}
{z2, z7}
{z3, z7}
{z4, z7}
{z5, z7}
{z6, z7}

W tabeli mamy więc wypełnione 6⋅7=42 pola. Zauważmy, że każda para została tu wypisana dokładnie dwa razy. Oznacza to, że wszystkich par jest 6∙72=21.

  • sposób III

Oznaczmy przez x liczbę wszystkich możliwych par graczy.
Liczbę wszystkich możliwych uporządkowanych par graczy możemy obliczyć następującymi dwoma sposobami.

  • Do każdego z siedmiu zawodników dobieramy drugiego do pary na 6 sposobów. W ten sposób otrzymaliśmy 6⋅7 par uporządkowanych.

  • W każdej z x par graczy możemy na dwa sposoby ustalić kolejność, co daje 2x wszystkich uporządkowanych par graczy.

Otrzymujemy więc równość

2x=6⋅7

stąd

x=6⋅72=21

Uwaga. Wykorzystując podobne rozumowanie, pokażemy, że liczba wszystkich dwuelementowych podzbiorów, które można wybrać ze zbioru A=a1,a2,...,an, liczącego n elementów jest równa

n⋅n-12

Jeśli przez x oznaczymy liczbę wszystkich możliwych podzbiorów dwuelementowych zbioru A, to liczba wszystkich możliwych uporządkowanych par elementów tego zbioru jest z jednej strony równa

n⋅n-1

bo do każdego z n elementów drugi do pary możemy dobrać na n-1 sposobów,
a z drugiej strony – jest równa

2x

bo w każdym z x dwuelementowych podzbiorów zbioru A możemy na dwa sposoby ustalić kolejność elementów.
Otrzymujemy więc równość

2x=n⋅n-1

stąd

x=n⋅n-12.
Przykład 2

Korzystając ze wzoru na liczbę dwuelementowych podzbiorów zbioru n-elementowego, obliczymy, że:

  • dwóch graczy spośród 11 zawodników można wybrać na 11⋅102=55 sposobów,

  • liczba wszystkich meczów w turnieju, do którego zgłosiło się 9 drużyn i każda drużyna ma rozegrać z każdą inną dokładnie jeden mecz, jest równa 9⋅82=36,

  • dwuosobową delegację z klasy liczącej 25 uczniów można wybrać na 25⋅242=300 sposobów.

Przykład 3

  1. Obliczymy, ile przekątnych ma jedenastokąt wypukły.
    Rozpatrzmy wszystkie możliwe odcinki, które powstały z połączenia par wierzchołków jedenastokąta wypukłego. Jest ich łącznie
    11⋅102=55.Każdy z tych odcinków jest albo bokiem tego jedenastokąta, albo jego przekątną. Ponieważ boków jest 11, więc przekątnych jest
    55-11=44.

  2. Pokażemy, że liczba wszystkich przekątnych n- kąta wypukłego, jest równa

n⋅n-32

Wszystkich możliwych odcinków, które powstały z połączenia par wierzchołków n-kąta wypukłego jest n⋅n-12. Każdy z tych odcinków jest albo przekątną tego wielokąta, albo jego bokiem. Ponieważ boków jest n, więc przekątnych jest

n⋅n-12-n=n2-n-2n2=n2-3n2=n⋅n-32
Przykład 4

Do szkolnego turnieju halowej piłki nożnej zgłosiło się 6 drużyn. Turniej rozegrano systemem „każdy z każdym”, bez rewanżów. W każdym meczu przyznawano punkty według zasady: w przypadku remisu obie drużyny otrzymują po 1 punkcie, a w meczu rozstrzygniętym zwycięzca otrzymuje 3 punkty, a przegrany – 0 punktów. Po zakończeniu turnieju okazało się, że drużyny uczestniczące w turnieju zdobyły w sumie 37 punktów. Ustalimy, ile meczów podczas tego turnieju zakończyło się wynikiem remisowym.
W turnieju rozgrywanym systemem „każdy z każdym”, bez rewanżów meczów jest tyle, ile wszystkich możliwości dobrania drużyn w pary. W przypadku tego szkolnego turnieju liczba meczów to liczba dwuelementowych podzbiorów zbioru sześcioelementowego, czyli

6⋅52=15

Oznaczmy przez x liczbę meczów remisowych w tym turnieju. Wtedy liczba meczów rozstrzygniętych to 15-x.
Ponieważ każdy mecz remisowy wnosił do ogólnej sumy 2 punkty, a mecz rozstrzygnięty – 3 punkty, więc otrzymujemy równanie

2x+3⋅15-x=37

Stąd

2x+45-3x=37

a więc

x=8

Oznacza to, że 8 meczów w tym turnieju zakończyło się wynikiem remisowym.

Przykład 5

Obliczymy, ile jest wszystkich wyników siedmiokrotnego rzutu monetą, w których dokładnie dwa razy wypadł orzeł.
Ponumerujemy rzuty od 1 do 7. Dwa z tych numerów odpowiadają wyrzuceniu orła. Jest 7⋅62=21 możliwości wyboru dwóch numerów z siedmiu, co oznacza, że jest 21 wszystkich wyników siedmiokrotnego rzutu monetą, w których dokładnie dwa razy wypadł orzeł.

i6H8JsFpVm_d5e414
Przykład 6

Obliczymy:

  1. ile jest trzycyfrowych liczb naturalnych, w których cyfra jedności jest mniejsza od cyfry dziesiątek.
    Ponieważ w rzędzie setek takiej liczby trzycyfrowej może być zapisana dowolna cyfra różna od zera, więc możemy ją wybrać na 9 sposobów.
    Zauważmy teraz, że jeżeli ze zbioru cyfr {0, 1, 2, …, 9} wybierzemy dwuelementowy podzbiór, to cyfry w ten sposób wybrane można na jeden sposób zapisać w kolejności malejącej. Zatem każdemu takiemu podzbiorowi można wzajemnie jednoznacznie przyporządkować liczbę dwucyfrową, której cyfra jedności jest mniejsza od cyfry dziesiątek.
    Jeżeli np. wybierzemy podzbiór {2, 5}, to taką liczbą jest 52, a dla liczby 83 takim podzbiorem jest {3, 8}.
    Oznacza to, że liczb dwucyfrowych, w których cyfra jedności jest mniejsza od cyfry dziesiątek jest dokładnie tyle, ile dwuelementowych podzbiorów dziesięcioelementowego zbioru cyfr {0, 1, 2, …, 9}, czyli
    10⋅92=45.Ponieważ kolejnych wyborów dokonujemy niezależnie, więc korzystając z reguły mnożenia, stwierdzamy, że liczb trzycyfrowych, w których cyfra jedności jest mniejsza od cyfry dziesiątek, jest
    9⋅45=405

  2. ile jest czterocyfrowych liczb naturalnych, spełniających jednocześnie trzy następujące warunki:

  • w zapisie tej liczby nie występuje cyfra 0,

  • cyfra setek jest większa od cyfry tysięcy,

  • cyfra jedności jest większa od cyfry dziesiątek.

Liczbę czterocyfrową, spełniającą warunki zadania, rozdzielamy na dwie dwucyfrowe, przy czym podział jest między cyfrą setek a cyfrą tysięcy.
Otrzymane liczby dwucyfrowe mają spełniać dwa warunki: w ich zapisie nie występuje cyfra 0, cyfra jedności jest większa od cyfry dziesiątek.
Rozumując podobnie, jak w podpunkcie a), zauważamy, że liczb dwucyfrowych, w których zapisie nie występuje 0 i cyfra jedności jest większa od cyfry dziesiątek, jest dokładnie tyle, ile dwuelementowych podzbiorów dziewięcioelementowego zbioru {1, 2, …, 9}. Oznacza to, że jest ich

9⋅82=36

Wobec tego dwie pierwsze cyfry liczby czterocyfrowej spełniającej warunki zadania można zapisać na 36 sposobów i dwie ostatnie również na 36 sposobów, zatem liczb czterocyfrowych, które spełniają jednocześnie podane trzy warunki, jest

36⋅36=1296
Przykład 7

W klasie jest 34 uczniów, przy czym chłopców jest o 6 więcej niż dziewczynek. Obliczymy, na ile sposobów można wybrać z tej klasy czteroosobową delegację, w której znajdą się dokładnie dwie dziewczynki.
Ponieważ delegacja jest czteroosobowa, więc oprócz dwóch dziewczynek muszą się w niej znaleźć jeszcze dwaj chłopcy.
Obliczamy, że dziewczynek jest w tej klasie 14, a chłopców jest 20.
Parę dziewczynek z tej klasy wybierzemy zatem na14⋅132=91 sposobów, a parę chłopców – na 20⋅192=190 sposobów.
Wyborów tych dokonujemy niezależnie, zatem, korzystając z reguły mnożenia, obliczamy, że wszystkich możliwych czteroosobowych delegacji z tej klasy, w której znajdą się dokładnie dwie dziewczynki, jest

91⋅190=17290.
Przykład 8

W pewnej grze losowej zakreślamy 4 liczby wybrane ze zbioru {1, 2, 3, …, 24, 25}. Wybrane liczby są następnie porównywane z czterema wylosowanymi z tego samego zbioru przez maszynę losującą. Ile jest możliwości zakreślenia takich 4 liczb, wśród których dokładnie dwie będą trafione?
Z treści zadania wynika, że dwie zakreślone liczby miały być trafione, czyli były w zbiorze 4 wylosowanych, a pozostałe dwie zakreślone były w zbiorze 21 niewylosowanych.
Dwie wylosowane liczby możemy trafić na 4⋅32=6 sposobów, a pozostałe dwie możemy wybrać na 21⋅202=210 sposobów. Oznacza to, że wszystkich możliwości zakreślenia takich 4 liczb, wśród których dokładnie dwie będą trafione jest

210⋅6=1260
Przykład 9

Proste k i l są równoległe. Na prostej k zaznaczono 4 punkty, a na prostej l – 5 punktów.

RRNjyUdnWMaIp1
Rysunek prostych równoległych k i l. Na prostej k zaznaczono 4 punkty, a na prostej l – 5 punktów.
Źródło: Zespół autorski Politechniki Łódzkiej, licencja: CC BY 3.0.

Obliczymy, ile jest wszystkich trójkątów, których wierzchołkami są trzy spośród zaznaczonych punktów.
Zauważmy, że trójkąt jest jednoznacznie wyznaczony przez ustalenie trzech jego wierzchołków.
Ponieważ trzy punkty leżące na jednej prostej nie są wierzchołkami trójkąta, więc trójkąty możemy utworzyć jedynie na dwa sposoby:

  1. na prostej k wybieramy dwa różne punkty, a do każdej takiej pary dobieramy trzeci punkt na prostej l albo

  2. na prostej l wybieramy dwa różne punkty, a do każdej takiej pary dobieramy trzeci punkt na prostej k.

Parę wierzchołków na prostej k możemy wybrać na 4⋅32=6 sposobów, a trzeci wierzchołek na prostej l na 5 sposobów. Zatem w przypadku (1) wszystkich trójkątów jest 6⋅5=30.
Parę wierzchołków na prostej l możemy wybrać na 5⋅42=10 sposobów, a trzeci wierzchołek na prostej k na 4 sposoby. Oznacza to, że w przypadku (2) wszystkich trójkątów jest 10⋅4=40.
Wobec tego wszystkich trójkątów, których wierzchołkami są trzy spośród zaznaczonych punktów, jest

30+40=70
Przykład 10

Sześć dziewcząt bierze udział w szkolnej wycieczce. Obliczymy, na ile sposobów można je zakwaterować w trzech dwuosobowych pokojach.
Zakwaterowanie rozkładamy na trzy etapy:

  1. wybieramy parę dziewczynek do pierwszego pokoju, co możemy zrobić na 6⋅52=15 sposobów,

  2. wybieramy kolejne dwie dziewczynki do drugiego pokoju, co możemy zrobić na 4⋅32=6 sposobów.

  3. kwaterujemy piątą i szóstą dziewczynkę w trzecim pokoju.

Korzystając z reguły mnożenia obliczamy, że szukanych możliwości zakwaterowania sześciu dziewcząt w trzech dwuosobowych pokojach, jest 15⋅6=90.

Przykład 11

Obliczymy, ile jest:

  1. wszystkich liczb naturalnych sześciocyfrowych, w zapisie których nie występuje zero i na dokładnie dwóch miejscach stoją cyfry nieparzyste.
    Zliczanie rozkładamy na dwa etapy:
    (1) wybór dwóch miejsc z sześciu dla cyfr nieparzystych (mamy 6⋅52=15 możliwości) oraz zapisanie tych cyfr (mamy 5⋅5=25 możliwości),
    (2) zapisanie pozostałych czterech cyfr (mamy 4⋅4⋅4⋅4=256 możliwości),
    Zatem jest 15⋅25⋅256=96000 takich liczb sześciocyfrowych.

  2. wszystkich liczb naturalnych pięciocyfrowych, w zapisie których na dokładnie dwóch miejscach stoją cyfry parzyste.

  • sposób I
    Rozróżniamy dwa przypadki:
    (1) na pierwszym miejscu zapisana jest cyfra parzysta albo
    (2) na pierwszym miejscu jest cyfra nieparzysta.
    W pierwszym przypadku: mamy 4 możliwości zapisu pierwszej cyfry, z kolejnych czterech miejsc mamy wybrać jedno dla cyfry parzystej (4 możliwości) i zapisać tę cyfrę (5 możliwości), a na każdym z pozostałych trzech miejscach zapisać cyfrę nieparzystą (5⋅5⋅5=125 możliwości). Takich liczb jest 4⋅4⋅5⋅125=10000.
    W drugim przypadku: mamy 5 możliwości zapisu pierwszej cyfry, z kolejnych czterech miejsc mamy wybrać dwa dla cyfry parzystej (4⋅32=6 możliwości) i zapisać te liczby (5⋅5=25 możliwości), a na pozostałych dwóch miejscach zapisać cyfry nieparzyste (5⋅5=25 możliwości). Takich liczb jest 5⋅6⋅25⋅25=18750.
    Oznacza to, że jest 10000+18750=28750 liczb pięciocyfrowych spełniających warunki zadania.

  • sposób II
    Wypisujemy kolejno jedna za drugą pięć cyfr, wybierając każdą cyfrę spośród dziesięciu możliwych (dopuszczamy 0 na początkowych miejscach), przy czym na dokładnie dwóch miejscach zapisujemy cyfrę parzystą.
    Mamy 5⋅42=10 możliwości wyboru dwóch miejsc dla cyfr parzystych, cyfry te możemy zapisać na 5⋅5=25 sposobów, a na pozostałych trzech miejscach cyfry nieparzyste zapiszemy na 5⋅5⋅5=125 sposobów.
    Zatem jest 10⋅25⋅125=31250 ciągów o 5 cyfrach, w których dokładnie dwie cyfry są parzyste.
    Są wśród nich takie, w których cyfra 0 zapisana jest na pierwszym miejscu. W każdym z takich ciągów na jednym z kolejnych czterech miejsc znajduje się cyfra parzysta (miejsce dla niej można wybrać na 4 sposoby, a zapisać ją – na 5 sposobów), a na trzech pozostałych –cyfry nieparzyste (można je zapisać na 5⋅5⋅5=125 sposobów). Oznacza to, że jest 4⋅5⋅125=2500 takich ciągów.
    Stąd wynika, że jest 31250-2500=28750 liczb pięciocyfrowych spełniających warunki zadania.

i6H8JsFpVm_d5e566
Przykład 12

Obliczymy:

  1. ile jest wszystkich wyników czterokrotnego rzutu sześcienną kostką do gry, w których dokładnie dwa razy wypadła parzysta liczba oczek.
    Rozpatrzmy ciąg kolejnych czterech rzutów kostką sześcienną. Zliczanie rozkładamy na dwa etapy:
    1) wybór tych dwóch z czterech numerów rzutów, dla których wypadła parzysta liczba oczek (mamy 4⋅32=6 możliwości) i rozmieszczenie parzystych liczb oczek na tych dwóch miejscach (mamy 3⋅3=9 możliwości),
    2) rozmieszczenie nieparzystych liczb oczek na pozostałych miejscach (mamy 3⋅3=9 możliwości).
    Oznacza to, że jest 6⋅9⋅9=486 wszystkich wyników czterokrotnego rzutu sześcienną kostką do gry, w których dokładnie dwa razy wypadła parzysta liczba oczek.

  2. ile jest wszystkich wyników pięciokrotnego rzutu sześcienną kostką do gry, w których dokładnie dwa razy wypadła szóstka.
    Rozpatrzmy ciąg kolejnych pięciu rzutów kostką sześcienną. Zliczanie rozkładamy na dwa etapy:
    1) wybór tych dwóch z pięciu numerów rzutów, dla których wypadła szóstka (mamy 5⋅42=10 możliwości) i rozmieszczenie dwóch szóstek na tych dwóch miejscach,
    2) rozmieszczenie innych liczb oczek na pozostałych trzech miejscach (mamy 5⋅5⋅5=125 możliwości).
    Oznacza to, że jest 10⋅125=1250 wszystkich wyników pięciokrotnego rzutu sześcienną kostką do gry, w których dokładnie dwa razy wypadła szóstka.

  3. ile jest wszystkich wyników sześciokrotnego rzutu sześcienną kostką do gry, w których wypadła dokładnie jedna jedynka i dokładnie dwie dwójki.
    Rozpatrzmy ciąg kolejnych sześciu rzutów kostką sześcienną. Zliczanie rozkładamy na trzy etapy:
    1) wybór jednego z sześciu numerów rzutów, w którym wypadła jedynka (mamy 6 możliwości) i rozmieszczenie jedynki na tym miejscu,
    2) wybór tych dwóch z pozostałych pięciu numerów rzutów, w których wypadły dwójki (mamy 5⋅42=10 możliwości) i rozmieszczenie dwójek na tych miejscach,
    3) rozmieszczenie innych liczb oczek na pozostałych trzech miejscach (mamy 4⋅4⋅4=64 możliwości).
    Oznacza to, że jest 6⋅10⋅64=3840 wszystkich wyników sześciokrotnego rzutu sześcienną kostką do gry, w których wypadła dokładnie jedna jedynka i dokładnie dwie dwójki.

Przykład 13

Obliczymy, ile jest wszystkich liczb naturalnych siedmiocyfrowych, których suma cyfr jest równa 11 i w zapisie których wszystkie cyfry są nieparzyste.

Rozróżniamy dwa przypadki:

  1. w zapisie takiej liczby jest jedna piątka i sześć jedynek albo

  2. w zapisie takiej liczby są dwie trójki i pięć jedynek.

  • W pierwszym przypadku: wybieramy jedno miejsce, na którym zapisujemy piątkę (7 możliwości), a na pozostałych sześciu miejscach zapisujemy jedynki. Zatem jest 7 takich liczb.

  • W drugim przypadku: wybieramy dwa miejsca z siedmiu, na których zapiszemy trójki (7⋅62=21 możliwości), a na pozostałych pięciu miejscach zapisujemy jedynki. Oznacza to, że jest 21 takich liczb.
    Stąd wynika, że jest 7+21=28 wszystkich liczb naturalnych siedmiocyfrowych, których suma cyfr jest równa 11 i w zapisie których wszystkie cyfry są nieparzyste.
     Uwaga. Otrzymany wynik to liczba wszystkich dwuelementowych podzbiorów zbioru ośmioelementowego
    28=8⋅72.Tyle jest np. wyników ośmiokrotnego rzutu monetą, w którym wypadły dokładnie dwa orły.
    Można pokazać, że każdy z wyników ośmiokrotnego rzutu monetą, w którym wypadły dokładnie dwa orły, odpowiada dokładnie jednej liczbie spełniającej warunki zadania i odwrotnie – każda liczba spełniająca warunki zadania odpowiada dokładnie jednemu wynikowi ośmiokrotnego rzutu monetą, w którym wypadły dokładnie dwa orły.
    Rozwiążemy w tym celu następujące zadanie.
    Ustal, ile rozwiązań w dodatnich liczbach nieparzystych ma równanie
    c1+c2+c3+c4+c5+c6+c7=11.Zauważmy, że wtedy każda liczba w ciągu c1,c2,c3,c4,c5,c6,c7 jest nieparzysta, żadna z nich nie jest większa od 10, zatem ciąg ten tworzą kolejne cyfry liczby naturalnej siedmiocyfrowej, której suma cyfr jest równa 11 i w jej zapisie wszystkie cyfry są nieparzyste.
    Ponieważ każda z liczb zapisanych po lewej stronie jest nieparzysta, więc przyjmując c1=2x1+1, c2=2x2+1, …, c7=2x7+1, można równanie zapisać w postaci
    2x1+1+2x2+1+2x3+1+2x4+1+2x5+1+2x6+1+2x7+1=11,
    gdzie każda z liczb x1,x2,...,x7 jest nieujemną liczbą całkowitą.
    Po przekształceniu otrzymujemy równanie
    x1+x2+x3+x4+x5+x6+x7=2

Naszym zadaniem jest wyznaczenie liczby wszystkich rozwiązań tego równania w nieujemnych liczbach całkowitych.
Rozpatrzmy teraz wszystkie możliwe wyniki ośmiokrotnego rzutu monetą, w których wypadły dokładnie dwa orły. Oznaczmy:
x1 - liczbę orłów uzyskanych w kolejnych rzutach do momentu, w którym wyrzucono pierwszą reszkę,
x2 - liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono pierwszą reszkę, do momentu, w którym wyrzucono drugą reszkę,
x3 - liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono drugą reszkę, do momentu, w którym wyrzucono trzecią reszkę,
x4 - liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono trzecią reszkę, do momentu, w którym wyrzucono czwartą reszkę,
x5 - liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono czwartą reszkę, do momentu, w którym wyrzucono piątą reszkę,
x6 - liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono piątą reszkę, do momentu, w którym wyrzucono szóstą reszkę,
x7 - liczbę orłów uzyskanych w kolejnych rzutach od momentu, w którym wyrzucono szóstą reszkę.
 
Zauważmy, że:

  • każdemu wynikowi takiego rzutu monetą odpowiada dokładnie jeden ciąg x1,x2,x3,x4,x5,x6,x7, temu ciągowi - dokładnie jeden ciąg c1,c2,c3,c4,c5,c6,c7, który to ciąg koduje dokładnie jedną liczbę siedmiocyfrową. Np. jeżeli w kolejnych rzutach dostaliśmy: (orzeł, reszka, reszka, reszka, reszka, orzeł, reszka, reszka), to

x1=1,x2=0,x3=0,x4=0,x5=1,x6=0,x7=0

a więc

c1=3,c2=1,c3=1,c4=1,c5=3,c6=1,c7=1,

Oznacza to, że ten wynik rzutu monetą koduje dokładnie jedną liczbę 3111311.

  • Na odwrót, każdej liczbie spełniającej warunki zadania odpowiada jeden ciąg c1,c2,c3,c4,c5,c6,c7, temu ciągowi odpowiada jeden ciąg x1,x2,x3,x4,x5,x6,x7, któremu odpowiada jeden wynik ośmiokrotnego rzutu monetą, w którym wypadły dokładnie dwa orły. Np. liczbie 1151111 odpowiada ciąg

c1=1,c2=1,c3=5,c4=1,c5=1,c6=1,c7=1

a temu – ciąg
x1=0,x2=0,x3=2,x4=0,x5=0,x6=0,x7=0, stąd mamy odpowiadający ciąg rzutów (reszka, reszka, orzeł, orzeł, reszka, reszka, reszka, reszka).
Zatem wszystkich liczb naturalnych siedmiocyfrowych, których suma cyfr jest równa 11 i w zapisie których wszystkie cyfry są nieparzyste, jest tyle samo, co wyników ośmiokrotnego rzutu monetą, w którym wypadły dokładnie dwa orły. Tych wyników jest
8⋅72=28.

Przykład 14

Obliczymy, ile jest wszystkich liczb naturalnych ośmiocyfrowych, których iloczyn cyfr jest równy 18.
Rozkładamy liczbę 18 na czynniki pierwsze: 18=2⋅3⋅3. Oznacza to, że możliwe są trzy przypadki:

  1. wśród cyfr tej liczby jest jedna dwójka, dwie trójki i pięć jedynek,

  2. wśród cyfr tej liczby jest jedna dwójka, jedna dziewiątka i sześć jedynek,

  3. wśród cyfr tej liczby jest jedna trójka, jedna szóstka i sześć jedynek.

  • W pierwszym przypadku: wybieramy jedno miejsce, na którym zapisujemy dwójkę (8 możliwości), z pozostałych siedmiu miejsc wybieramy dwa, na których zapisujemy trójki (7⋅62=21 możliwości), a na pozostałych pięciu miejscach zapisujemy jedynki. Oznacza to, że jest 8⋅21=168 takich liczb.

  • W drugim przypadku: wybieramy jedno miejsce, na którym zapisujemy dwójkę (8 możliwości), z pozostałych siedmiu miejsc wybieramy jedno, na którym zapisujemy dziewiątkę (7 możliwości) , a na pozostałych sześciu miejscach zapisujemy jedynki. Zatem jest 8⋅7=56 takich liczb.

  • W trzecim przypadku: wybieramy jedno miejsce, na którym zapisujemy trójkę (8 możliwości), z pozostałych siedmiu miejsc wybieramy jedno, na którym zapisujemy szóstkę (7 możliwości) , a na pozostałych sześciu miejscach zapisujemy jedynki. Jest więc 8⋅7=56 takich liczb.
    Stąd wynika, że jest 168+56+56=280 wszystkich liczb naturalnych ośmiocyfrowych, których iloczyn cyfr jest równy 18.

Przykład 15

Obliczymy, ile jest wszystkich liczb naturalnych pięciocyfrowych, w zapisie których występuje dokładnie dwa razy cyfra 0 i dokładnie dwa razy cyfra 1.

  • sposób I

Rozróżniamy dwa przypadki:

  1. na pierwszym miejscu zapisana jest cyfra 1,

  2. na pierwszym miejscu jest cyfra różna od 0 i od 1.

  • W pierwszym przypadku: zapisujemy 1 na pierwszym miejscu. Z kolejnych czterech miejsc mamy wybrać jedno dla jedynki (4 możliwości) i zapisać na nim jedynkę. Z pozostałych trzech miejsc wybrać dwa dla zer (3 możliwości) i zapisać na nich zera, a na ostatnim pozostałym miejscu zapisać cyfrę różną od 0 i od 1 (8 możliwości). Takich liczb jest więc 4⋅3⋅8=96.

  • W drugim przypadku: mamy 8 możliwości zapisu pierwszej cyfry, z kolejnych czterech miejsc mamy wybrać dwa dla jedynek (4⋅32=6 możliwości) i zapisać te jedynki, a na pozostałych dwóch miejscach zapisać zera. Zatem jest 8⋅6=48 takich liczb.
    Oznacza to, że jest 96+48=144 wszystkich liczb naturalnych pięciocyfrowych, w zapisie których występuje dokładnie dwa razy cyfra 0 i dokładnie dwa razy występuje cyfra 1.

  • sposób II

Zliczanie rozkładamy na trzy etapy, pamiętając o tym, że zera nie możemy zapisać na pierwszym miejscu (w rzędzie dziesiątek tysięcy):

  1. wybieramy dwa z czterech miejsc, na których możemy wstawić zera (4⋅32=6 możliwości) i zapisujemy zera na tych miejscach,

  2. wybieramy te dwa z pozostałych trzech miejsc, na których zapiszemy jedynki (3 możliwości) i zapisujemy jedynki na tych miejscach,

  3. na ostatnim pozostałym miejscu zapisujemy cyfrę różną od 0 i od 1 (8 możliwości).
    Zatem jest 6⋅3⋅8=144 wszystkich takich liczb naturalnych pięciocyfrowych.

  • sposób III

Wypisujemy kolejno jedna za drugą pięć cyfr, wybierając każdą cyfrę spośród dziesięciu możliwych (dopuszczamy 0 na początkowych miejscach), przy czym na dokładnie dwóch miejscach zapisujemy cyfrę 0 i na dokładnie dwóch miejscach zapisujemy cyfrę 1.
Mamy 5⋅42=10 możliwości wyboru dwóch miejsc dla zer, na pozostałych trzech miejscach zapiszemy dwie jedynki na 3 sposoby, a na ostatnim z pozostałych miejsc zapiszemy cyfrę różną od 0 i od 1 na 8 sposobów. Takich ciągów o 5 cyfrach jest zatem 10⋅3⋅8=240.
Są wśród nich takie, w których cyfra 0 zapisana jest na pierwszym miejscu. W każdym z takich ciągów na kolejnych czterech miejscach znajduje się jeszcze jedna cyfra 0 (miejsce dla niej można wybrać na 4 sposoby), na pozostałych trzech miejscach są dwie jedynki (można je zapisać na 3 sposoby), a na ostatnim z pozostałych miejsc jest cyfra różna od 0 i od 1, którą można zapisać na 8 sposobów. Oznacza to, że jest 4⋅3⋅8=96 takich ciągów z zerem na pierwszym miejscu.
Stąd wynika, że liczb pięciocyfrowych spełniających warunki zadania jest 240-96=144.

i6H8JsFpVm_d5e734
Przykład 16

Do pracy w samorządzie szkolnym zgłosiło się 5 osób: Agnieszka, Beata, Czarek, Darek i Ewa.
W głosowaniu każdy z uczniów tej szkoły ma się wypowiedzieć na temat przydatności do pracy w samorządzie każdej osoby spośród tych pięciorga zgłoszonych. Głosujący dostaje kartkę z danymi pięciorga kandydatów:

R15gctlhLlgZO1
Rysunek kartki do głosowania z napisem: Kandydaci do samorządu szkolnego. Podane, jedno pod drugim, imiona kandydatów: Agnieszka, Beata, Czarek, Darek, Ewa. Obok imion kwadrat do zaznaczenia oddanego głosu.
Źródło: Zespół autorski Politechniki Łódzkiej, licencja: CC BY 3.0.

i podejmuje decyzję, wpisując „x” w kratkę przy danych wybranego kandydata lub pozostawiając kratkę pustą, jeśli danej osoby do samorządu nie zgłasza.

  1. Obliczymy, ile jest wszystkich możliwych wyników takiego głosowania.
    sposób I
    Przy każdym z 5 kandydatów głosujący ma podjąć decyzję na 2 sposoby: zgłaszając kandydata do samorządu, zostawia znak „x” albo pozostawia pustą kratkę, kiedy danej osoby do samorządu nie zgłasza.
    Na przykład:
    – osoba która zgłosiła do samorządu tylko Beatę, Darka i Ewę zostawiła na kartce następujący ciąg znaków , x,, x, x,
    – osoba, która zostawiła na kartce ciąg znaków ,, x, x, zagłosowała tylko na Czarka i Darka.
    Zatem wynik głosowania można utożsamić z pięcioelementowym ciągiem o elementach wybranych ze zbioru dwuelementowego: {x,}.
    Wobec tego wszystkich możliwych wyników tego głosowania jest 2⋅2⋅2⋅2⋅2=25=32.
    sposób II
    Oznaczymy następująco wybory dokonywane w głosowaniu:
    A – oddano głos na Agnieszkę,
    B – oddano głos na Beatę,
    C – oddano głos na Czarka,
    D – oddano głos na Darka,
    E – oddano głos na Ewę.
    Zauważmy, że wynik głosowania jest wyborem konkretnego podzbioru ze zbioru {A, B, C, D, E}. Podzielimy te podzbiory ze względu na ich liczbę elementów. Wtedy:
    – jest 1 wynik głosowania, w którym nie wybrano do samorządu żadnej ze zgłoszonych osób. Odpowiadający takiemu wynikowi podzbiór to zbiór pusty: ,
    – jest 5 wyników głosowania, w których wybrano do samorządu 1 ze zgłoszonych osób. Odpowiadające takim wynikom podzbiory to
    {A}, {B}, {C}, {D}, {E},
    – jest 10 wyników głosowania, w których wybrano do samorządu 2 spośród zgłoszonych osób. Odpowiadające takim wynikom podzbiory to
    {A, B}, {A, C}, {A, D}, {A, E}, {B, C}, {B, D}, {B, E}, {C, D}, {C, E}, {D, E},
    – jest również 10 wyników głosowania, w których wybrano do samorządu 3 spośród zgłoszonych osób. Podzbiory odpowiadające takim wynikom głosowania można potraktować jako dopełnienia do zbioru {A, B, C, D, E} wypisanych powyżej podzbiorów 2-elementowych (np. dopełnieniem podzbioru 2-elementowego {B, C} jest podzbiór 3-elementowy {A, D, E}). W ten sposób otrzymujemy wzajemnie jednoznaczne przyporządkowanie między dwuelementowymi a trzyelementowymi podzbiorami zbioru pięcioelementowego, skąd wynika, że jest tyle samo podzbiorów dwuelementowych i podzbiorów trzyelementowych zbioru pięcioelementowego.
    Odpowiadające takim wynikom podzbiory to
    {C, D, E}, {B, D, E},{B, C, E}, {B, C, D},{A, D, E}, {A, C, E},{A, C, D}, {A, B, E}, {A, B, D}, {A, B, C}.
    – jest 5 wyników głosowania, w których wybrano do samorządu 4 spośród zgłoszonych osób. Traktując te podzbiory jako dopełnienia do zbioru {A, B, C, D, E} wypisanych powyżej podzbiorów jednoelementowych, zauważymy, że jest tyle samo podzbiorów czteroelementowych i podzbiorów jednoelementowych zbioru pięcioelementowego. Podzbiory czteroelementowe rozpatrywanego zbioru pięcioelementowego to

B, C, D, E, A, C, D, E, A, B, D, E, A, B, C, E, A, B, C, D.– jest 1 wynik głosowania, w którym wybrano do samorządu każdą ze zgłoszonych osób. Odpowiadający takiemu wynikowi podzbiór to zbiór {A, B, C, D, E}, który jest (oczywiście) dopełnieniem zbioru pustego do zbioru {A, B, C, D, E}.
Zatem wszystkich możliwych wyników głosowania jest
2⋅1+5+10=32

  1. Wykażemy, że w klasie 3b, liczącej 35 uczniów znajdą się 2 osoby, które w tym głosowaniu oddały głosy na tych samych kandydatów.
    Wybierzmy dowolne 32 osoby spośród 35 uczniów klasy 3b. Jeżeli któreś dwie z nich zagłosowały tak samo, to właśnie te wskazujemy jako szukaną parę. W przeciwnym razie te 32 osoby wyczerpały wszystkie możliwe wyniki głosowania, a więc kolejna, trzydziesta trzecia osoba wypełniła kartkę do głosowania tak samo, jak jedna z wybranych 32 osób. To spostrzeżenie kończy dowód.

Przykład 17

Obliczymy, ile jest:

  1. wszystkich wyników pięciokrotnego rzutu monetą, w których wypadło mniej orłów niż reszek.
    sposób I
    Rozróżniamy trzy przypadki:
    (1) ani razu nie wypadł orzeł (wtedy w każdym rzucie wypadła reszka) – jest jedna taka możliwość,
    (2) wypadł dokładnie jeden orzeł (wtedy wypadły jeszcze 4 reszki) – takich możliwości jest 5,
    (3) wypadły dokładnie dwa orły (wtedy wypadły jeszcze 3 reszki) – takich możliwości jest 5⋅42=10.
    Stąd wynika, że jest 1+5+10=16 wszystkich wyników pięciokrotnego rzutu monetą, w których wypadło mniej orłów niż reszek.
    sposób II
    Skorzystamy z reguły równoliczności.
    Jest 2⋅2⋅2⋅2⋅2=25=32 wszystkich wyników pięciokrotnego rzutu monetą. Można je podzielić na dwie rozłączne grupy:
    (1) tych wyników, w których wypadło mniej orłów niż reszek,
    (2) tych wyników, w których wypadło mniej reszek niż orłów.
    Biorąc dowolny wynik z pierwszej grupy i zamieniając każdego orła na reszkę oraz każdą reszkę na orła dostaniemy jeden wynik z drugiej grupy. Postępując analogicznie z wynikiem z drugiej grupy dostaniemy jeden wynik z pierwszej grupy. Zatem wyniki te można połączyć w pary, co oznacza, że dokładnie połowa wszystkich wyników pięciokrotnego rzutu monetą to te, w których orłów jest mniej niż reszek. Jest ich więc 12⋅32=16.

  2. wszystkich wyników dziewięciokrotnego rzutu monetą, w których wypadło więcej orłów niż reszek.
    Jest 2⋅2⋅2⋅2⋅2⋅2⋅2⋅2⋅2=29=512 wszystkich wyników dziewięciokrotnego rzutu monetą. Można je podzielić na dwie rozłączne grupy:
    (1) tych wyników, w których wypadło więcej orłów niż reszek,
    (2) tych wyników, w których wypadło więcej reszek niż orłów.
    Rozumując podobnie jak w II sposobie rozwiązania poprzedniego podpunktu, stwierdzimy, że pojedyncze wyniki z obu tych grup można połączyć w pary. Oznacza to, że dokładnie połowa wszystkich wyników dziewięciokrotnego rzutu monetą to te, w których orłów jest więcej niż reszek. Wyników tych jest zatem 12⋅512=256.

Przykład 18

W pudełku znajduje się sześć kul ponumerowanych od 1 do 6. Z tego pudełka losujemy dowolnie wybrane kule. Ile jest możliwości wylosowania w ten sposób takich kul, że suma numerów: najmniejszego i największego z zapisanych na tych wylosowanych kulach jest równa 7?
Zauważmy, że w sposób opisany w treści zadania sumę numerów równą 7 można otrzymać:

  • gdy najmniejszy z numerów jest równy 1 i największy jest równy 6,

  • gdy najmniejszy z numerów jest równy 2 i największy jest równy 5,

  • gdy najmniejszy z numerów jest równy 3 i największy jest równy 4.

Rozróżniamy zatem trzy rozłączne przypadki:

  1. wśród wylosowanych znalazły się kule o numerach 1 oraz 6,

  2. wśród wylosowanych nie ma żadnej z kul o numerach 1, 6 i znalazły się kule o numerach 2 oraz 5,

  3. wylosowano tylko dwie kule: z numerem 3 oraz z numerem 4.

W pierwszym przypadku wraz z wylosowanymi dwiema kulami można wylosować dowolny podzbiór ze zbioru czterech pozostałych kul. Ponieważ decyzji o wyborze każdej z tych 4 kul możemy dokonać na 2 sposoby, więc łącznie w tym przypadku jest 2⋅2⋅2⋅2=24=16 możliwości wylosowania kul.
W drugim przypadku wraz z wylosowanymi dwiema kulami można wylosować dowolny podzbiór ze zbioru, w którym są dwie kule: kula z numerem 3 oraz kula z numerem 4. Zatem w tym przypadku są 2⋅2=22=4 możliwości wylosowania kul.
W trzecim przypadku mamy jeden sposób wylosowania kul.
Oznacza to, że jest 16+4+1=21 wszystkich możliwości wylosowania kul w sposób opisany w treści zadania.

Reguła mnożenia, reguła dodawania
Podzbiory zbioru skończonego (treść rozszerzona)