Kombinatoryka sprawdzian

Kombinatoryka

Sprawdzian

Grupa A

Zadanie 1 (2 pkt)

Na ile różnych sposobów $8$ różnych przedmiotów można tak podzielić między dwie osoby, aby każda osoba dostała co najmniej jeden przedmiot?

Wskazówki:

Każdy z $8$ różnych przedmiotów może trafić niezależnie do pierwszej lub do drugiej osoby, co daje $2$ możliwości wyboru na każdy przedmiot.
Zadanie najszybciej rozwiązuje się metodą zdarzenia przeciwnego – od liczby wszystkich możliwych podziałów odejmuje się te przypadki, które nie spełniają warunków zadania (gdy jedna z osób nie otrzymała ani jednego przedmiotu).
Alternatywnie można zastosować kombinacje: wybieramy liczbę przedmiotów, które trafią do pierwszej osoby (od $1$ do $7$), a pozostałe automatycznie otrzymuje druga osoba.

Rozwiązanie krok po kroku:

Sposób I – Wykorzystanie zasady dopełnienia (zdarzenia przeciwnego):
Niech osoby zostaną oznaczone jako osoba $A$ oraz osoba $B$. Każdy z $8$ rozróżnialnych przedmiotów możemy przydzielić na jeden z dwóch sposobów: albo wręczamy go osobie $A$, albo osobie $B$.

Na mocy reguły mnożenia łączna liczba wszystkich możliwych przydziałów wynosi: $$\begin{aligned} N &= 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \\[8pt] &= 2^8 = 256 \end{aligned}$$ Warunek zadania mówi, że każda osoba musi otrzymać co najmniej jeden przedmiot. Zdarzeniami niepożądanymi są sytuacje, w których jedna z osób nie dostaje niczego:
- Osoba $A$ otrzymuje wszystkie $8$ przedmiotów, a osoba $B$ dostaje $0$ przedmiotów – jest dokładnie $1$ taka możliwość.
- Osoba $B$ otrzymuje wszystkie $8$ przedmiotów, a osoba $A$ dostaje $0$ przedmiotów – jest dokładnie $1$ taka możliwość.
Liczba niepoprawnych podziałów wynosi $1 + 1 = 2$.

Odejmujemy przypadki niepożądane od wszystkich możliwych: $$\begin{aligned} W &= 2^8 - 2 \\[8pt] &= 256 - 2 \\[8pt] &= 254 \end{aligned}$$
Sposób II – Bezpośrednie zliczenie za pomocą kombinacji:
Podział polega na wybraniu podzbioru przedmiotów, które otrzyma pierwsza osoba (druga osoba otrzymuje automatycznie wszystkie pozostałe).

Ponieważ każda osoba musi dostać co najmniej jeden przedmiot, pierwsza osoba może otrzymać od $1$ do $7$ przedmiotów. Liczbę wyborów dla każdej możliwej liczby przedmiotów określa symbol Newtona $\binom{n}{k}$:

$$\begin{aligned} \binom{8}{1} &= 8 \\[8pt] \binom{8}{2} &= \dfrac{8 \cdot 7}{2} = 28 \\[8pt] \binom{8}{3} &= \dfrac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56 \\[8pt] \binom{8}{4} &= \dfrac{8 \cdot 7 \cdot 6 \cdot 5}{4 \cdot 3 \cdot 2 \cdot 1} = 70 \end{aligned}$$ Wykorzystując symetrię symbolu Newtona $\binom{8}{k} = \binom{8}{8-k}$, wyznaczamy pozostałe wartości: $$\begin{aligned} \binom{8}{5} &= \binom{8}{3} = 56 \\[8pt] \binom{8}{6} &= \binom{8}{2} = 28 \\[8pt] \binom{8}{7} &= \binom{8}{1} = 8 \end{aligned}$$ Sumujemy wszystkie dopuszczalne warianty: $$\begin{aligned} W &= \binom{8}{1} + \binom{8}{2} + \binom{8}{3} + \binom{8}{4} + \binom{8}{5} + \binom{8}{6} + \binom{8}{7} \\[8pt] &= 8 + 28 + 56 + 70 + 56 + 28 + 8 \\[8pt] &= 254 \end{aligned}$$ Obie metody prowadzą do tego samego wyniku.

Odpowiedź:
Podziału $8$ różnych przedmiotów między dwie osoby tak, aby każda dostała co najmniej jeden przedmiot, można dokonać na $254$ sposoby.

Zadanie 2 (2 pkt)

Ile różnych słów ośmioliterowych (mających sens lub nie) można utworzyć ze słowa KATAKANA?

Wskazówki:

Zlicz liczbę wszystkich liter w słowie KATAKANA oraz ustal liczbę powtórzeń poszczególnych liter.
Ponieważ litery $\text{A}$ oraz $\text{K}$ powtarzają się wielokrotnie, przestawienie identycznych liter między sobą nie tworzy nowego słowa. Zastosuj wzór na permutacje z powtórzeniami.
Alternatywnie zadanie można rozwiązać, wybierając pozycje w słowie dla poszczególnych liter za pomocą kombinacji (symbolu Newtona) i stosując regułę mnożenia.

Rozwiązanie krok po kroku:

Zliczenie liczby poszczególnych liter w słowie KATAKANA:
W słowie KATAKANA występuje łącznie $8$ liter. Zliczamy liczbę powtórzeń każdej z nich:
- litera $\text{A}$: $4$ razy,
- litera $\text{K}$: $2$ razy,
- litera $\text{T}$: $1$ raz,
- litera $\text{N}$: $1$ raz.
Suma liter wynosi $4 + 2 + 1 + 1 = 8$. Tworzymy słowa ośmioliterowe, co oznacza, że w każdym utworzonym słowie wykorzystujemy wszystkie litery ze słowa wyjściowego.
Sposób I – Wykorzystanie wzoru na permutacje z powtórzeniami:
Gdyby wszystkie litery były różne, liczba możliwych permutacji wynosiłaby $8!$. Ponieważ niektóre litery się powtarzają, zamiana miejscami jednakowych liter nie daje nowego słowa. Całkowitą liczbę permutacji dzielimy przez iloczyn silni liczb powtórzeń poszczególnych liter: $$P_n^{n_1, n_2, \dots, n_k} = \dfrac{n!}{n_1! \cdot n_2! \cdot \dots \cdot n_k!}$$ Podstawiamy wartości: $n = 8$, $n_{\text{A}} = 4$, $n_{\text{K}} = 2$, $n_{\text{T}} = 1$, $n_{\text{N}} = 1$: $$\begin{aligned} P_8^{4, 2, 1, 1} &= \dfrac{8!}{4! \cdot 2! \cdot 1! \cdot 1!} \\[8pt] &= \dfrac{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4!}{4! \cdot (2 \cdot 1) \cdot 1 \cdot 1} \\[8pt] &= \dfrac{8 \cdot 7 \cdot 6 \cdot 5}{2} \\[8pt] &= 4 \cdot 7 \cdot 6 \cdot 5 \\[8pt] &= 28 \cdot 30 = 840 \end{aligned}$$
Sposób II – Wybór miejsc dla kolejnych liter (kombinacje i reguła mnożenia):
Słowo ośmioliterowe możemy traktować jako $8$ ponumerowanych pozycji. Rozmieszczamy w nich kolejne litery:
- Najpierw wybieramy $4$ miejsca z $8$ dla liter $\text{A}$: $$\binom{8}{4} = \dfrac{8 \cdot 7 \cdot 6 \cdot 5}{4 \cdot 3 \cdot 2 \cdot 1} = \dfrac{1680}{24} = 70$$
- Z pozostałych $4$ wolnych miejsc wybieramy $2$ miejsca dla liter $\text{K}$: $$\binom{4}{2} = \dfrac{4 \cdot 3}{2 \cdot 1} = 6$$
- Z pozostałych $2$ miejsc wybieramy $1$ miejsce dla litery $\text{T}$: $$\binom{2}{1} = 2$$
- Na ostatnim $1$ wolnym miejscu umieszczamy literę $\text{N}$: $$\binom{1}{1} = 1$$
Na mocy reguły mnożenia łączna liczba różnych słów wynosi: $$\begin{aligned} N &= \binom{8}{4} \cdot \binom{4}{2} \cdot \binom{2}{1} \cdot \binom{1}{1} \\[8pt] &= 70 \cdot 6 \cdot 2 \cdot 1 \\[8pt] &= 420 \cdot 2 = 840 \end{aligned}$$

Odpowiedź:
Ze słowa KATAKANA można utworzyć $840$ różnych słów ośmioliterowych.

Zadanie 3 (2 pkt)

Używając cyfr 1, 2, 3, 4, 5, 6, 7 każdej tylko raz, tworzymy siedmiocyfrową liczbę naturalną. Ile jest takich liczb, których zapis zawiera ciąg cyfr 123 lub ciąg cyfr 31?

Wskazówki:

Zadanie można rozwiązać dwoma prostymi sposobami: „sklejając” sąsiednie cyfry w jeden nierozerwalny klocek (Sposób I) albo wybierając miejsca w siedmiocyfrowej liczbie, na których dany blok może stanąć, a pozostałe cyfry rozmieszczając na wolnych polach (Sposób II).
Zauważ, że cyfry nie mogą się powtarzać – ciągi „123” oraz „31” nie mogą wystąpić w tej samej liczbie jednocześnie (wymagałoby to powtórzenia cyfry 1 lub cyfry 3). Wystarczy więc obliczyć liczbę przypadków dla każdego ciągu osobno i dodać oba wyniki do siebie.

Rozwiązanie krok po kroku:

Sposób I – Metoda „sklejania” cyfr w jeden blok (permutacje):
W tym podejściu grupy cyfr, które muszą stać obok siebie w ustalonej kolejności, traktujemy jak pojedyncze, „sklejone” elementy.

• Część 1: Liczby zawierające ciąg cyfr 123
Sklejamy cyfry $1, 2, 3$ w jeden element $[123]$. Pozostałe cyfry to: $4, 5, 6, 7$.
Mamy do poukładania $5$ elementów: $$\{[123], 4, 5, 6, 7\}$$ Liczba permutacji tych $5$ elementów wynosi: $$\begin{aligned} N_1 &= 5! \\[8pt] &= 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \\[8pt] &= 120 \end{aligned}$$ • Część 2: Liczby zawierające ciąg cyfr 31
Sklejamy cyfry $3, 1$ w jeden element $[31]$. Pozostałe cyfry to: $2, 4, 5, 6, 7$.
Mamy do poukładania $6$ elementów: $$\{[31], 2, 4, 5, 6, 7\}$$ Liczba permutacji tych $6$ elementów wynosi: $$\begin{aligned} N_2 &= 6! \\[8pt] &= 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \\[8pt] &= 720 \end{aligned}$$ • Część 3: Czy oba ciągi mogą pojawić się w jednej liczbie naraz?
Gdyby w liczbie wystąpiły jednocześnie bloki $[123]$ oraz $[31]$:
– osobno: cyfra $1$ oraz cyfra $3$ musiałyby pojawić się po dwa razy,
– połączone na zakładkę: powstałby ciąg $1231$ (dwie jedynki) lub $3123$ (dwie trójki).
W treści zaznaczono, że każdą cyfrę wykorzystujemy tylko raz. Zatem żadna liczba nie może zawierać jednocześnie obu tych ciągów naraz (przypadki wzajemnie się wykluczają).

Dodajemy liczbę możliwości z obu przypadków: $$\begin{aligned} N &= N_1 + N_2 \\[8pt] &= 120 + 720 \\[8pt] &= 840 \end{aligned}$$

Ostatecznie istnieje $840$ takich liczb.
Sposób II – Metoda wyboru pozycji w liczbie i reguła mnożenia:
Każda tworzona liczba ma $7$ pozycji: $\underline{\phantom{0}}\; \underline{\phantom{0}}\; \underline{\phantom{0}}\; \underline{\phantom{0}}\; \underline{\phantom{0}}\; \underline{\phantom{0}}\; \underline{\phantom{0}}$. Sprawdzamy, na ile sposobów możemy wstawić dany blok na konkretne miejsca, a następnie na ile sposobów możemy uzupełnić pozostałe pozycje wolnymi cyframi.

• Przypadek 1: Liczby zawierające ciąg cyfr 123
Ciąg „123” składa się z $3$ cyfr i musi zająć trzy kolejne miejsca w liczbie. Może on zająć pozycje:
1. miejsca od 1. do 3.: $\mathbf{123}\underline{\phantom{0}}\underline{\phantom{0}}\underline{\phantom{0}}\underline{\phantom{0}}$
2. miejsca od 2. do 4.: $\underline{\phantom{0}}\mathbf{123}\underline{\phantom{0}}\underline{\phantom{0}}\underline{\phantom{0}}$
3. miejsca od 3. do 5.: $\underline{\phantom{0}}\underline{\phantom{0}}\mathbf{123}\underline{\phantom{0}}\underline{\phantom{0}}$
4. miejsca od 4. do 6.: $\underline{\phantom{0}}\underline{\phantom{0}}\underline{\phantom{0}}\mathbf{123}\underline{\phantom{0}}$
5. miejsca od 5. do 7.: $\underline{\phantom{0}}\underline{\phantom{0}}\underline{\phantom{0}}\underline{\phantom{0}}\mathbf{123}$
Mamy więc dokładnie $5$ możliwych położeń dla całego bloku.

Dla każdego wybranego położenia bloku zostają $4$ puste miejsca, na których dowolnie rozmieszczamy pozostałe $4$ cyfry ($4, 5, 6, 7$). Zgodnie z regułą mnożenia możemy to zrobić na $4!$ sposobów: $$4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$$ Liczba liczb zawierających ciąg „123” wynosi: $$N_1 = 5 \cdot 4! = 5 \cdot 24 = 120$$ • Przypadek 2: Liczby zawierające ciąg cyfr 31
Ciąg „31” składa się z $2$ cyfr i musi zająć dwa kolejne miejsca w liczbie. Może on stać na pozycjach:
1. miejsca 1–2, 2. miejsca 2–3, 3. miejsca 3–4, 4. miejsca 4–5, 5. miejsca 5–6 lub 6. miejsca 6–7.
Mamy więc dokładnie $6$ możliwych położeń dla tego bloku.

Dla każdego z tych położeń pozostaje $5$ wolnych miejsc, na których rozmieszczamy pozostałe $5$ cyfr ($2, 4, 5, 6, 7$) na $5!$ sposobów: $$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$$ Liczba liczb zawierających ciąg „31” wynosi: $$N_2 = 6 \cdot 5! = 6 \cdot 120 = 720$$ • Podsumowanie obu przypadków:
Ponieważ żadna z cyfr nie może się powtórzyć w zapisie liczby, żaden układ nie może zawierać naraz ciągów „123” i „31”. Z reguły dodawania otrzymujemy: $$\begin{aligned} N &= N_1 + N_2 \\[8pt] &= 120 + 720 \\[8pt] &= 840 \end{aligned}$$ Ostatecznie istnieje $840$ takich liczb.

Odpowiedź:
Liczba takich liczb wynosi $840$.

Zadanie 4 (2 pkt)

Ile jest siedmiocyfrowych liczb parzystych całkowitych dodatnich, o różnych cyfrach, których zapis zaczyna się cyfrą 3?

Wskazówki:

Liczba siedmiocyfrowa składa się z siedmiu pozycji. Zbiór wszystkich cyfr w układzie dziesiętnym to $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ (łącznie 10 cyfr).
Zauważ, że pierwsza cyfra (cyfra milionów) jest ustalona z góry i wynosi $3$. Ponieważ liczba $3$ jest nieparzysta, nie zmniejsza ona puli dostępnych cyfr parzystych.
Warunek parzystości liczby oznacza, że jej ostatnia cyfra (cyfra jedności) musi należeć do zbioru cyfr parzystych: $\{0, 2, 4, 6, 8\}$.
Ponieważ wszystkie cyfry muszą być różne, po obsadzeniu pierwszej i ostatniej pozycji ze zbioru 10 cyfr pozostaje 8 cyfr do rozmieszczenia na 5 wolnych miejscach.
Do wyznaczenia liczby takich liczb zastosuj regułę mnożenia.

Rozwiązanie krok po kroku:

Sposób I – Wykorzystanie klasycznej reguły mnożenia:
Niech nasza liczba siedmiocyfrowa ma postać: $$d_1 d_2 d_3 d_4 d_5 d_6 d_7$$ gdzie poszczególne litery oznaczają cyfry na kolejnych pozycjach (od cyfry milionów do cyfry jedności). Analizujemy liczbę możliwości wyboru cyfry dla każdej pozycji:

• Pozycja $d_1$ (pierwsza cyfra): Zgodnie z treścią zadania zapis musi zaczynać się cyfrą $3$, co daje dokładnie: $$1 \text{ możliwość} \quad (d_1 = 3)$$ • Pozycja $d_7$ (ostatnia cyfra): Liczba ma być parzysta, więc jej ostatnią cyfrą musi być cyfra parzysta: $d_7 \in \{0, 2, 4, 6, 8\}$. Ponieważ cyfra $3$ jest nieparzysta, nie wyklucza żadnej z cyfr parzystych. Mamy zatem do wyboru: $$5 \text{ możliwości}$$ • Pozycje środkowe ($d_2, d_3, d_4, d_5, d_6$): Cały zbiór cyfr liczy $10$ elementów: $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Ponieważ wszystkie cyfry liczby muszą być różne, a dwie cyfry ($d_1$ oraz $d_7$) zostały już wykorzystane, pozostaje: $$10 - 2 = 8 \text{ dostępnych cyfr}$$ Kolejne pozycje obsadzamy z puli pozostałych cyfr:

- Dla pozycji $d_2$: mamy $8$ możliwości,
- Dla pozycji $d_3$: mamy $7$ możliwości,
- Dla pozycji $d_4$: mamy $6$ możliwości,
- Dla pozycji $d_5$: mamy $5$ możliwości,
- Dla pozycji $d_6$: mamy $4$ możliwości.

Na mocy reguły mnożenia całkowita liczba takich liczb siedmiocyfrowych wynosi: $$\begin{aligned} N &= 1 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 5 \\[8pt] &= 5 \cdot (8 \cdot 7 \cdot 6 \cdot 5 \cdot 4) \\[8pt] &= 5 \cdot 6720 \\[8pt] &= 33\,600 \end{aligned}$$
Sposób II – Wykorzystanie wariacji bez powtórzeń:
Wybór cyfry pierwszej $d_1$ oraz ostatniej $d_7$ traktujemy jako etapy wstępne:

• Wybór cyfry pierwszej: $1$ sposób (cyfra $3$).
• Wybór cyfry ostatniej: $5$ sposobów (jedna cyfra ze zbioru $\{0, 2, 4, 6, 8\}$).

Pozostałe $5$ miejsc ($d_2, d_3, d_4, d_5, d_6$) obsadzamy pięcioma różnymi cyframi wybranymi z puli $8$ pozostałych cyfr. Liczba takich uporządkowanych wyborów odpowiada liczbie $5$-wyrazowych wariacji bez powtórzeń ze zbioru $8$-elementowego: $$V_8^5 = \dfrac{8!}{(8 - 5)!} = \dfrac{8!}{3!}$$ Rozpisujemy silnię: $$\begin{aligned} V_8^5 &= \dfrac{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3!}{3!} \\[8pt] &= 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \\[8pt] &= 6720 \end{aligned}$$ Łączna liczba liczb wynosi zatem: $$\begin{aligned} N &= 1 \cdot 5 \cdot V_8^5 \\[8pt] &= 5 \cdot 6720 \\[8pt] &= 33\,600 \end{aligned}$$

Odpowiedź:
Jest $33\,600$ takich liczb.

Zadanie 5 (2 pkt)

Na okręgu zaznaczono szesnaście różnych punktów. Ile różnych pięciokątów wypukłych o wszystkich wierzchołkach w tych punktach można narysować?

Wskazówki:

Zastanów się, czy dowolne trzy punkty leżące na okręgu mogą być współliniowe. Okrąg ma tę własność, że żadne trzy punkty nie leżą na jednej prostej.
Zauważ, że każde wybrane $5$ punktów na okręgu wyznacza dokładnie jeden wielokąt wypukły, jeśli połączymy je w kolejności występowania na okręgu.
Kolejność wyboru punktów nie tworzy nowego pięciokąta – liczy się jedynie skład wybranego podzbioru wierzchołków. Zastosuj kombinacje bez powtórzeń $\binom{n}{k}$.

Rozwiązanie krok po kroku:

Analiza geometryczna i własność punktów na okręgu:
Wszystkie $16$ punktów leży na jednym okręgu. Ponieważ prosta może przeciąć okrąg w co najwyżej dwóch punktach, żadne trzy z zaznaczonych punktów nie są współliniowe.

Okrąg jest figurą ściśle wypukłą. Oznacza to, że dowolny wybór $5$ różnych punktów z danych $16$ jednoznacznie definiuje dokładnie jeden pięciokąt wypukły – powstaje on poprzez połączenie tych punktów kolejno odcinkami zgodnie z ich naturalnym uporządkowaniem wzdłuż brzegu okręgu. Zmiana kolejności wybierania wierzchołków nie daje innego wielokąta, dlatego mamy do czynienia z wyborem podzbioru $5$-elementowego ze zbioru $16$-elementowego.
Zastosowanie kombinacji i obliczenie liczby pięciokątów:
Liczba możliwych do utworzenia pięciokątów wypukłych jest równa liczbie $5$-elementowych kombinacji ze zbioru $16$-elementowego, czyli symbolowi Newtona $\binom{16}{5}$: $$\binom{n}{k} = \dfrac{n!}{k!(n - k)!}$$ Dla danych $n = 16$ oraz $k = 5$: $$\begin{aligned} \binom{16}{5} &= \dfrac{16!}{5! \cdot (16 - 5)!} \\[8pt] &= \dfrac{16!}{5! \cdot 11!} \\[8pt] &= \dfrac{16 \cdot 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11!}{(5 \cdot 4 \cdot 3 \cdot 2 \cdot 1) \cdot 11!} \\[8pt] &= \dfrac{16 \cdot 15 \cdot 14 \cdot 13 \cdot 12}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} \end{aligned}$$ Upraszczamy ułamek przez skracanie czynników w liczniku i mianowniku:
– iloczyn $5 \cdot 3 = 15$ w mianowniku skraca się z liczbą $15$ w liczniku,
– iloczyn $4 \cdot 2 = 8$ w mianowniku skraca się z liczbą $16$ w liczniku, dając $2$: $$\begin{aligned} \binom{16}{5} &= 2 \cdot 14 \cdot 13 \cdot 12 \\[8pt] &= 28 \cdot 156 \\[8pt] &= 4368 \end{aligned}$$

Odpowiedź:
Można narysować $4368$ różnych pięciokątów wypukłych.

Grupa B

Zadanie 1 (2 pkt)

Na ile różnych sposobów 7 różnych przedmiotów można tak podzielić między dwie osoby, aby każda osoba dostała co najmniej jeden przedmiot?