Pytanie 1: Zaznacz zdania prawdziwe
-
○
Uporządkowany podział zbioru, to podział zbioru na podzbiory, taki że elementy w tych podzbiorach są uporządkowane rosnąco.
-
✓
Jeśli rodzina zbiorów $\{A_1, A_2, ..., A_k\}$ jest podziałem zbioru $S$, to $S = A_1 \cup A_2 \cup ... \cup A_k$.
-
○
Liczba podziałów zbioru $S$ może być zapisana za pomocą współczynnika wielomianowego.
-
○
Podziałem zbioru nazywamy każdą rodzinę pewnych niepustych rozłącznych podzbiorów zbudowanych z pewnych elementów tego zbioru.
-
○
Wszystkie podziały pewnego zbioru $n$-elementowego można wygenerować za pomocą generacji wszystkich liczb binarnych z zakresu od $0$ do $2^n-1$.
Pytanie 2: Obiekty kombinatoryczne $B, A, C$ i $C, A, B$ utworzone ze zbioru $\{A, B, C, D\}$ i są identyczne (nie można ich odróżnić). Podane obiekty mogą być przykładem:
-
○
podziału zbioru na dwa podzbiory.
-
○
3-elementowej wariacji bez powtórzeń ze zbioru 4-elementowego.
-
○
3-elementowej wariacji z powtórzeniami ze zbioru 4-elementowego.
-
✓
3-elementowej kombinacji z powtórzeniami ze zbioru 4-elementowego.
-
○
3-elementowej permutacji bez powtórzeń ze zbioru 4-elementowego.
Pytanie 3: Zaznacz zdania prawdziwe:
-
○
Każde rozmieszczenie $k$ rozróżnialnych elementów w $n$ rozróżnialnych pudełkach odpowiada $k$-wyrazowej wariacji bez powtórzeń ze zbioru $n$-elementowego.
-
○
$k$-wyrazową wariacją bez powtórzeń z $n$-elementowego zbioru nazywamy każdy ciąg elementów pochodzących z tego zbioru, a liczba takich wariacji wynosi $n^k$.
-
✓
Każde liniowe uporządkowanie $k$ rozróżnialnych elementów ze zbioru $n$-elementowego jest $k$-wyrazową wariacją bez powtórzeń z tego zbioru.
-
○
$k$-wyrazową wariacją bez powtórzeń ze zbioru $n$-elementowego nazywamy każdy $k$-wyrazowy ciąg elementów tego zbioru i liczba takich wariacji wynosi $\frac{n!}{(n-k)!}$, gdzie $k < n$ lub $k \geq n$.
-
○
$k$-wyrazową wariacją bez powtórzeń z $n$-elementowego zbioru nazywamy każdy $k$-wyrazowy ciąg elementów tego zbioru.
Pytanie 4: Każdy sposób wrzucenia 4 identycznych elementów do 5 rozróżnialnych pudełek jest przykładem:
-
○
5-elementowej wariacji bez powtórzeń ze zbioru 4-elementowego.
-
○
4-elementowej wariacji z powtórzeniami ze zbioru 5-elementowego.
-
✓
4-elementowej kombinacji z powtórzeniami ze zbioru 5-elementowego.
-
○
5-elementowej kombinacji bez powtórzeń ze zbioru 4-elementowego.
-
○
4-elementowej permutacji z powtórzeniami ze zbioru 5-elementowego.
Pytanie 5: Zaznacz zdanie prawdziwe.
-
○
Zasada dobrego uporządkowania stwierdza, że zbiór liczb całkowitych zawiera element najmniejszy.
-
✓
Dowód poprawności pierwszej zasady indukcji matematycznej opiera się o zasadę dobrego uporządkowania i wykorzystuje technikę sprowadzania do sprzeczności.
-
○
Zbiorem dobrze uporządkowanym jest dowolny podzbiór zbioru liczb całkowitych oraz liczb wymiernych, ale nie liczb rzeczywistych.
-
○
Jeśli dla każdej pary elementów $a$ i $b$ można odpowiedzieć na pytanie czy $a \leq b$, to zbiór $S$ jest dobrze uporządkowany.
-
○
Zbiór liczb całkowitych ujemnych jest dobrze uporządkowany.
Pytanie 6: Zaznacz zdanie prawdziwe.
-
○
Dowód kroku indukcyjnego w drugiej zasadzie indukcji wymaga wykazania prawdziwości zdania $S(n_0) \land S(n_0+1) \land ... \land S(k)$ i prawdziwości zdania $S(k+1)$ dla pewnej liczby $k \geq 1$.
-
○
Dowód kroku indukcyjnego w drugiej zasadzie indukcji wymaga pokazania, że dla pewnej konkretnej wartości $k \geq n_0$ zachodzi implikacja $[S(n_0) \land ... \land S(k)] \Rightarrow S(k+1)$.
-
✓
W zasadzie silnej indukcji matematycznej warunek początkowy ma postać $S(n_0) \land S(n_0+1) \land ... \land S(n_1)$, gdzie $n_0, n_1 \in \mathbb{Z}^+$ i $n_0 \leq n_1$, a $S(n)$ oznacza zdanie otwarte, w którym występuje liczba całkowita dodatnia $n$.
-
○
Dowód kroku indukcyjnego w drugiej zasadzie indukcji wymaga wykazania prawdziwości zdania $S(k+1)$ dla każdej liczby $k \geq n_0$.
-
○
Dowód warunku początkowego w drugiej zasadzie indukcji matematycznej wymaga pokazania prawdziwości pewnych zdań $S(n)$ dla dowolnych elementów $n$, takich że $n_0 \leq n \leq n_1$.
Pytanie 7: Zasada indukcji matematycznej jest techniką, która może być zastosowana do dowodzenia twierdzeń $S(n)$:
-
○
dotyczących kolejnych liczb rzeczywistych.
-
○
dotyczących dowolnych liczb dodatnich.
-
○
dotyczących liczb wymiernych.
-
✓
w których $n$ należy do zbioru liczb całkowitych dodatnich.
-
○
w których $n$ jest nieujemne.
Pytanie 8: Zaznacz zdanie prawdziwe.
-
✓
Zależność postaci $c_n a_n + c_{n-1} a_{n-1} + c_{n-2} a_{n-2} + c_{n-3} a_{n-3} = 0$, gdzie $c_n, c_{n-1}, c_{n-2}, c_{n-3}$ są pewnymi stałymi, $c_n \neq 0$ i $c_{n-3} \neq 0$, jest liniową zależnością rekurencyjną jednorodną rzędu trzeciego i może być rozwiązana za pomocą równania charakterystycznego stopnia trzeciego.
-
○
Rozwiązanie liniowej niejednorodnej zależności rekurencyjnej rzędu pierwszego ze stałymi współczynnikami, postaci $a_{n+1} + c a_n = f(n)$ jest dane wzorem: $a_n = a_0 d^n$ gdzie $d_0$ i $d$ oznaczają pewne stałe, $n \in \mathbb{N}$.
-
○
Rozwiązanie liniowej niejednorodnej zależności rekurencyjnej rzędu drugiego ze stałymi współczynnikami, ma postać $ a_n = c_1 r_1^n + c_2 r_2^n$ lub $a_n = c_1 r_1^n + c_2 n r^n$ w zależności od liczby różnych pierwiastków równania charakterystycznego.
-
○
Rozwiązanie liniowej jednorodnej zależności rekurencyjnej rzędu drugiego ze stałymi współczynnikami o równaniu charakterystycznym o dwóch różnych pierwiastkach, ma postać $a_n = c_1 x_1^n + c_2 x_2^n$ gdzie $x_1$ i $x_2$ są wyznaczane w oparciu o początkowe elementy ciągu.
-
○
Wyznaczenie wzoru jawnego jest możliwe dla ciągów liczbowych opisanych jedynie zależnościami rekurencyjnymi jednorodnymi.
Pytanie 9: Zależność rekurencyjna $(a_0 = 0, a_1 = 3, a_2 = 4, a_3 = 6, 2a_{n+1} + 3a_{n-3} = 0 \text{ dla } n \geq 3)$ jest zależnością rekurencyjną:
-
✓
liniową ze stałymi współczynnikami rzędu czwartego jednorodną.
-
○
liniową ze stałymi współczynnikami rzędu drugiego jednorodną.
-
○
liniową ze stałymi współczynnikami rzędu pierwszego niejednorodną.
-
○
liniową ze stałymi współczynnikami rzędu czwartego niejednorodną.
-
○
liniową ze stałymi współczynnikami rzędu trzeciego jednorodną.
Pytanie 10: Zależność rekurencyjna $(a_0 = 1, a_1 = 2, a_2 = 3, a_n + 5a_{n-1} - 4a_{n-3} = 0 \text{ dla } n \geq 3)$ jest zależnością:
-
○
która nie może być rozwiązana metodą równania charakterystycznego.
-
○
dla której równanie charakterystyczne jest równaniem kwadratowym.
-
✓
dla której równanie charakterystyczne jest równaniem stopnia trzeciego.
-
○
nieliniową.
-
○
niejednorodną.
Pytanie 11: Zaznacz zdanie prawdziwe:
-
○
Liczby Stirlinga drugiego rodzaju opisujące liczbę sposobów podziału zbioru $n$-elementowego na $k$-niepustych podzbiorów są nie mniejsze niż liczby Stirlinga pierwszego rodzaju opisujące liczbę sposobów rozmieszczenia $n$ elementów w $k$ cyklach.
-
○
Z definicji przyjmuje się, że liczba Stirlinga drugiego rodzaju $S(n,n) = 1$ dla $n \geq 0$, ponieważ opisywany przez nią podział jest niemożliwy.
-
○
Liczby harmoniczne $H_n$ są dyskretnym odpowiednikiem funkcji $f(x) = \frac{1}{x}$ i tworzą ciąg liczbowy rosnący logarytmicznie wolno dla $n \to \infty$.
-
✓
Liczby Eulera pierwszego rzędu $\left\langle \begin{array}{c} n \\ k \end{array} \right\rangle$ oznaczają liczbę $n$-elementowych permutacji bez powtórzeń ze zbioru $n$-elementowego zawierających $k$ wzniesień.
-
○
Twierdzenie Zeckendorfa stwierdza, iż każda liczba całkowita dodatnia $n$ może być jednoznacznie przedstawiona w postaci iloczynu pewnych liczb Fibonacciego i zapisana w postaci odpowiedniego ciągu zer i jedynek.
Pytanie 12: Zaznacz zdanie prawdziwe:
-
○
Liczby Fibonacciego są przykładem zależności rekurencyjnej rzędu drugiego niejednorodnej.
-
○
Ciąg liczb harmonicznych jest zbudowany z liczb całkowitych.
-
✓
Za pomocą liczb Stirlinga pierwszego rodzaju $s(n, k)$, $k = 0, 1, \dots, n$, można obliczyć wartość funkcji $n!$.
-
○
Liczby Eulera związane są z liczbą $k$-elementowych podzbiorów zbioru $n$-elementowego.
-
○
Liczby Stirlinga drugiego rodzaju związane są ze zliczaniem $k$-elementowych permutacji ze zbioru $n$-elementowego.
Pytanie 13: Zaznacz zdanie prawdziwe:
-
○
Zasada włączania i wyłączania ma postać: $\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i=1}^{n} |A_i| + \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \dots + (-1)^{n-1} |A_1 \cap A_2 \cap \dots \cap A_n|$
-
✓
Zasada włączania i wyłączania, mówi, że aby wyznaczyć liczbę elementów zbioru $A_1 \cup A_2 \cup \dots \cup A_n$, należy zanalizować wszystkie możliwe przecięcia (części wspólne) zbiorów z rodziny $\{A_1, A_2, \dots, A_n\}$ i dodać liczność przecięć nieparzystej liczby zbiorów oraz odjąć liczność przecięć parzystej liczby zbiorów.
-
○
Zasada włączania i wyłączania, mówi, że aby wyznaczyć liczbę elementów zbioru $A_1 \cap A_2 \cap \dots \cap A_n$, należy zanalizować wszystkie możliwe przecięcia zbiorów z rodziny $\{A_1, A_2, \dots, A_n\}$ i dodać liczność przecięć parzystej liczby zbiorów oraz odjąć liczność przecięć nieparzystej liczby zbiorów.
-
○
Zasada włączania i wyłączania jest uogólnieniem prawa sumy umożliwiającym obliczenie liczności części wspólnej zbiorów, bez konieczności wyznaczania elementów należących do tej części wspólnej.
-
○
Prawo sumy (pozwalające na wyznaczenie liczności sumy dwóch zbiorów) nie jest równoważne zasadzie włączania i wyłączania (pozwalającej na wyznaczenie liczności sumy zbiorów $A_1, \dots, A_n$ dla $n=2$.
Pytanie 14: Pełna poprawna zasada włączania i wyłączania dla 4 zbiorów składa się z
-
○
4 składników, ponieważ są 4 zbiory.
-
✓
15 składników.
-
○
16 składników, ponieważ należy sprawdzić część wspólną każdego zbioru z każdym.
-
○
5 składników.
-
○
nieskończonej liczby składników.
Pytanie 15: Zaznacz zdanie prawdziwe.
-
○
Zasada szufladkowa Dirichleta stwierdza, że jeśli skończony zbiór $S$ jest podzielony na $k$ rozłącznych niepustych podzbiorów, to dokładnie jeden z tych zbiorów zawiera $\lceil |S|/k \rceil$ elementów lub więcej.
-
○
Zasada szufladkowa Dirichleta stwierdza, że jeśli skończony zbiór $S$ jest podzielony na $k$ rozłącznych niepustych podzbiorów, to liczność tych wszystkich zbiorów wynosi co najmniej $\lfloor |S|/k \rfloor$.
-
○
Uogólniona zasada szufladkowa sprowadza się do „klasycznej” zasady szufladkowej, gdy każdy z elementów analizowanego zbioru $S$ należy do co najmniej jednego podzbioru spośród $A_1, \dots, A_k$.
-
✓
Uogólniona zasada szufladkowa Dirichleta określa minimalną wartość średniej arytmetycznej liczb elementów zbiorów $A_1, \dots, A_k$ będących podzbiorami skończonego zbioru $S$, takimi że każdy element zbioru $S$ należy do co najmniej 1 spośród zbiorów $A_i$ ($1 \leq |S|/k$).
-
○
Dowód uogólnionej zasady szufladkowej Dirichleta wymaga zastosowania zwykłej zasady szufladkowej.
Pytanie 16: Jeśli zbiór 12 elementowy zostanie podzielony w dowolny sposób na 3 niepuste rozłączne podzbiory, to
-
○
dokładnie jeden podzbiór zawiera 4 elementy lub więcej.
-
○
dokładnie jeden podzbiór zawiera 4 elementy.
-
○
co najwyżej jeden podzbiór zawiera 4 elementy lub więcej.
-
✓
co najmniej jeden podzbiór zawiera 4 elementy lub więcej.
-
○
podzbiory są równoliczne.
Pytanie 17: Zaznacz zdanie prawdziwe.
-
○
Macierz o wymiarze $p \times p$ zbudowaną z elementów ze zbioru $\{1, \dots, n\}$, gdzie $p < n$, w której w żadnym wierszu i kolumnie elementy się nie powtarzają nazywamy kwadratem łacińskim.
-
✓
Rozszerzenie prostokąta łacińskiego $p \times q$ ($p \leq n$, $q < n$) do kwadratu $n \times n$ nie jest możliwe, jeśli dla pewnego elementu $l$ ($1 \leq l \leq n$) liczba jego wystąpień w prostokącie $l(l)$ jest mniejsza od $p + q - n$.
-
○
Rozszerzenie dowolnego prostokąta łacińskiego o dodatkowe kolumny jest zawsze możliwe, należy jedynie w każdej nowej kolumnie umieszczać elementy występujące najrzadziej.
-
○
Rozszerzalny prostokąt łaciński $p \times q$ rozbudowuje się do kwadratu łacińskiego $n \times n$ przez dopisanie najpierw $(n-q)$ wierszy, a następnie $(n-p)$ kolumn.
-
○
Dla $n$ będącego liczbą pierwszą istnieje dokładnie $n-1$ wzajemnie ortogonalnych kwadratów łacińskich o wymiarze $n \times n$, a dla $n$ będącego potęgą liczby pierwszej co najmniej $n-1$ wzajemnie ortogonalnych kwadratów łacińskich o wymiarze $n \times n$.
Pytanie 18: Zaznacz zdanie prawdziwe:
-
○
Dla dowolnej szachownicy $B$, wartość współczynnika $r_1$ jest równa liczbie zabronionych pól obszaru $B$.
-
✓
Wielomian szachowy dla obszaru $B$ o wymiarze $n \times n$, postaci $r(x) = 1 + r_1 x + r_2 x^2 + \dots + r_n x^n$, nie zawiera niezerowych współczynników $r_k$ dla $k > n$, ponieważ nie można ustawić więcej niż $n$ wzajemnie nieatakujących się wież na szachownicy o wymiarze $n \times n$.
-
○
Każda linia pozioma dzieli dowolną szachownicę $B$ na dwa niezależne obszary, niemające wspólnych wierszy ani kolumn.
-
○
Jeśli szachownica $B$ składa się z dwóch niezależnych obszarów $C, D$, to wówczas $r(x) = r(C) + x r(D)$.
-
○
W oparciu o wielomian szachowy obszaru $B$ można wyznaczyć wszystkie współczynniki wielomianu szachowego dla dopełnienia tego obszaru $\overline{B}$.
Pytanie 19: Zaznacz zdanie prawdziwe.
-
○
$k$-wyrazową wariacją z powtórzeniami ze zbioru $n$-elementowego nazywamy każdy $k$-wyrazowy ciąg elementów tego zbioru, a liczba takich wariacji wynosi: $\frac{n!}{(n-k)!}$, gdzie $k < n$ lub $k \geq n$.
-
○
Liczba $k$-wyrazowych wariacji z powtórzeniami jest równa liczbie $k$-wyrazowych permutacji z powtórzeniami.
-
✓
$k$-wyrazowa wariacja z powtórzeniami ze zbioru $n$-elementowego odpowiada rozmieszczeniu $k$ rozróżnialnych elementów w $n$ rozróżnialnych pudełkach.
-
○
Liczba $k$-wyrazowych wariacji z powtórzeniami ze zbioru $n$-elementowego jest nie większa od liczby $k$-wyrazowych wariacji bez powtórzeń.
-
○
Istnieje $b^b$ różnych $b$-wyrazowych wariacji z powtórzeniami ze zbioru $a$-elementowego $(a \leq b$ lub $b < a)$.
Pytanie 20: Obiekty kombinatoryczne $D, C, A, B$ i $A, D, C, B$ zostały utworzone ze zbioru $\{A, B, C, D, E\}$ i nie są identyczne (można je odróżnić). Podane obiekty mogą być przykładem:
-
○
4-elementowej kombinacji z powtórzeniami ze zbioru 5-elementowego.
-
○
5-elementowej wariacji z powtórzeniami ze zbioru 4-elementowego.
-
✓
4-elementowej wariacji bez powtórzeń ze zbioru 5-elementowego.
-
○
Uporządkowanego podziału zbioru na dwa podzbiory.
-
○
4-elementowej kombinacji bez powtórzeń ze zbioru 5-elementowego.
Pytanie 21: Zaznacz zdanie prawdziwe.
-
○
Kombinacja $k$-elementowa z powtórzeniami ze zbioru $n$-elementowego, to $k$-elementowy podzbiór elementów tego zbioru, w którym kolejność elementów nie jest istotna.
-
○
Każda $k$-elementowa kombinacja z powtórzeniami ze zbioru $n$-elementowego może być przedstawiona jako $k$-elementowa permutacja z powtórzeniami ze zbioru $n$-elementowego.
-
✓
Każda $k$-elementowa kombinacja z powtórzeniami ze zbioru $n$-elementowego może być interpretowana jako rozmieszczenie $k$ identycznych elementów w $n$ rozróżnialnych pudełkach.
-
○
Każda $k$-elementowa kombinacja z powtórzeniami ze zbioru $n$-elementowego może być przedstawiona jako permutacja z powtórzeniami dwóch różnych symboli powtarzających się odpowiednio $n$ i $k$ razy.
-
○
Liczba wszystkich $k$-elementowych kombinacji z powtórzeniami ze zbioru $n$-elementowego wynosi $\binom{k + n - 1}{n}$ gdzie $k < n$.
Pytanie 22: Do 6 rozróżnialnych pudełek wrzucane są w dowolny sposób 4 rozróżnialne elementy. Każdy sposób wrzucenia elementów do pudełek jest przykładem:
-
✓
4-elementowej wariacji z powtórzeniami ze zbioru 6-elementowego.
-
○
6-elementowej permutacji z powtórzeniami ze zbioru 4-elementowego.
-
○
4-elementowej kombinacji z powtórzeniami ze zbioru 6-elementowego.
-
○
4-elementowej wariacji bez powtórzeń ze zbioru 6-elementowego.
-
○
6-elementowej kombinacji z powtórzeniami ze zbioru 4-elementowego.
Pytanie 23: Zaznacz zdanie prawdziwe.
-
✓
Pierwsza zasada indukcji matematycznej może być sformułowana następująco $[S(1) \land (\forall_{k\geq 1} S(k) \Rightarrow S(k+1))] \Rightarrow \forall_{n\geq1} S(n)$, gdzie $S(n)$ oznacza zdanie otwarte, w którym występuje pewna liczba całkowita dodatnia $n$.
-
○
Pierwsza zasada indukcji może być podana dla dowolnego elementu $n_0$, od którego rozpoczyna się proces indukcyjny i przyjmuje wówczas postać $[S(n_0) \land (S(k) \Rightarrow S(k+1))] \Rightarrow \forall_{n \geq n_{0}} S(n)$.
-
○
Dowód kroku indukcyjnego w pierwszej zasadzie indukcji matematycznej wymaga wykazania prawdziwości zdania $S(k)$ i prawdziwości zdania $S(k+1)$ dla pewnej liczby $k \geq 1$.
-
○
Dowód warunku początkowego w pierwszej zasadzie indukcji matematycznej wymaga pokazania prawdziwości zdania $S(n)$ dla dowolnego elementu $n \geq n_0$.
-
○
Dowód kroku indukcyjnego w pierwszej zasadzie indukcji matematycznej wymaga wykazania prawdziwości zdania $S(k)$ i prawdziwości zdania $S(k+1)$ dla każdej liczby $k \geq n_0$.
Pytanie 24: Zasada indukcji matematycznej może być zastosowana do dowodzenia twierdzeń $S(n)$, w którym $n$ należy do zbioru:
-
○
liczb rzeczywistych dodatnich.
-
✓
liczb naturalnych.
-
○
dowolnego podzbioru zbioru liczb wymiernych.
-
○
liczb całkowitych.
-
○
liczb rzeczywistych.
Pytanie 25: Zaznacz zdanie prawdziwe.
-
○
Rozwiązanie zależności liniowej jednorodnej rzędu drugiego ze stałymi współczynnikami o równaniu charakterystycznym o dwóch różnych pierwiastkach $x_1$ i $x_2$ ma postać $a_n = x_1 r_1^n + x_2 r_2^n$.
-
✓
Każda zależność postaci $c_n a_n + c_{n-1} a_{n-1} + \ldots + c_{n-k} a_{n-k} = 0$, gdzie $c_i$ dla $i = n-k, \ldots, n$ są zupełnie dowolnymi stałymi rzeczywistymi, jest liniową zależnością rekurencyjną rzędu $k$-tego.
-
○
Rozwiązanie liniowej jednorodnej zależności rekurencyjnej rzędu pierwszego ze stałymi współczynnikami postaci $a_{n+1} + c a_n = 0$ jest dane wzorem $a_n = a_0 b^n$, gdzie $b = -c$, a $c$ oznacza pewną stałą i nie $\in \mathbb{N}$.
-
○
Rozwiązanie zależności rekurencyjnej polega na wyznaczeniu wartości liczbowej elementu ciągu występującego po elementach początkowych.
-
○
Zależność postaci $c_n a_n + c_{n-1} a_{n-1} + c_{n-2} a_{n-2} = 1$, gdzie $c_n, c_{n-1}, c_{n-2}$ są pewnymi stałymi, $c_n \neq 0$ i $c_{n-2} \neq 0$, może być rozwiązana za pomocą metody równania charakterystycznego.
Pytanie 26: Zależność rekurencyjna $ (a_0 = 0, a_1 = 3, a_2 = 4, a_3 = 6, 2a_{n} + 3a_{n-4} = 2 $ dla $ n \geq 4 $ jest zależnością rekurencyjną:
-
○
liniową ze stałymi współczynnikami rzędu drugiego jednorodną.
-
○
liniową ze stałymi współczynnikami rzędu pierwszego niejednorodną.
-
✓
liniową ze stałymi współczynnikami rzędu czwartego niejednorodną.
-
○
liniową ze stałymi współczynnikami rzędu czwartego jednorodną.
-
○
którą można rozwiązać za pomocą metody równania charakterystycznego.
Pytanie 27: Zależność rekurencyjna $ (a_0 = 1, a_1 = 2, a_2 = 3, a_3 = 4, a_{n+1} + 5a_{n-1} - 4a_{n-3} = 0) $ dla $ n \geq 3 $ jest zależnością:
-
○
która nie może być rozwiązana metodą równania charakterystycznego.
-
○
dla której równanie charakterystyczne jest równaniem kwadratowym.
-
○
nieliniową.
-
✓
dla której równanie charakterystyczne jest równaniem stopnia czwartego.
-
○
niejednorodną.
Pytanie 28: Zaznacz zdanie prawdziwe.
-
✓
Wyrażenia postaci $x(n, n) = 1, n \geq 0$ oraz $x(n, 0) = 0, n > 0$ są składnikami definicji rekurencyjnej liczb Stirlinga zarówno pierwszego ($x = s$), jak i drugiego rodzaju ($x = S$).
-
○
Z definicji przyjmuje się, że liczba Stirlinga pierwszego rodzaju $s(n, n) = 1$ dla $n \geq 0$, ponieważ opisywane przez nią rozmieszczenie obiektów w cyklach jest niemożliwe.
-
○
Liczby Eulera drugiego rzędu $\left\langle\left\langle \begin{array}{c} n \\ k \end{array} \right\rangle\right\rangle$ oznaczają liczbę dowolnych permutacji z powtórzeniami ze zbioru $n$-elementowego zawierających $k$ wniesień takich, że pomiędzy poszczególnymi wystąpieniami pewnej liczby znajdują się tylko liczby większe od niej.
-
○
Liczby harmoniczne drugiego rzędu $H_n^{(2)}$ są dyskretnym odpowiednikiem funkcji $f(x) = \frac{1}{x}$.
-
○
W oparciu o twierdzenie Zeckendorfa można stworzyć system liczbowy, w którym dowolna liczba rzeczywista dodatnia może być przedstawiona jako $\sum_{k=0}^{m} b_k F_k$, gdzie $b_k \in \{0,1\}$, a $F_k$ oznacza liczbę Fibonacciego.
Pytanie 29: Zaznacz zdanie prawdziwe.
-
○
Liczby Stirlinga drugiego rodzaju dotyczą podziału zbioru na cykle, a liczby Stirlinga pierwszego rodzaju podziału zbioru na podzbiory.
-
○
Liczby Eulera dotyczą wariacji z powtórzeniami.
-
✓
Cykle jedno- i dwu-elementowe są równoważne zbiorom jedno- i dwu-elementowym.
-
○
Ciąg liczb harmonicznych pierwszego rzędu jest zbieżny.
-
○
Ciąg liczb Fibonacciego jest przykładem zależności rekurencyjnej rzędu trzeciego, ponieważ w zależności rekurencyjnej występują trzy elementy ciągu.
Pytanie 30: Zaznacz zdanie prawdziwe.
-
○
Zasada włączania i wyłączania jest uogólnieniem prawa iloczynu dla więcej niż dwóch zbiorów skończonych.
-
✓
Zasada włączania i wyłączania ma postać: $ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i=1}^{n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap A_2 \cap \dots \cap A_n|$
-
○
Zasada włączania i wyłączania umożliwia obliczenie liczności części wspólnej $n$ zbiorów $A_1, A_2, ..., A_n$ w oparciu o liczności sum zbiorów z rodziny $\{A_1, A_2, ..., A_n\}$.
-
○
Zasadę włączania i wyłączania stosuje się do obliczenia liczności sumy pewnej liczby zbiorów w sytuacji, gdy nie można wyznaczyć elementów należących do tej sumy.
-
○
Zasadę włączania i wyłączania można zastosować wyłącznie do obliczenia liczności sumy zbiorów, których części wspólne nie są zbiorami pustymi; zasady tej nie można zastosować dla zbiorów rozłącznych.
Pytanie 31: Poprawna pełna zasada włączania i wyłączania dla zbioru $N$ elementowego, którego pewne elementy spełniają własności $c_i, (i = 1,2,3)$ ma postać:
-
○
$N(c_1 \vee c_2 \vee c_3) = N(c_1) + N(c_2) + N(c_3)$
-
○
$N(c_1 c_2 c_3) = N(c_1) + N(c_3) - N(c_1 c_3)$
-
○
$N(\overline{c_1} \overline{c_2} \overline{c_3}) = N(c_1) + N(c_2) + N(c_3) - N(c_1 c_2) - N(c_1 c_3) - N(c_2 c_3) + N(c_1 c_2 c_3)$
-
✓
$N(\overline{c_1} \overline{c_2} \overline{c_3}) = N - N(c_1) - N(c_2) - N(c_3) + N(c_1 c_2) + N(c_1 c_3) + N(c_2 c_3) - N(c_1 c_2 c_3)$
-
○
$N(c_1 c_2 c_3) = N - N(c_1) - N(c_2) - N(c_3) + N(c_1 c_2) + N(c_1 c_3) + N(c_2 c_3)$
Pytanie 32: Zaznacz zdanie prawdziwe:
-
○
Zasada szufladkowa Dirichleta mówi, że jeśli skończony zbiór $S$ jest podzielony na $k$ rozłącznych niepustych podzbiorów, to co najwyżej jeden z tych podzbiorów zawiera $\lceil \frac{|S|}{k} \rceil$ elementów lub więcej.
-
○
Zasada szufladkowa Dirichleta wynika z obserwacji, że jeśli $m$ przedmiotów umieszcza się w zupełnie dowolny sposób w $n$ szufladkach i $m > n$, to żadna szufladka nie będzie pusta.
-
○
„Klasyczna” zasada szufladkowa dotyczy podziału zbioru $S$ na dwa zbiory, a uogólniona zasada szufladkowa dotyczy podziału na dowolną liczbę zbiorów.
-
✓
Uogólniona zasada szufladkowa Dirichleta mówi, że jeśli skończony zbiór $S$ jest podzielony na $k$ podzbiorów $A_1, A_2, ..., A_k$, takich że każdy element $S$ należy do co najmniej $p$ spośród tych podzbiorów, to średnia liczność zbiorów $A_i$ wynosi co najmniej $\frac{p |S|}{k}$.
-
○
Z uogólnionej zasady szufladkowej Dirichleta wynika, że jeśli skończony zbiór $S$ jest podzielony na $k$ podzbiorów $A_1, A_2, ..., A_k$, takich że każdy element $S$ należy do dokładnie $t$ spośród tych podzbiorów, to średnia liczność zbiorów $A_i$ wynosi dokładnie $\frac{k |S|}{t}$.
Pytanie 33: Średnia liczność zbiorów $A_1, A_2, A_3, A_4$ będących podzbiorami zbioru 8-elementowego $S$, takimi, że każdy element $S$ należy do co najmniej 3 podzbiorów wynosi:
-
○
co najwyżej 6.
-
○
dokładnie 6.
-
○
co najwyżej 3.
-
○
co najmniej 8.
-
✓
co najmniej 6.
Pytanie 34: Zaznacz zdanie prawdziwe.
-
✓
Macierz o wymiarze $p \times p$ zbudowana z elementów ze zbioru $\{1, ..., n\}$, gdzie $p < n$, w której w żadnym wierszu i kolumnie elementy się nie powtarzają jest prostokątem łacińskim.
-
○
Rozszerzenie prostokąta łacińskiego $p \times q$ do kwadratu $n \times n$ jest możliwe tylko wówczas, jeśli liczba wystąpień poszczególnych elementów spełnia warunek $l(i) > p + q - n$ dla każdego $i = 1, ..., n$.
-
○
Rozszerzenie prostokąta łacińskiego $p \times q$ do kwadratu $n \times n$ jest zawsze możliwe i wymaga wyznaczenia transwersali rodziny zbiorów zawierających elementy nie występujące dotychczas odpowiednio w poszczególnych wierszach i kolumnach.
-
○
Prostokąt łaciński $p \times q$ rozbudowuje się do kwadratu łacińskiego $n \times n$ przez dopisanie najpierw $(n - p)$ wierszy zbudowanych z dowolnej transwersali, a następnie $(n - q)$ kolumn zbudowanych ze specyficznej transwersali zawierającej zbiór $P$.
-
○
Dla $n$ będącego liczbą pierwszą lub potęgą liczby pierwszej istnieje co najwyżej $n - 1$ wzajemnie ortogonalnych kwadratów łacińskich o wymiarze $n \times n$, a dla pozostałych wartości $n$ istnieje dokładnie $n - 1$ wzajemnie ortogonalnych kwadratów łacińskich o wymiarze $n \times n$.
Pytanie 35: Zaznacz obiekt nie będący prostokątem łacińskim ze zbioru $\{1,\ldots,6\}$:
-
○
$[1, 2, 3, 4, 5, 6]$
-
○
$\begin{bmatrix}2 & 1 \\3 & 4 \\5 & 6 \\1 & 2 \\6 & 3 \\4 & 5\end{bmatrix}$
-
○
$\begin{bmatrix}3 & 1 & 2 \\2 & 3 & 1 \\1 & 2 & 6\end{bmatrix}$
-
✓
$\begin{bmatrix}1 & 2 & 3 & 4 & 5 & 6 \\6 & 5 & 4 & 3 & 2 & 1 \\5 & 4 & 3 & 2 & 1 & 6 \\4 & 3 & 2 & 1 & 6 & 5 \\3 & 6 & 5 & 1 & 3 & 4\end{bmatrix}$
-
✓
$\begin{bmatrix}6 & 5 & 4 & 3 \\3 & 1 & 5 & 1 \\1 & 3 & 2 & 6 \\2 & 3 & 5 & 1\end{bmatrix}$
Pytanie 36: Zaznacz zdanie prawdziwe.
-
✓
Wielomian szachowy $r_B(x) = 1 + r_1x + r_2x^2 + ... + r_kx^k + ... + r_nx^n$, to funkcja tworząca, której współczynniki $r_k$ oznaczają liczbę możliwych rozmieszczeń $k$ wzajemnie nie atakujących się wież na szachownicy $B$ o wymiarze $n \times n$.
-
○
W wielomianie szachowym dla dowolnej szachownicy o wymiarze $n \times n$ mogą wystąpić niezerowe współczynniki $r_k$ dla $k > n$.
-
○
Każdą szachownicę $B$ można zdekomponować na dwie inne szachownice $B^1$ i $B^2$, takie że w $B^1$ zabroniona jest kolumna, a w $B^2$ wiersz, zawierające pewne dowolnie wybrane pole $s$.
-
○
Jeśli szachownica $B$ składa się z dwóch niezależnych obszarów $B^1$ i $B^2$, to wówczas $r_B(x)$ jest sumą wielomianów szachowych obszarów $B^1$ i $B^2$.
-
○
Dekompzycję wielomianów stosuje się jedynie wówczas, gdy nie wyznacza się pełnego wielomianu szachowego pewnego obszaru o wymiarze $n \times n$, ale oblicza się jedynie pojedynczy współczynnik tego wielomianu $r_k$ dla $k < n$.
Pytanie 37: Zaznacz funkcję tworzącą, która może być wielomianem szachowym pewnej szachownicy o wymiarze 5×5:
-
✓
$r_B(x) = 1 + 15x + 75x^2 + 145x^3 + 96x^4 + 12x^5$
-
○
$r_B(x) = 0 + 15x + 75x^2 + 145x^3 + 96x^4 + 12x^5$
-
○
$r_B(x) = 1 + 15x + 75x^2 + 145x^3 + 96x^4 + 12x^6$
-
○
$r_B(x) = 2 + 15x + 75x^2 + 145x^3 + 96x^4 + 12x^5$
-
○
$r_B(x) = 1 + 27x + 75x^2 + 145x^3 + 96x^4 + 12x^5$
Pytanie 38: Niech $A, B$ i $C$ będą podzbiorami pewnej przestrzeni $U$. Wśród poniższych zdań wskaż prawa algebry zbiorów.
-
○
$\overline{A \cap B} = \overline{A} \cap \overline{B}$
-
✓
$(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$
-
✓
$(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$
-
○
$\overline{A \cup B} = \overline{A} \cup \overline{B}$
-
○
$\overline{A \cup B} = \overline{A \cap B}$
Pytanie 39: Zaznacz wszystkie zdania prawdziwe.
-
○
Relację, która jest jednocześnie relacją przechodnią, symetryczną i spójną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.
-
○
Relację, która jest jednocześnie relacją przechodnią, symetryczną i przeciwzwrotną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.
-
○
Relację, która jest jednocześnie relacją przechodnią, antysymetryczną i spójną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.
-
○
Relację, która jest jednocześnie relacją zwrotną, antysymetryczną i spójną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.
-
○
Relację, która jest jednocześnie relacją zwrotną, przechodnią i antysymetryczną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.
Pytanie 40: Wśród poniższych zdań wskaż wszystkie zdania będące definicjami odpowiednich obiektów:
-
✓
Słowem danego alfabetu $\Sigma$ jest dowolny skończony ciąg liter zbioru $\Sigma$.
-
✓
Jeżeli przez $\Sigma^*$ oznaczymy zbiór wszystkich słów zbudowanych z liter alfabetu $\Sigma$, to dowolny podzbiór zbioru $\Sigma^*$ jest językiem nad alfabetem $\Sigma$.
-
○
Językiem nad alfabetem $\Sigma$ jest zbiór potęgowy zbioru $\Sigma$.
-
○
Słowem danego alfabetu $\Sigma$ jest dowolny skończony ciąg liter zbioru $\Sigma$, który zawiera co najwyżej jedno wystąpienie każdego z elementów zbioru $\Sigma$.
-
○
Jeżeli przez $\Sigma^*$ oznaczymy zbiór wszystkich słów zbudowanych z liter alfabetu $\Sigma$, to językiem nad alfabetem $\Sigma$ jest $\Sigma^* \times \Sigma^*$.
Pytanie 41: Niech $G=(V,E)$ będzie dowolnym grafem i niech $X,Y \subseteq V$. Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.
-
✓
Minimalna liczba wierzchołków, które rozdzielają $X$ od $Y$ równa jest maksymalnej liczbie rozłącznych ścieżek z $X$ do $Y$.
-
○
Minimalna liczba wierzchołków, które rozdzielają $X$ od $Y$ równa jest minimalnej liczbie rozłącznych ścieżek z $X$ do $Y$.
-
○
Minimalna liczba wierzchołków, które rozdzielają $X$ od $Y$ równa jest liczności zbioru $X$.
-
○
Minimalna liczba wierzchołków, które rozdzielają $X$ od $Y$ równa jest liczności zbioru $Y$.
-
○
Minimalna liczba wierzchołków, które rozdzielają $X$ od $Y$ równa jest $\min{|X|, |Y|}$.
Pytanie 42: Obiekty $|A, C, D, E|$ i $|B, E, F, F|$ utworzono ze zbioru $\{A, B, C, D, E, F\}$. Kolejność tych obiektów oraz uporządkowanie ich elementów nie są istotne. Obiekty te są przykładem:
-
○
podziału uporządkowanego zbioru $\{A, B, C, D, E, F\}$ ponieważ elementy w obiektach są ustawione alfabetycznie.
-
○
podziału zbioru $\{A, B, C, D, E, F\}$ na dwa podzbiory.
-
○
dwóch 4-elementowych wariacji bez powtórzeń ze zbioru 6-elementowego.
-
○
dwóch 4-elementowych permutacji bez powtórzeń ze zbioru 6-elementowego.
-
✓
dwóch 4-elementowych kombinacji z powtórzeniami ze zbioru 6-elementowego.
Pytanie 43: Zaznacz zdania prawdziwe.
-
○
Wszystkie $k$-elementowe kombinacje bez powtórzeń z $n$-elementowego zbioru, dla $k=0, \ldots, n$, mogą być wygenerowane za pomocą generacji ze wszystkich liczb binarnych z zakresu od $1$ do $2^n$.
-
○
Każde rozmieszczenie $k$ identycznych elementów w $n$ rozróżnialnych pudełkach odpowiada $k$-elementowej kombinacji bez powtórzeń ze zbioru $n$-elementowego.
-
✓
Z każdej $k$-elementowej kombinacji bez powtórzeń ze zbioru $n$-elementowego można utworzyć $k!$ różnych $k$-wyrazowych wariacji bez powtórzeń ze zbioru $n$-elementowego.
-
○
Liczba wszystkich $k$-elementowych kombinacji bez powtórzeń z $n$-elementowego zbioru wynosi $\binom{n}{k}$ gdzie $n \leq k$ lub $k < n$
-
○
Każda $k$-elementowa kombinacja bez powtórzeń ze zbioru $n$-elementowego odpowiada pewnemu podziałowi tego zbioru na $k$ podzbiorów.
Pytanie 44: Do 7 rozróżnialnych pudełek można wrzucić (w dowolny sposób) 4 identyczne elementy na
-
○
$\binom{7}{4}$ sposobów.
-
○
$7^4$ sposobów.
-
✓
$\binom{7+4-1}{4}$ sposobów.
-
○
$4^7$ sposobów.
-
○
$\frac{7!}{(7-4)!}$ sposobów.
Pytanie 45: Zaznacz zdania prawdziwe.
-
○
$k$-wyrazową permutacją z powtórzeniami ze zbioru $n$-elementowego nazywamy każdy $k$-wyrazowy ciąg mogących się powtarzać elementów tego zbioru.
-
○
Permutacja z powtórzeniami może być interpretowana jako dowolne rozmieszczenie $n$ rozróżnialnych obiektów w $k$ rozróżnialnych pudełkach.
-
○
$k$-wyrazowe permutacje z powtórzeniami są równoważne $k$-wyrazowym wariacjom z powtórzeniami.
-
✓
Liczba $k$-wyrazowych permutacji z powtórzeniami jest nie większa niż liczba $k$-wyrazowych permutacji bez powtórzeń.
-
○
W $n$-elementowej permutacji z powtórzeniami ze zbioru $\{a_1, \dots, a_n\}$, w której element $a_i$ powtarza się $n_i$ razy, dla $i = 1, \dots, k$, zachodzi: $\sum_{i=1}^{k}{n_i=n!}$.
Pytanie 46: Zaznacz zdania prawdziwe.
-
○
Rozwiązanie liniowej jednorodnej zależności rekurencyjnej rzędu pierwszego ze stałymi współczynnikami postaci $a_{n+1} + ca_n = 0$ jest dane wzorem $a_n = ca_0^n$, gdzie $c$ oznacza pewną stałą i $n \in \mathbb{N}$.
-
○
Rozwiązanie zależności liniowej jednorodnej rzędu drugiego ze stałymi współczynnikami o równaniu charakterystycznym o jednym pierwiastku podwójnym ma postać $a_n = c_1 r^n + c_2 n r^n$, gdzie wartości stałych $c_1$ i $c_2$ są wyznaczane w oparciu o początkowe elementy ciągu.
-
✓
Rozwiązanie problemu wież z Hanoi, $T_n = 2T_{n-1} + 1, n > 0, T_0 = 0$, jest przykładem niejednorodnej liniowej zależności rekurencyjnej rzędu pierwszego ze stałymi współczynnikami.
-
○
Zależność postaci $c_n a_n + c_{n-1} a_{n-1} + \dots + c_k a_k = 0$, gdzie $c_i$ dla $i = n, \dots, k$ są pewnymi stałymi rzeczywistymi, $c_n \neq 0$ i $c_k \neq 0$ nazywamy liniową jednorodną zależnością rekurencyjną rzędu k-tego ze stałymi współczynnikami.
-
○
Każdy pierwiastek pojedynczy $r$ równania charakterystycznego wprowadza do rozwiązania liniowej jednorodnej zależności rekurencyjnej ze stałymi współczynnikami rzędu $k \geq 2$ czynnik $rc^n$, gdzie $c$ jest pewną stałą, którą można wyznaczyć w oparciu o początkowe wyrazy ciągu.
Pytanie 47: Zależność rekurencyjna $\{a_0 = 0, a_1 = 3, a_2 = 4, a_{n+1}+3a_{n-2} = 3n \text{ dla } n \geq 2\}$ jest zależnością rekurencyjną liniową ze stałymi współczynnikami:
-
○
rzędu drugiego jednorodną,
-
○
rzędu drugiego niejednorodną,
-
○
rzędu trzeciego jednorodną,
-
✓
rzędu trzeciego niejednorodną,
-
○
rzędu $(n+1)$-szego jednorodną.
Pytanie 48: Zależność rekurencyjna $\{a_0 = 1, a_1 = 2, na_n = 3a_{n-1}\cdot a_{n-2}=0 \text{ dla } n \geq 2\}$ jest zależnością:
-
○
niejednorodną,
-
○
dla której równanie charakterystyczne jest równaniem kwadratowym,
-
○
o stałych współczynnikach,
-
✓
która nie może być rozwiązana metodą równania charakterystycznego,
-
○
dla której równanie charakterystyczne jest równaniem stopnia trzeciego.
Pytanie 49: Zaznacz zdania prawdziwe:
-
○
Pierwsza zasada indukcji matematycznej dla pewnego $n_0 \in \mathbb{Z}^{+}$ ma postać: $[S(n_0) \land [\forall_{k \geq 1} [S(k) \implies S(k+1)]]] \implies \forall_{n \geq 1} S(n)$.
-
○
Pierwszą zasadę indukcji matematycznej stosuje się do dowodzenia twierdzeń, w których prawdziwość pewnego zdania wynika z prawdziwości jednego, dowolnego ze zdań poprzedzających.
-
✓
Pierwsza zasada indukcji matematycznej dla $n_0 = 1$ ma postać: $[(\forall_{k \geq 1} [S(k) \implies S(k + 1)]) \land S(1)] \implies \forall_{n \in \mathbb{Z}^{+}} S(n)$.
-
○
Zasada indukcji matematycznej może być wykorzystana do dowodzenia twierdzeń dotyczących dowolnych liczb dodatnich.
-
○
Jeśli pewne twierdzenie $\forall_{n \in \mathbb{Z}^{+}} S(n)$ nie jest prawdziwe dla pewnych początkowych wartości $n \geq 1$, to może ono być udowodnione z wykorzystaniem drugiej zasady indukcji matematycznej.
Pytanie 50: Zaznacz zdania prawdziwe.
-
○
Pierwsza i druga zasada indukcji matematycznej są sobie równoważne tylko dla pewnego rodzaju twierdzeń.
-
○
Dowód kroku indukcyjnego w pierwszej zasadzie indukcji matematycznej wymaga wykazania prawdziwości zdania $S(k)$ i prawdziwości zdania $S(k+1)$ dla pewnej liczby $k \geq 1$.
-
○
Dowód pierwszej zasady indukcji matematycznej nie dowodzi poprawności drugiej zasady indukcji matematycznej, ponieważ jest ona inaczej sformułowana.
-
○
Pierwszą zasadę indukcji matematycznej stosuje się do dowodzenia twierdzeń, w których prawdziwość pewnego zdania wynika z prawdziwości jednego ze zdań poprzedzających.
-
✓
Drugą zasadę indukcji matematycznej można zastosować do dowodzenia twierdzeń dotyczących liczb całkowitych dodatnich, w których prawdziwość zdania $S(n)$ dla $n=k+1$ wynika z prawdziwości kilku zdań poprzedzających.
Pytanie 51: Zaznacz zdania prawdziwe.
-
○
Definicja rekurencyjna liczb Stirlinga drugiego rodzaju zawiera zależność postaci: $S(n, k) = S(n-1, k) + k S(n-1, k-1)$, a definicja rekurencyjna liczb Stirlinga pierwszego rodzaju: $s(n, k) = s(n-1, k) + (n-1) s(n-1, k-1)$ (gdzie $n > k > 0$).
-
✓
Liczby Stirlinga drugiego rodzaju opisujące liczbę sposobów podziału zbioru $n$-elementowego na $k$ niepustych rozłącznych podzbiorów są nie większe niż liczby Stirlinga pierwszego rodzaju opisujące liczbę sposobów rozmieszczenia $n$ elementów w $k$ cyklach.
-
○
Liczby Eulera drugiego rzędu $\left\langle \left\langle \begin{matrix} n \\ k \end{matrix} \right\rangle \right\rangle$ oznaczają liczbę permutacji z powtórzeniami multizbioru $\{1, 1, 2, 2, \dots, k, k\}$ zawierających $n$ wniesień.
-
○
Liczby harmoniczne pierwszego rzędu tworzą ciąg zbieżny do pewnej granicy, ponieważ zgodnie z definicją rekurencyjną każda kolejna liczba $H_{n+1}$ powstaje z poprzedniej liczby $H_{n}$ przez dodanie ułamka $\frac{1}{(n+1)}$.
-
○
W systemie liczbowym Fibonacciego, zbudowanym w oparciu o twierdzenie Zeckendorfa, do jednoznacznej reprezentacji liczb całkowitych dodatnich wykorzystuje się wszystkie liczby Fibonacciego $F_k$, dla $k \geq 0$.
Pytanie 52: Zaznacz zdania prawdziwe.
-
○
W ciągu liczby Stirlinga drugiego rodzaju mogą pojawić się liczby nie będące liczbami całkowitymi.
-
✓
Każdej $n$-elementowej permutacji bez powtórzeń ze zbioru $n$-elementowego odpowiada pewien układ cykli i każdemu układowi cykli odpowiada pewna $n$-elementowa permutacja bez powtórzeń ze zbioru $n$-elementowego.
-
○
Liczby harmoniczne rzędu $r$, dla $r > 1$, tworzą ciąg rozbieżny.
-
○
Liczby Fibonacciego są liczbami opisanymi zależnością rekurencyjną rzędu trzeciego, ponieważ w definicji występują trzy elementy ciągu.
-
○
Liczby Eulera związane są z liczbą cykli Eulera w grafie.
Pytanie 53: Pełna poprawna zasada włączania i wyłączania dla 4 zbiorów jest formułą składającą się z:
-
○
4 składników, ponieważ są 4 zbiory.
-
○
16 składników, ponieważ należy sprawdzić część wspólną każdego zbioru z każdym.
-
✓
15 składników.
-
○
8 składników.
-
○
nieznanej liczby składników, ponieważ ich liczba zależy od liczności tych zbiorów.
Pytanie 54: Zaznacz zdania prawdziwe.
-
○
Zasada włączania i wyłączania mówi, że liczba elementów pewnego zbioru $S$, $|S| = N$, które nie spełniają żadnego z warunków $c_i$, $1 \leq i \leq t$, jest równa $N = N - N(c_1) - N(c_2) - ... - N(c_t)$, gdzie $N(c_i)$ oznacza liczbę elementów $S$ spełniających warunek $c_i$.
-
○
Zasada włączania i wyłączania w postaci alternatywnej dotyczy pewnego zbioru $S$, dla którego zdefiniowane są warunki $c_i$, $1 \leq i \leq t$, które muszą być spełnione przez wszystkie elementy zbioru $S$.
-
✓
Dla zbioru $S$ i warunków $c_i$, $1 \leq i \leq t$, spełnionych przez pewne elementy ze zbioru $S$, liczba elementów, które nie spełniają żadnego z tych warunków wynosi: $N(\overline{c_1} \overline{c_2} ... \overline{c_t}) = |S| - \sum_{1 \leq i \leq t} N(c_i) + \sum_{1 \leq i < j \leq t} N(c_i c_j) - \sum_{1 \leq i < j < k \leq t} N(c_i c_j c_k) + \dots + (-1)^t N(c_1 c_2 ... c_t)$.
-
○
Symbol $N(c_i c_j)$ występujący w zasadzie włączania i wyłączania oznacza liczbę elementów ze zbioru $S$ spełniających warunki $c_i$ i $c_j$ i równocześnie nie spełniających pozostałych warunków $c_k$, $(1 \leq i, j, k \leq t, k \neq i, k \neq j)$.
-
○
Dowód zasady włączania i wyłączania w postaci alternatywnej jest oparty o prawa teorii mnogości.
Pytanie 55: Zaznacz zdania prawdziwe.
-
○
Zasada szufladkowa Dirichleta mówi, że jeśli skończony zbiór $S$ jest podzielony na $k$ rozłącznych niepustych podzbiorów, to każdy z tych podzbiorów zawiera $\lceil |S| / k \rceil$ elementów lub więcej.
-
○
Dowód zasady szufladkowej Dirichleta wykorzystuje pojęcie uporządkowanego podziału zbioru.
-
○
„Klasyczna” zasada szufladkowa Dirichleta w żaden sposób nie wynika z uogólnionej zasady szufladkowej Dirichleta, ponieważ dotyczy zbiorów o odmiennych własnościach.
-
✓
Z zasady szufladkowej Dirichleta wynika, że jeśli skończony zbiór $S$ jest podzielony na $k$ rozłącznych niepustych podzbiorów, to średnia liczność tych zbiorów wynosi $\frac{|S|}{k}$.
-
○
Uogólniona zasada szufladkowa Dirichleta określa wartość średniej arytmetycznej liczb elementów zbiorów $A_1, ..., A_k$ będących rozłącznymi podzbiorami pewnego skończonego zbioru $S$.
Pytanie 56: Średnia liczność zbiorów $A_1, A_2, A_3, A_4, A_5, A_6$ będących podzbiorami zbioru 18-elementowego $S$, takimi, że każdy element $S$ należy do dokładnie 3 podzbiorów wynosi:
-
○
nie może być określona.
-
✓
dokładnie 9.
-
○
co najwyżej 9.
-
○
co najmniej 9.
-
○
dokładnie 3.
Pytanie 57: Zaznacz zdania prawdziwe.
-
✓
Rozszerzenie prostokąta łacińskiego $n \times q$ do kwadratu $n \times n$ jest zawsze możliwe i wymaga wyznaczenia transwersali rodziny zbiorów zawierających elementy nie występujące dotychczas w poszczególnych wierszach.
-
○
Każda macierz o wymiarze $p \times q$ zbudowana z elementów ze zbioru $\{1, \dots, n\}$, gdzie $\min(p, q) < n$, w której w żadnym wierszu elementy się nie powtarzają jest prostokątem łacińskim.
-
○
Rozszerzenie dowolnego prostokąta łacińskiego o dodatkowe kolumny jest zawsze możliwe, należy jedynie w każdej nowej kolumnie umieszczać elementy występujące najrzadziej.
-
○
Pewne prostokąty łacińskie $p \times n$, w których liczba wystąpień niektórych elementów jest zbyt mała, nie mogą być rozszerzone do kwadratu łacińskiego $n \times n$.
-
○
Kwadratem grecko-łacińskim, czyli kwadratem Eulera, nazywamy złożenie dwóch dowolnych kwadratów łacińskich o takim samym rozmiarze.
Pytanie 58: Dany jest poniższy prostokąt łaciński $L$ ze zbioru $\{1,6\}$. Zaznacz kolumnę, której $\textbf{nie można}$ dopisać do tego prostokąta, jeśli ma być nadal rozszerzalny do kwadratu łacińskiego $6 \times 6$: $L =\begin{pmatrix}2 & 3 & 4 & 6 \\4 & 5 & 3 & 1 \\3 & 4 & 6 & 2 \\5 & 6 & 1 & 4\end{pmatrix}$
-
○
$\begin{matrix}5 \\2 \\1 \\3\end{matrix}$
-
○
$\begin{matrix}1 \\2 \\5 \\3\end{matrix}$
-
✓
$\begin{matrix}5 \\6 \\1 \\3\end{matrix}$
-
○
$\begin{matrix}5 \\6 \\1 \\2\end{matrix}$
-
○
$\begin{matrix}1 \\6 \\5 \\2\end{matrix}$
Pytanie 59: Zaznacz zdania prawdziwe.
-
○
Wielomian szachowy $r_f(x) = 1 + r_1 x + r_2 x^2 + ... + r_k x^k + ... + r_n x^n$ to funkcja, której wartość oznacza liczbę możliwych rozmieszczeń $x$ wzajemnie atakujących się wież na szachownicy o wymiarze $n \times n$.
-
○
Szachownica $B$ składa się z dwóch niezależnych obszarów $C$ i $D$, to wówczas $r_f(x) = r_C(x) + x r_D(x)$.
-
○
Dekompzycja wielomianów szachowych jest możliwa tylko i wyłącznie wówczas, jeśli daną szachownicę można podzielić na dwa rozłączne obszary nie mające wspólnych wierszy ani kolumn.
-
✓
W dowolnym wielomianie szachowym dla szachownicy o wymiarze $n \times n$ wszystkie współczynniki $r_k$ stojące przy $x^k$ dla $k > n$ przyjmują wartość zerową.
-
○
Szachownicę $B$ można zdekomponować, poprzez wybór pewnego pola dopuszczalnego $s$, na dwie szachownice $B^1$ i $B^2$, takie że w $B^1$ niedostępny jest wiersz, a w $B^2$ niedostępna jest kolumna zawierająca pole $s$.
Pytanie 60: Zaznacz funkcję tworzącą, która $\textbf{może być}$ wielomianem szachowym $\textbf{dopełnienia}$ podanej szachownicy $B$: <img src="img/zad_20_sterna_2019-2020.png" height="100" />
-
○
$r_B(x) = 1 + 15x + 35x^2 + 50x^3 + 26x^4 + 4x^5$
-
✓
$r_B(x) = 1 + 10x + 35x^2 + 50x^3 + 26x^4 + 4x^5$
-
○
$r_B(x) = 1 + 15x + 35x^2 + 50x^3 + 26x^4 + 4x^6$
-
○
$r_B(x) = 1 + 10x + 35x^2 + 50x^3 + 26x^4 + 4x^6$
-
○
$r_B(x) = 1 + 25x + 35x^2 + 50x^3 + 26x^4 + 4x^5$
Pytanie 61: Wskaż wszystkie zdania prawdziwe:
-
○
Zdania złożone $P \text{ i } Q$ są zdaniami logicznie równoważnymi, jeżeli $Q$ ma wartość logiczną prawdy zawsze wtedy, gdy $P$ ma wartość logiczną prawdy.
-
○
Zdania złożone $P \text{ i } Q$ są zdaniami logicznie równoważnymi, jeżeli $P$ ma wartość logiczną prawdy zawsze wtedy, gdy $Q$ ma wartość logiczną prawdy.
-
✓
Zdania złożone $P \text{ i } Q$ są zdaniami logicznie równoważnymi, jeżeli mają takie same wartości logiczne dla wszystkich możliwych sposobów przypisania wartości logicznych ich zmiennym zdaniowym.
-
○
Zdania złożone $P \text{ i } Q$ są zdaniami logicznie równoważnymi, jeżeli $Q$ ma wartość logiczną fałszu zawsze wtedy, gdy zdanie $P$ ma wartość logiczną fałszu.
-
○
Zdania złożone $P \text{ i } Q$ są zdaniami logicznie równoważnymi, jeżeli $P$ i $Q$ mają przeciwne wartości logiczne dla wszystkich możliwych sposobów przypisania wartości logicznych ich zmiennym zdaniowym.
Pytanie 62: Wskaż wszystkie zdania prawdziwe:
-
○
Jeżeli zdanie złożone $P$ zawiera zdanie $Q$, $R$ jest zdaniem takim, że $Q \Rightarrow R$ i w $P$ zastąpimy dokładnie jedno wystąpienie $Q$ przez $R$, to otrzymamy zdanie złożone $P_1$ takie, że $P \equiv P_1$.
-
✓
Jeżeli zdanie złożone $P$ jest tautologią i wszystkie wystąpienia pewnej zmiennej $p$ (zdania składowego) występującej w zdaniu $P$ zastąpimy zdaniem $R$, to otrzymane zdanie złożone $P_1$ będzie również tautologią.
-
○
Jeżeli zdanie złożone $P$ zawiera zdanie $Q$, $R$ jest zdaniem takim, że $Q \Rightarrow R$ i w $P$ zastąpimy dokładnie jedno wystąpienie $Q$ przez $R$, to otrzymamy zdanie złożone $P_1$ takie, że $P \equiv P_1$.
-
○
Jeżeli zdanie złożone $P$ jest zdaniem sprzecznym i wszystkie wystąpienia pewnej zmiennej $p$ (zdania składowego) występującej w zdaniu $P$ zastąpimy zdaniem $R$, to otrzymane zdanie złożone $P_1$ będzie tautologią.
-
✓
Jeżeli zdanie złożone $P$ zawiera zdanie $Q$, $R$ jest zdaniem takim, że $Q \Leftrightarrow R$ i w $P$ zastąpimy jedno lub więcej wystąpień $Q$ przez $R$, to otrzymamy zdanie złożone $P_1$ takie, że $P \equiv P_1$.
Pytanie 63: Wskaż definicję relacji równoważności:
-
○
Relację $\rho \subseteq X \times X$, która jest relacją przeciwzwrotną, symetryczną i przechodnią, nazywamy relacją równoważności.
-
✓
Relację $\rho \subseteq X \times X$, która jest relacją zwrotną, symetryczną i przechodnią, nazywamy relacją równoważności.
-
○
Relację $\rho \subseteq X \times X$, która jest relacją zwrotną, antysymetryczną i przechodnią, nazywamy relacją równoważności.
-
○
Relację $\rho \subseteq X \times X$, która jest relacją przeciwzwrotną, antysymetryczną i przechodnią, nazywamy relacją równoważności.
-
○
Relację $\rho \subseteq X \times X$, która jest spójną, symetryczną i przechodnią, nazywamy relacją równoważności.
Pytanie 64: Wskaż zdania będące definicjami izomorfizmu grafów:
-
○
Funkcja $f: V_1 \rightarrow V_2$ jest izomorfizmem grafów, jeżeli $f$ jest funkcją wzajemnie jednoznaczną oraz dla każdej pary wierzchołków $x, y \in V_1$, $\{x, y\} \in E_2$ wtedy i tylko wtedy, gdy $\{f(x), f(y)\} \in E_2$.
-
○
Funkcja $f: V_1 \rightarrow V_2$ jest izomorfizmem grafów, jeżeli $f$ jest funkcją wzajemnie jednoznaczną oraz dla każdej pary wierzchołków $x, y \in V_1$, $\{x, y\} \in E_1$ wtedy i tylko wtedy, gdy $\{f(x), f(y)\} \in E_1$.
-
✓
Funkcja $f: V_1 \rightarrow V_2$ jest izomorfizmem grafów, jeżeli $f$ jest funkcją wzajemnie jednoznaczną oraz dla każdej pary wierzchołków $x, y \in V_1$, $\{x, y\} \in E_1$ wtedy i tylko wtedy, gdy $\{f(x), f(y)\} \in E_2$.
-
○
Funkcja $f: V_1 \rightarrow V_2$ jest izomorfizmem grafów, jeżeli $f$ jest funkcją wzajemnie jednoznaczną oraz dla każdej pary wierzchołków $x, y \in V_1$, $\{x, y\} \in E_1$ wtedy i tylko wtedy, gdy $\{f(x), f(y)\} \notin E_2$.
-
○
Funkcja $f: V_1 \rightarrow V_2$ jest izomorfizmem grafów, jeżeli $f$ jest funkcją wzajemnie jednoznaczną oraz dla każdej pary wierzchołków $x, y \in V_1$, $\{f(x), f(y)\} \in E_1$ wtedy i tylko wtedy, gdy $\{f(x), f(y)\} \in E_2$.
Pytanie 65: Niech $G=(V_1, V_2, E)$ będzie grafem dwudzielnym. Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.
-
○
Skojarzeniem z $V_1$ do $V_2$ w $G$ jest zbiór złożony z $|V_2|$ krawędzi, które nie mają wspólnych wierzchołków końcowych.
-
✓
Skojarzeniem z $V_1$ do $V_2$ w $G$ jest zbiór złożony z $|V_1|$ krawędzi, które nie mają wspólnych wierzchołków końcowych.
-
○
Skojarzeniem z $V_1$ do $V_2$ w $G$ jest zbiór z tych krawędzi, które oba wierzchołki końcowe mają w zbiorze $V_1$.
-
○
Skojarzeniem z $V_1$ do $V_2$ w $G$ jest zbiór z tych krawędzi, które oba wierzchołki końcowe mają w zbiorze $V_2$.
-
○
Skojarzeniem z $V_1$ do $V_2$ w $G$ jest podzbiór zbioru $V_1$ zawierający wszystkie wierzchołki o stopniu parzystym.
Pytanie 66: Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:
-
✓
Jeżeli $a,b,c \in \mathbb{P}$, to równanie diofantyczne $ax+by=c$ ma rozwiązania całkowite $x=x_0, y=y_0$ wtedy i tylko wtedy, gdy $\gcd(a,b)$ dzieli $c$.
-
○
Jeżeli $a,b,c \in \mathbb{P}$, to równanie diofantyczne $ax+by=c$ ma rozwiązania całkowite $x=x_0, y=y_0$ wtedy i tylko wtedy, gdy $c$ dzieli $\gcd(a,b)$.
-
○
Jeżeli $a,b,c \in \mathbb{P}$, to równanie diofantyczne $ax+by=c$ ma rozwiązania całkowite $x=x_0, y=y_0$ wtedy i tylko wtedy, gdy $a$ i $b$ są liczbami pierwszymi.
-
○
Jeżeli $a,b,c \in \mathbb{P}$, to równanie diofantyczne $ax+by=c$ ma rozwiązania całkowite $x=x_0, y=y_0$ wtedy i tylko wtedy, gdy $c$ dzieli $\operatorname{lcm}(a,b)$.
-
○
Jeżeli $a,b,c \in \mathbb{P}$, to równanie diofantyczne $ax+by=c$ ma rozwiązania całkowite $x=x_0, y=y_0$ wtedy i tylko wtedy, gdy $\operatorname{lcm}(a,b)$ dzieli $c$.
Pytanie 67: Niech $H$ będzie grafem sprzężonym pewnego grafu $G$. Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:
-
○
W grafie $G$ istnieje ścieżka Hamiltona wtedy i tylko wtedy, gdy w grafie $H$ istnieje droga Eulera.
-
✓
W grafie $G$ istnieje droga Eulera wtedy i tylko wtedy, gdy w grafie $H$ istnieje ścieżka Hamiltona.
-
○
W grafie $G$ istnieje droga Eulera wtedy i tylko wtedy, gdy w grafie $H$ istnieje obwód Eulera.
-
○
W grafie $G$ istnieje ścieżka Hamiltona wtedy i tylko wtedy, gdy w grafie $H$ istnieje cykl Hamiltona.
-
○
W grafie $G$ istnieje cykl Hamiltona wtedy i tylko wtedy, gdy w grafie $H$ istnieje ścieżka Hamiltona.
Pytanie 68: Niech $G=(V_1,V_2,E)$ będzie grafem dwudzielnym. Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:
-
✓
Minimalna liczba wierzchołków grafu $G$, wśród których jest co najmniej jeden koniec każdej jego krawędzi równa jest maksymalnej liczbie krawędzi w skojarzeniu.
-
○
Minimalna liczba wierzchołków grafu $G$, wśród których jest co najmniej jeden koniec każdej jego krawędzi równa jest minimalnej liczbie krawędzi w skojarzeniu.
-
○
Minimalna liczba wierzchołków grafu $G$, wśród których jest co najmniej jeden koniec każdej jego krawędzi równa jest liczbie krawędzi grafu $G$.
-
○
Maksymalna liczba wierzchołków grafu $G$, wśród których jest co najmniej jeden koniec każdej jego krawędzi równa jest minimalnej liczbie wierzchołków w skojarzeniu.
-
○
Maksymalna liczba wierzchołków grafu $G$, wśród których jest co najmniej jeden koniec każdej jego krawędzi równa jest maksymalnej liczbie wierzchołków w skojarzeniu.
Pytanie 69: Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:
-
○
$1+2^2x+3^2x^2+4^2x^3+...$ jest wykładniczą funkcją tworzącą sekwencji liczb $1^2, 2^2, 3^2, 4^2, ...$
-
✓
$1+2^2x+3^2x^2+4^2x^3+...$jest funkcją tworzącą sekwencji liczb $1^2, 2^2, 3^2, 4^2, ...$
-
✓
$x+2^2x^2+3^2x^2+4^2x^4+...$ jest funkcją tworzącą sekwencji liczb $0^2, 1^2, 2^2, 3^2, 4^2, ...$
-
○
$x+2^2x^2+3^2x^2+4^2x^4+...$ jest wykładniczą funkcją tworzącą sekwencji liczb $0^2, 1^2, 2^2, 3^2, 4^2, ...$
-
○
$x+2^2x^2+3^2x^2+4^2x^4+...$ jest funkcją tworzącą sekwencji liczb $1^2, 2^2, 3^2, 4^2, ...$
Pytanie 70: Funkcję $e^x$ można przedstawić w postaci: $e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \dots = \sum_{i=0}^{\infty} \frac{x^i}{i!}$. Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:
-
○
$e^x$ jest wykładniczą funkcją tworzącą sekwencji liczb $1, 1, \frac{1}{2!}, \frac{1}{3!}, \frac{1}{4!}, \dots$.
-
○
$e^x$ jest funkcją tworzącą sekwencji liczb $1, 1, 1, 1, 1, 1, \dots$.
-
✓
$e^x$ jest funkcją tworzącą sekwencji liczb $1, 1, \frac{1}{2!}, \frac{1}{3!}, \frac{1}{4!}, \dots$.
-
○
$e^x$ jest funkcją tworzącą sekwencji liczb $1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, \dots$.
-
✓
$e^x$ jest wykładniczą funkcją tworzącą sekwencji liczb $1, 1, 1, 1, 1, 1, \dots$.
Pytanie 71: Zaznacz wszystkie zdania prawdziwe:
-
○
Zdaniem odwrotnym do zdania $p \rightarrow q$ jest zdanie $p \rightarrow \neg q$.
-
✓
Zdaniem przeciwstawnym do zdania $p \rightarrow q$ jest zdanie $\neg q \rightarrow \neg p$.
-
○
Zdanie złożone jest tautologią, jeżeli jest ono fałszywe niezależnie od wartości logicznych jego zdań składowych.
-
○
Zdaniem odwrotnym do zdania $p \rightarrow q$ jest zdanie $\neg p \rightarrow \neg q$.
-
○
Zdaniem przeciwstawnym do zdania $p \rightarrow q$ jest zdanie $\neg q \rightarrow p$.
Pytanie 72: Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:
-
○
$5$ i $10$ są liczbami względnie pierwszymi.
-
✓
$2$ i $3$ są liczbami względnie pierwszymi.
-
○
$1$ jest najmniejszą liczbą pierwszą.
-
✓
$2$ jest najmniejszą liczbą pierwszą.
-
○
$0$ jest najmniejszą liczbą pierwszą.
Pytanie 73: Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:
-
○
Rodzina zbiorów $\mathcal{A} = (A_1, A_2, \dots, A_n)$ ma transwersalę wtedy i tylko wtedy, gdy $|\bigcup_{i \in I} A_i| \geq |I|$ dla wszystkich $I \subseteq \{A_1, A_2, \dots, A_n\}$.
-
○
Jeżeli $\mathcal{A} = (A_1, A_2, \dots, A_n)$ jest rodziną zbiorów, a $P \subseteq A_1 \cup A_2 \cup \dots \cup A_n$, to $\mathcal{A}$ ma transwersalę, która zawiera zbiór $P$ wtedy i tylko wtedy, gdy $\mathcal{A}$ ma transwersalę oraz $|P \setminus (\bigcup_{i \in I} A_i)| \geq n - |I|$ dla każdego $I \subseteq \{1, 2, \dots, n\}$.
-
✓
Rodzina zbiorów $\mathcal{A} = (A_1, A_2, \dots, A_n)$ ma transwersalę wtedy i tylko wtedy, gdy $|\bigcup_{i \in I} A_i| \geq |I|$ dla wszystkich $I \subseteq \{1, 2, \dots, n\}$.
-
✓
Jeżeli $\mathcal{A} = (A_1, A_2, \dots, A_n)$ jest rodziną zbiorów, a $P \subseteq A_1 \cup A_2 \cup \dots \cup A_n$, to $\mathcal{A}$ ma transwersalę, która zawiera zbiór $P$ wtedy i tylko wtedy, gdy $\mathcal{A}$ ma transwersalę oraz $|P \setminus (\bigcup_{i \in I} A_i)| \leq n - |I|$ dla każdego $I \subseteq \{1, 2, \dots, n\}$.
-
○
Transwersalą rodziny zbiorów $\mathcal{A} = (A_1, A_2, \dots, A_n)$ jest zbiór $Y = (A_1 \cup A_2 \cup \dots \cup A_n) \setminus (A_1 \cap A_2 \cap \dots \cap A_n)$, którego elementy mogą zostać zapisane w pewnym porządku.
Pytanie 74: Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:
-
○
Każdy graf $(\infty, k)$-etykietowalny jest również $(n-k,k)$-etykietowalny, gdzie $n$ jest liczbą wierzchołków w grafie.
-
✓
Jeżeli graf $G$ jest etykietowalny za pomocą etykiet o długości $k>2$ zbudowanych nad alfabetem o dowolnej liczności, to jest on również etykietowalny za pomocą etykiet o długości $l=2, \dots, k-1$ zbudowanych nad alfabetem o dowolnej liczności.
-
✓
Każdy graf $(\infty, k)$-etykietowalny jest również $(nk,k)$-etykietowalny, gdzie $n$ jest liczbą wierzchołków w grafie.
-
○
Grafu niespójnego nie można zaetykietować.
-
○
Każdy graf $(\infty, k)$-etykietowalny jest również $(k,nk)$-etykietowalny, gdzie $n$ jest liczbą wierzchołków w grafie.
Pytanie 75: Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:
-
○
Liczby całkowite $a$ i $b$ są względnie pierwsze, jeżeli istnieją liczby całkowite $x$ i $y$, takie że $ax + by = 2$.
-
✓
Liczby całkowite $a$ i $b$ są względnie pierwsze, jeżeli $\gcd(a, b) = 1$.
-
○
Liczby całkowite $a$ i $b$ są względnie pierwsze, jeżeli $\gcd(a, b) = 0$.
-
✓
Liczby całkowite $a$ i $b$ są względnie pierwsze, jeżeli istnieją liczby całkowite $x$ i $y$, takie że $ax + by = 1$.
-
○
Liczby całkowite $a$ i $b$ są względnie pierwsze, jeżeli istnieją liczby całkowite $x$ i $y$, takie że $ax + by = \sqrt{2}$.d
Pytanie 76: Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:
-
○
Funkcja $f(x) = a_0 x_0 + a_1 x_1 + a_2 x_2^2 + a_3 x_3^3 + \dots = \sum_{i=0}^{\infty} a_i x_i^i$ jest wykładniczą funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1 x_1, a_2 x_2, a_3 x_3, \dots$.
-
✓
Funkcja $f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots = \sum_{i=0}^{\infty} a_i x^i$ jest funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1, a_2, a_3, \dots$.
-
○
Funkcja $f(x) = \frac{1}{a_0} + \frac{x}{a_1} + \frac{2! x^2}{a_2} + \frac{3! x^3}{a_3} + \dots = \sum_{i=0}^{\infty} \frac{i! x^i}{a_i}$ jest wykładniczą funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1, a_2, a_3, \dots$.
-
○
Funkcja $f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots = \sum_{i=0}^{\infty} a_i x^i$ jest wykładniczą funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1, a_2, a_3, \dots$.
-
✓
Funkcja $f(x) = a_0 + a_1 x + \frac{a_2 x^2}{2!} + \frac{a_3 x^3}{3!} + \dots = \sum_{i=0}^{\infty} \frac{a_i x^i}{i!}$ jest wykładniczą funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1, a_2, a_3, \dots$.
Pytanie 77: Wybierz wszystkie poprawne:
-
○
Relację, która jest jednocześnie relacją przechodnią, symetryczną i spójną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.
-
○
Relację, która jest jednocześnie relacją przechodnią, symetryczną i przeciwzwrotną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.
-
○
Relację, która jest jednocześnie relacją zwrotną, antysymetryczną i spójną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.
-
✓
Relację, która jest jednocześnie relacją przechodnią, antysymetryczną, zwrotną i spójną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.
-
○
Relację, która jest jednocześnie relacją zwrotną, przechodnią i antysymetryczną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.
Pytanie 78: Wybierz wszystkie poprawne:
-
○
Graf $G=(V,E)$ jest grafem dwudzielnym, jeżeli występuje w nim parzysta liczba rozłącznych ścieżek Hamiltona.
-
○
Graf $G=(V,E)$ jest grafem dwudzielnym, jeżeli $V=V_1 \cup V_2$, $V_1 \subseteq V_2$ oraz dla każdej krawędzi $\{x,y\} \in E$ zachodzi $x \in V_1 \land y \in V_2$.
-
✓
Graf $G=(V,E)$ jest grafem dwudzielnym, jeżeli jego zbiór wierzchołków można podzielić na dwa rozłączne podzbiory w taki sposób, że żadna krawędź występująca w tym grafie nie jest incydentna z dwoma wierzchołkami należącymi do tego samego podzbioru.
-
○
Graf $G=(V,E)$ jest grafem dwudzielnym, jeżeli występuje w nim parzysta liczba rozłącznych cykli.
-
✓
Graf $G=(V,E)$ jest grafem dwudzielnym, jeżeli $V=V_1 \cup V_2$, $V_1 \cap V_2 = \emptyset$ oraz dla każdej krawędzi $\{x,y\} \in E$ zachodzi $x \in V_1 \land y \in V_2$.
Pytanie 79: Wybierz wszystkie poprawne:
-
○
Skojarzenie w grafie $G=(V,E)$ jest to największy podgraf pełny tego grafu.
-
○
Skojarzenie w grafie $G=(V,E)$ jest to jego drzewo rozpinające.
-
○
Skojarzenie w grafie $G=(V,E)$ jest to ścieżka przechodząca przez wszystkie jego wierzchołki.
-
○
Skojarzenie w grafie $G=(V,E)$ jest to droga przechodząca przez wszystkie jego krawędzie.
-
✓
Skojarzenie w grafie $G=(V,E)$ jest to zbiór krawędzi, z których żadne dwie nie mają wspólnego wierzchołka końcowego.
Pytanie 80: Wśród poniższych zdań wskaż wszystkie zdania będące definicjami drzewa.
-
○
Graf $G=(V,E)$ jest drzewem, jeżeli posiada korzeń.
-
○
Graf $G=(V,E)$ jest drzewem, jeżeli nie zawiera cykli i $|V|=|E|-1$.
-
✓
Graf $G=(V,E)$ jest drzewem, jeżeli nie zawiera cykli i jeżeli $x,y \in V$ oraz $\{x,y\} \notin E$, to dodanie do $G$ krawędzi $\{x,y\}$ spowoduje powstanie grafu $G'$ zawierającego dokładnie jeden cykl.
-
✓
Graf $G=(V,E)$ jest drzewem, jeżeli nie zawiera cykli i $|V|=|E|+1$.
-
○
Graf $G=(V,E)$ jest drzewem, jeżeli jest spójny i $|V|=|E|-1$.
Pytanie 81: Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.
-
○
1-graf $H=(A,U)$ jest grafem sprzężonym wtedy i tylko wtedy, gdy dla każdej pary wierzchołków $x,y \in A$ spełniony jest następujący warunek: $N^+(x) \cap N^+(y) \neq \emptyset \Rightarrow N^-(x) \cap N^-(y) \neq \emptyset$.
-
✓
1-graf $H=(A,U)$ jest grafem sprzężonym wtedy i tylko wtedy, gdy dla każdej pary wierzchołków $x,y \in A$ spełniony jest następujący warunek: $N^+(x) \cap N^+(y) \neq \emptyset \Rightarrow N^+(x) = N^+(y)$.
-
○
1-graf $H=(A,U)$ jest grafem sprzężonym wtedy i tylko wtedy, gdy dla każdej pary wierzchołków $x,y \in A$ spełniony jest następujący warunek: $N^+(x) \cap N^+(y) \neq \emptyset \Rightarrow (N^+(x) = N^+(y) \land N^-(x) \cap N^-(y) = \emptyset)$.
-
○
1-graf $H=(A,U)$ jest grafem sprzężonym wtedy i tylko wtedy, gdy dla każdej pary wierzchołków $x,y \in A$ spełniony jest następujący warunek: $N^-(x) \cap N^-(y) \neq \emptyset \Rightarrow N^+(x) \cap N^+(y) \neq \emptyset$.
-
○
1-graf $H=(A,U)$ jest grafem sprzężonym wtedy i tylko wtedy, gdy dla każdej pary wierzchołków $x,y \in A$ spełniony jest następujący warunek: $N^+(x) \cap N^+(y) \neq \emptyset \Rightarrow N^-(x) \cap N^-(y) = \emptyset$.
Pytanie 82: Niech $G=(V,E)$ będzie grafem nieskierowanym bez wierzchołków izolowanych. Wśród poniższych zdań wskaż zdania prawdziwe.
-
○
$G$ zawiera cykl Hamiltona wtedy i tylko wtedy, gdy $G$ jest spójny i każdy wierzchołek $G$ ma nieparzysty stopień.
-
○
$G$ zawiera drogę Eulera wtedy i tylko wtedy, gdy $G$ jest spójny i zawiera dokładnie dwa wierzchołki o stopniu nieparzystym.
-
✓
$G$ zawiera obwód Eulera wtedy i tylko wtedy, gdy $G$ jest spójny i każdy wierzchołek $G$ ma parzysty stopień.
-
○
$G$ zawiera drogę Eulera wtedy i tylko wtedy, gdy $G$ jest spójny i zawiera dokładnie dwa wierzchołki o stopniu parzystym.
-
○
$G$ zawiera cykl Hamiltona wtedy i tylko wtedy, gdy $G$ jest spójny i każdy wierzchołek $G$ ma parzysty stopień.
Pytanie 83: Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.
-
✓
$1 + 2x + 3x^2 + 4x^3 + 5x^4 + \dots$ jest funkcją tworzącą sekwencji liczb $1, 2, 3, 4, 5, \dots$.
-
○
$x + x^2 + x^3 + x^4 + x^5 + \dots$ jest funkcją tworzącą sekwencji liczb $0, 1, 2, 3, 4, \dots$.
-
○
$1 + 2x + 3x^2 + 4x^3 + 5x^4 + \dots$ jest funkcją tworzącą sekwencji liczb $0, 1, 2, 3, 4, \dots$.
-
○
$1 + 2x + 3x^2 + 4x^3 + 5x^4 + \dots$ jest wykładniczą funkcją tworzącą sekwencji liczb $1, 2, 3, 4, 5, \dots$.
-
○
$x + x^2 + x^3 + x^4 + x^5 + \dots$ jest funkcją tworzącą sekwencji liczb $1, 2, 3, 4, 5, \dots$.
Pytanie 84: Wybierz wszystkie poprawne:
-
✓
Między dwoma dowolnymi wierzchołkami $x$ i $y$ należącymi do sieci minimalna przepustowość przekroju, który rozdziela $x$ od $y$, równa jest maksymalnej wartości przepływu z $x$ do $y$.
-
○
Między dwoma dowolnymi wierzchołkami $x$ i $y$ należącymi do sieci maksymalna przepustowość przekroju, który rozdziela $x$ od $y$, równa jest minimalnej wartości przepływu z $x$ do $y$.
-
○
Między dwoma dowolnymi wierzchołkami $x$ i $y$ należącymi do sieci minimalna przepustowość przekroju, który rozdziela $x$ od $y$, równa jest minimalnej wartości przepływu z $x$ do $y$.
-
○
Między dwoma dowolnymi wierzchołkami $x$ i $y$ należącymi do sieci maksymalna przepustowość przekroju, który rozdziela $x$ od $y$, równa jest maksymalnej wartości przepływu z $x$ do $y$.
-
○
Między dwoma dowolnymi wierzchołkami $x$ i $y$ należącymi do sieci minimalna przepustowość przekroju, który rozdziela $x$ od $y$, równa jest $out(x)$.
Pytanie 85: Wybierz wszystkie poprawne:
-
○
Jeżeli liczby $b_1, b_2, \dots, b_n$ są wynikiem pewnego turnieju, to ich suma może być większa niż $\binom{n}{2}$.
-
○
Jeżeli liczby $b_1, b_2, \dots, b_n$ są wynikiem pewnego turnieju, to ich suma może być mniejsza niż $\binom{n}{2}$.
-
○
Jeżeli liczby $b_1, b_2, \dots, b_n$ są wynikiem pewnego turnieju, to dla pewnego $r$, takiego że $2 \leq r \leq n$, można wybrać $r$ spośród tych liczb w taki sposób, że suma wybranych liczb jest mniejsza niż $\binom{n}{2}$.
-
✓
Jeżeli liczby $b_1, b_2, \dots, b_n$ są wynikiem pewnego turnieju, to dla żadnego $r$, takiego że $2 \leq r \leq n$, nie można wybrać $r$ spośród tych liczb w taki sposób, że suma wybranych liczb jest mniejsza niż $\binom{r}{2}$.
-
✓
Jeżeli liczby $b_1, b_2, \dots, b_n$ są wynikiem pewnego turnieju, to ich suma nie może być ani mniejsza, ani większa niż $\binom{n}{2}$.
Pytanie 86: Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.
-
○
W grafie de Bruijna $B(d,k)$ może wystąpić co najwyżej $k$ etykiet o długości $d$.
-
○
W grafie de Bruijna $B(d,k)$ może wystąpić co najwyżej $d$ etykiet o długości $k$.
-
○
Graf de Bruijna $B(d,k)$ zawiera $k^d$ łuków.
-
○
Graf de Bruijna $B(d,k)$ zawiera $k^d$ wierzchołków.
-
✓
Graf de Bruijna $B(d,k)$ zawiera $d^k$ wierzchołków.
Pytanie 87: Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.
-
○
Funkcja $f(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots = \sum_{i=0}^{\infty} a_i x^i$ jest wykładniczą funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1, a_2, a_3, \dots$.
-
○
Funkcja $f(x) = a_0^0 + a_1 x^1 + a_2 x^2 + a_3 x^3 + \dots = \sum_{i=0}^{\infty} a_i x^i$ jest wykładniczą funkcją tworzącą sekwencji liczb rzeczywistych $a_0 x_0, a_1 x_1, a_2 x_2, a_3 x_3, \dots$.
-
○
Funkcja $f(x) = \frac{1}{a_0} + \frac{x}{a_1} + \frac{2! x^2}{a_2} + \frac{3! x^3}{a_3} + \dots = \sum_{i=0}^{\infty} \frac{i! x^i}{a_i}$ jest wykładniczą funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1, a_2, a_3, \dots$.
-
✓
Funkcja $f(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots = \sum_{i=0}^{\infty} a_i x^i$ jest funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1, a_2, a_3, \dots$.
-
✓
Funkcja $f(x) = a_0 + a_1x + \frac{a_2 x^2}{2!} + \frac{a_3 x^3}{3!} + \dots = \sum_{i=0}^{\infty} \frac{a_i x^i}{i!}$ jest wykładniczą funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1, a_2, a_3, \dots$.
Pytanie 88: Wśród poniższych zdań wskaż definicje odpowiednich relacji.
-
○
Relację $\rho \subset X \times X$ nazywamy spójną wtedy i tylko wtedy, gdy warunki $\langle x, y \rangle \in \rho$ i $\langle y, z \rangle \in \rho$ implikują warunek $\langle x, z \rangle \in \rho$ dla każdych trzech elementów $x, y, z$ zbioru $X$.
-
✓
Relację $\rho \subset X \times X$ nazywamy symetryczną wtedy i tylko wtedy, gdy z warunku $\langle x, y \rangle \in \rho$ wynika warunek $\langle y, x \rangle \in \rho$ dla każdego $x, y \in X$.
-
○
Relację $\rho \subset X \times X$ nazywamy zwrotną wtedy i tylko wtedy, gdy dla każdego $x \in X$ spełniony jest warunek $\langle x, x \rangle \notin \rho$.
-
✓
Relację $\rho \subset X \times X$ nazywamy antysymetryczną wtedy i tylko wtedy, gdy warunki $\langle x, y \rangle \in \rho$ i $\langle y, x \rangle \in \rho$ pociągają za sobą warunek $x = y$ dla każdej pary $x, y$ elementów zbioru $X$.
-
○
Relację $\rho \subset X \times X$ nazywamy przeciwzwrotną wtedy i tylko wtedy, gdy dla każdego $x \in X$ spełniony jest warunek $\langle x, x \rangle \in \rho$.
Pytanie 89: Wśród poniższych zdań wskaż definicje odpowiednich funkcji.
-
○
Funkcję różnowartościową $f: X \to Y$, która przekształca zbiór $X$ w zbiór $Y$ nazywamy przekształceniem wzajemnie jednoznacznym zbioru $Y$ na zbiór $X$.
-
✓
Funkcję różnowartościową $f: X \to Y$, która przekształca zbiór $X$ w zbiór $Y$ nazywamy przekształceniem wzajemnie jednoznacznym zbioru $X$ na zbiór $Y$.
-
○
Funkcją odwrotną do funkcji $f: X \to Y$ jest taka funkcja $f^{-1}$, która każdemu elementowi $y \in Y$ przyporządkowuje element $x \in X$ taki, że $f(x) = x$.
-
✓
Funkcją odwrotną do funkcji $f: X \to Y$ jest taka funkcja $f^{-1}$, która każdemu elementowi $y \in Y$ przyporządkowuje element $x \in X$ taki, że $f(x) = y$.
-
○
Funkcją odwrotną do funkcji $f: X \to Y$ jest taka funkcja $f^{-1}$, która każdemu elementowi $y \in Y$ przyporządkowuje element $x \in X$ taki, że $f(x) = y^{-1}$.
Pytanie 90: Niech $a, b, c \in \mathbb{Z}$. Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.
-
✓
$[(a|b) \land (a|c)] \Rightarrow a|(bx + cy)$ dla wszystkich $x, y \in \mathbb{Z}$.
-
○
$a|b \Rightarrow a|x^b$ dla każdego $x \in \mathbb{Z}$.
-
○
$[(a|b) \land (a|c)] \Rightarrow (bx + cy)|a$ dla wszystkich $x, y \in \mathbb{Z}$.
-
○
$[(a|b) \land (b|c)] \Rightarrow c|a$.
-
✓
Jeżeli $x = y + z$ dla pewnych $x, y, z \in \mathbb{Z}$ oraz $a$ dzieli dwie z trzech liczb $x, y, z$, to $a$ dzieli również trzecią z tych liczb.
Pytanie 91: Wybierz wszystkie poprawne:
-
✓
Turniej z udziałem $n$ graczy oznaczonych kolejnymi liczbami całkowitymi dodatnimi $1, 2, \dots, n$ jest zbiorem $\binom{n}{2}$ uporządkowanych par zawodników, przy czym dla $1 \leq i < j \leq n$ w turnieju występuje albo para $(i, j)$ albo para $(j, i)$.
-
○
Turniej z udziałem $n$ graczy oznaczonych kolejnymi liczbami całkowitymi dodatnimi $1, 2, \dots, n$ jest posortowaną listą zawodników.
-
○
Turniej z udziałem $n$ graczy oznaczonych kolejnymi liczbami całkowitymi dodatnimi $1, 2, \dots, n$ jest zbiorem $\binom{n}{2}$ nieuporządkowanych par zawodników.
-
○
Turniej z udziałem $n$ graczy oznaczonych kolejnymi liczbami całkowitymi dodatnimi $1, 2, \dots, n$ jest zbiorem $\binom{n}{3}$ nieuporządkowanych trójek zawodników.
-
○
Turniej z udziałem $n$ graczy oznaczonych kolejnymi liczbami całkowitymi dodatnimi $1, 2, \dots, n$ jest zbiorem wszystkich zawodników.
Pytanie 92: Wśród poniższych zdań wskaż reguły podstawiania.
-
○
Jeżeli zdanie złożone $P$ jest zdaniem sprzecznym i wszystkie wystąpienia pewnej zmiennej $p$ (zdania składowego) występującej w zdaniu $P$ zastąpimy zdaniem $R$, to otrzymane zdanie złożone $P_1$ będzie tautologią.
-
✓
Jeżeli zdanie złożone $P$ zawiera zdanie $Q$, $R$ jest zdaniem takim, że $Q \Leftrightarrow R$ i jeśli w $P$ zastąpimy jedno lub więcej wystąpień $Q$ przez $R$, to otrzymamy zdanie złożone $P_1$ takie, że $P \Leftrightarrow P_1$.
-
○
Jeżeli zdanie złożone $P$ zawiera zdanie $Q$, $R$ jest zdaniem takim, że $R \Rightarrow Q$ i w $P$ zastąpimy dokładnie jedno wystąpienie $Q$ przez $R$, to otrzymamy zdanie złożone $P_1$ takie, że $P \Leftrightarrow P_1$.
-
○
Jeżeli zdanie złożone $P$ zawiera zdanie $Q$, $R$ jest zdaniem takim, że $Q \Rightarrow R$ i w $P$ zastąpimy dokładnie jedno wystąpienie $Q$ przez $R$, to otrzymamy zdanie złożone $P_1$ takie, że $P \Leftrightarrow P_1$.
-
✓
Jeżeli zdanie złożone $P$ jest tautologią i wszystkie wystąpienia pewnej zmiennej $p$ (zdania składowego) występującej w zdaniu $P$ zastąpimy zdaniem $R$, to otrzymane zdanie złożone $P_1$ będzie również tautologią.
Pytanie 93: Wśród poniższych zdań wskaż wszystkie zdania będące definicjami odpowiednich zbiorów.
-
✓
Dla danej funkcji $g(n)$ oznaczamy przez $O(g(n))$ następujący zbiór funkcji: $O(g(n)) = \{ f(n) :$ istnieją dodatnie stałe $c$ i $n_0$ takie, że $0 \leq f(n) \leq c g(n)$ dla wszystkich $n \geq n_0 \}$.
-
○
Dla danej funkcji $g(n)$ oznaczamy przez $O(g(n))$ następujący zbiór funkcji: $O(g(n)) = \{ f(n) :$ istnieją dodatnie stałe $c$ i $n_0$ takie, że $0 \leq f(n) \leq c g(n)$ dla wszystkich $n \leq n_0 \}$.
-
✓
Dla danej funkcji $g(n)$ oznaczamy przez $\Omega(g(n))$ następujący zbiór funkcji: $\Omega(g(n)) = \{ f(n) :$ istnieją dodatnie stałe $c$ i $n_0$ takie, że $0 \leq c g(n) \leq f(n)$ dla wszystkich $n \geq n_0 \}$.
-
○
Dla danej funkcji $g(n)$ oznaczamy przez $\Omega(g(n))$ następujący zbiór funkcji: $\Omega(g(n)) = \{ f(n) :$ istnieją dodatnie stałe $c$ i $n_0$ takie, że $0 \leq f(n) \leq c g(n)$ dla wszystkich $n \geq n_0 \}$.
-
○
Dla danej funkcji $g(n)$ oznaczamy przez $\Omega(g(n))$ następujący zbiór funkcji: $\Omega(g(n)) = \{ f(n) :$ istnieją dodatnie stałe $c$ i $n_0$ takie, że $0 \leq c g(n) \leq f(n)$ dla wszystkich $n \leq n_0 \}$.
Pytanie 94: Wśród poniższych zdań wskaż zdania prawdziwe.
-
○
Dla każdego drzewa $G = (V, E)$ zachodzi $|V| = |E| - 1$.
-
✓
Graf nieskierowany $G = (V, E)$ jest spójny wtedy i tylko wtedy, gdy posiada drzewo rozpinające.
-
○
W drzewie $G = (V, E)$ między każdą parą wierzchołków $x, y \in V$ istnieją co najmniej dwie ścieżki.
-
✓
W drzewie $G = (V, E)$ między każdą parą wierzchołków $x, y \in V$ istnieje dokładnie jedna ścieżka.
-
○
Drzewo $G = (V, E)$ takie, że $|V| \geq 2$, ma co najmniej trzy wierzchołki o stopniu równym 1.
Pytanie 95: Niech dana będzie przestrzeń $U$ oraz pewien jej podzbiór $A$. Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.
-
✓
Zbiór potęgowy zbioru $A$ jest to zbiór wszystkich podzbiorów zbioru $A$.
-
○
Dopełnienie zbioru $A$ jest to zbiór $A \setminus U$.
-
○
Dopełnienie zbioru $A$ jest to zbiór $A \cup U$.
-
○
Dopełnienie zbioru $A$ jest to zbiór $A \cap U$.
-
○
Zbiór potęgowy zbioru $A$ jest to zbiór zawierający te elementy przestrzeni $U$, które nie należą do $A$.
Pytanie 96: Niech $p$ i $q$ będą zdaniami logicznymi prostymi, $T_0$ niech będzie dowolną tautologią, a $F_0$ dowolnym zdaniem sprzecznym. Wśród poniższych par zdań wskaż zdania logicznie równoważne.
-
✓
$p \rightarrow q, \neg p \lor q$
-
○
$p \land F_0, p$
-
○
$p \lor T_0, p$
-
✓
$p \land F_0, F_0$
-
○
$p \land T_0, \neg p$
Pytanie 97: Niech $A, B$ i $C$ będą podzbiorami pewnej przestrzeni $U$. Wśród poniższych zdań wskaż prawa algebry zbiorów.
-
○
$\overline{A \cap B} = \overline{A} \cap \overline{B}$
-
○
$(A \cap B) \cap C = A \cup (B \cap C)$
-
✓
$A \cup (A \cap B) = A$
-
○
$A \cap (A \cup B) = \overline{A}$
-
✓
$\overline{A \cup B} = \overline{A} \cap \overline{B}$
Pytanie 98: Zaznacz zdania prawdziwe:
-
○
Wszystkie $k$-elementowe kombinacje bez powtórzeń z $n$-elementowego zbioru, dla $k = 0, \ldots, n$, mogą być wygenerowane za pomocą generacji wszystkich liczb binarnych z zakresu od $1$ do $2^n$.
-
○
Każde rozmieszczenie $k$ identycznych elementów w $n$ rozróżnialnych pudełkach odpowiada $k$-elementowej kombinacji bez powtórzeń ze zbioru $n$-elementowego.
-
✓
Z każdej $k$-elementowej kombinacji bez powtórzeń ze zbioru $n$-elementowego można utworzyć $k!$ różnych $k$-wyrazowych wariacji bez powtórzeń ze zbioru $n$-elementowego.
-
○
Liczba wszystkich $k$-elementowych kombinacji bez powtórzeń ze zbioru $n$-elementowego wynosi $\binom{n}{k}$, gdzie $n \leq k < n$.
-
○
Każda $k$-elementowa kombinacja bez powtórzeń ze zbioru $n$-elementowego odpowiada pewnemu podziałowi tego zbioru na $k$ podzbiorów.
Pytanie 99: Obiekty $|A, C, D|$ i $|B, E, F|$ utworzono ze zbioru $\{A, B, C, D, E, F\}$. Kolejność tych obiektów oraz uporządkowanie ich elementów nie jest istotna. Obiekty te są przykładem:
-
○
podziału uporządkowanego zbioru $\{A, B, C, D, E, F\}$, ponieważ elementy w obiektach są ustawione alfabetycznie.
-
✓
podziału zbioru $\{A, B, C, D, E, F\}$ na dwa podzbiory.
-
○
dwóch 3-elementowych wariacji bez powtórzeń ze zbioru 6-elementowego.
-
○
dwóch 3-elementowych permutacji bez powtórzeń ze zbioru 6-elementowego.
-
○
dwóch 3-elementowych permutacji z powtórzeniami, w których poszczególne elementy występują tylko jeden raz.
Pytanie 100: Zaznacz zdania prawdziwe:
-
○
$k$-wyrazową permutacją z powtórzeniami ze zbioru $n$-elementowego nazywamy każdy $k$-wyrazowy ciąg mogących się powtarzać elementów tego zbioru.
-
○
Permutacja z powtórzeniami może być interpretowana jako dowolne rozmieszczenie $n$ rozróżnialnych obiektów w $k$ rozróżnialnych pudełkach.
-
○
$k$-wyrazowe permutacje z powtórzeniami są równoważne $k$-wyrazowym wariacjom z powtórzeniami
-
✓
Liczba $n$-wyrazowych permutacji z powtórzeniami jest nie większa niż liczba $n$-wyrazowych permutacji bez powtórzeń.
-
○
W $n$-elementowej permutacji z powtórzeniami ze zbioru $\{a_1, \ldots, a_n\}$, w której element $a_i$ powtarza się $n_i$ razy, dla $i = 1, \ldots, k$, zachodzi: $\sum_{i=1}^{k} n_i = n!$.
Pytanie 101: 3 identyczne elementy mogą być wrzucone w dowolny sposób do 6 rozróżnialnych pudełek na
-
○
$\binom{6}{3}$ sposobów.
-
○
$6^3$ sposobów.
-
○
$3^6$ sposobów.
-
✓
$\binom{6+3-1}{3}$ sposobów.
-
○
$\frac{6!}{3!}$ sposobów.
Pytanie 102: Zaznacz zdania prawdziwe:
-
○
Pierwsza zasada indukcji matematycznej dla pewnego $n_0 \in \mathbb{Z}^{+}$ ma postać: $[S(n_0) \land [\forall_{k \geq 1} [S(k) \implies S(k+1)]]] \implies \forall_{n \geq 1} S(n)$.
-
○
Pierwszą zasadę indukcji matematycznej stosuje się do dowodzenia twierdzeń, w których prawdziwość pewnego zdania wynika z prawdziwości jednego, dowolnego ze zdań poprzedzających.
-
✓
Pierwsza zasada indukcji matematycznej dla $n_0 = 1$ ma postać: $[(\forall_{k \geq 1} [S(k) \implies S(k + 1)]) \land S(1)] \implies \forall_{n \in \mathbb{Z}^{+}} S(n)$.
-
○
Zasada indukcji matematycznej może być wykorzystana do dowodzenia twierdzeń dotyczących dowolnych liczb dodatnich.
-
○
Jeśli pewne twierdzenie $\forall_{n \in \mathbb{Z}^{+}} S(n)$ nie jest prawdziwe dla pewnych początkowych wartości $n \geq 1$, to może ono być udowodnione z wykorzystaniem drugiej zasady indukcji matematycznej.
Pytanie 103: Pierwsza i druga zasada indukcji matematycznej:
-
✓
są równoważne.
-
○
nie są równoważne.
-
○
są równoważne jedynie dla twierdzeń dotyczących liczb naturalnych.
-
○
mogą być zastosowane do dowodzenia twierdzeń dotyczących liczb rzeczywistych dodatnich.
-
○
są technikami dowodzenia twierdzeń dotyczących wyłącznie zależności rekurencyjnych jednorodnych.
Pytanie 104: Zaznacz zdania prawdziwe:
-
○
Druga zasada indukcji matematycznej dla dowolnych $n_0, n_1 \in \mathbb{Z}^+$, $n_0 \leq n_1$, ma postać: $[[S(1) \land S(2) \land \ldots \land S(n_1)] \land [\forall_{k \geq n_0} [[S(1) \land S(2) \land \ldots \land S(k)] \Rightarrow S(k+1)]]] \Rightarrow \forall_{n \geq n_1} S(n)$
-
○
Druga zasada indukcji matematycznej jest wykorzystywana do dowodzenia twierdzeń postaci: $\forall_{n \in \mathbb{Z}^+} S(n)$, takich że zdanie $S(n)$ nie jest prawdziwe dla pewnych początkowych wartości $n \in \mathbb{Z}^+$.
-
✓
Druga zasada indukcji matematycznej dla $n_0 = 1$, $n_1 \geq 1$ ma postać: $\left[ \forall_{k \geq n_1} [[ S(1) \land S(2) \land \ldots \land S(k) ] \Rightarrow S(k+1)] \land [S(1) \land S(2) \land \ldots \land S(n_1)] \right] \Rightarrow \forall_{n \geq n_1} S(n)$
-
○
Jeśli w dowodzie kroku indukcyjnego wykorzystuje się założenie o prawdziwości tylko jednego ze zdań $S(x)$ poprzedzających zdanie $S(k+1)$, $x \leq k$, to w pierwszej zasadzie twierdzenia wystarczy pierwsza zasada indukcji matematycznej.
-
○
W pierwszej zasadzie indukcji matematycznej z prawdziwości warunku początkowego lub kroku indukcyjnego wynika prawdziwość hipotezy indukcyjnej.
Pytanie 105: Zaznacz zdania prawdziwe:
-
○
Rozwiązanie liniowej jednorodnej zależności rekurencyjnej rzędu pierwszego ze stałymi współczynnikami postaci $a_n = ca_0^n$, $c$ oznacza pewną stałą i $n \in \mathbb{N}$.
-
○
Rozwiązanie zależności liniowej jednorodnej rzędu drugiego ze stałymi współczynnikami o równaniu charakterystycznym o pierwiastku podwójnym ma postać $a_n = c_1 r^n + c_2 n r^n$, gdzie $c_1$ i $c_2$ są wyznaczane w oparciu o początkowe elementy ciągu.
-
✓
Pełna definicja ciągu opisanego zależnością rekurencyjną rzędu $k$-tego musi zawierać wartości $k$ kolejnych (np. początkowych) elementów tego ciągu.
-
○
Zależność rekurencyjna postaci $c_{n} a_{n} + c_{n-1} a_{n-1} + \ldots + c_k a_{k} = 0$, gdzie $c_{i}$ dla $i = n, \ldots, k$ są pewnymi stałymi rzeczywistymi, $c_{n} \neq 0$ i $c_{k} \neq 0$ nazywamy liniową jednorodną zależnością rekurencyjną rzędu k-tego ze stałymi współczynnikami.
-
○
Każdy pierwiastek pojedynczy $r$ równania charakterystycznego wprowadza do rozwiązania liniowej jednorodnej zależności rekurencyjnej ze stałymi współczynnikami rzędu $k \geq 2$ czynnik $r c^n$, gdzie $c$ jest pewną stałą, którą można wyznaczyć w oparciu o początkowe wyrazy ciągu.
Pytanie 106: Zależność rekurencyjna $(a_0 = 0, a_1 = 3, a_2 = 4, a_{n+1} = 3a_{n-2} = 3n \text{ dla } n \geq 2)$ jest zależnością rekurencyjną:
-
✓
liniową ze stałymi współczynnikami rzędu trzeciego niejednorodną.
-
○
liniową ze stałymi współczynnikami rzędu drugiego jednorodną.
-
○
liniową ze stałymi współczynnikami rzędu drugiego niejednorodną.
-
○
liniową ze stałymi współczynnikami rzędu pierwszego jednorodną.
-
○
liniową ze stałymi współczynnikami rzędu trzeciego jednorodną.
Pytanie 107: Zależność rekurencyjna $(a_0 = 1, a_1 = 2, na_{n} + 3a_{n-1} - a_{n-2} = 0 \text{ dla } n \geq 2)$ jest zależnością:
-
○
niejednorodną.
-
○
dla której równanie charakterystyczne jest równaniem kwadratowym.
-
✓
nieliniową.
-
✓
która nie może być rozwiązywana metodą równania charakterystycznego.
-
○
dla której równanie charakterystyczne jest równaniem stopnia trzeciego.
Pytanie 108: Zaznacz zdania prawdziwe:
-
✓
Liczby Stirlinga drugiego rodzaju opisujące liczbę sposobów podziału zbioru $n$-elementowego na $k$ niepustych rozłącznych podzbiorów są nie większe niż liczby Stirlinga pierwszego rodzaju opisujące liczbę sposobów rozmieszczenia $n$ elementów w $k$ niepustych cyklach.
-
○
Definicja rekurencyjna liczb Stirlinga drugiego rodzaju zawiera zależność postaci: $S(n, k) = S(n-1, k) + k \cdot S(n-1, k-1)$, a definicja rekurencyjna liczb Stirlinga pierwszego rodzaju: $s(n, k) = s(n-1, k) + (n-1) \cdot s(n-1, k-1)$ $(\text{gdzíe n} > 0, k > 0)$.
-
○
Liczby Eulera drugiego rzędu $\left\langle\left\langle {n \atop k} \right\rangle\right\rangle$ oznaczają liczbę permutacji z powtórzeniami multizbioru $\{1, 1, 2, 2, \ldots, k, k\}$ zawierających $n$ wzniesień.
-
○
Liczby harmoniczne pierwszego rzędu tworzą ciąg zbieżny do pewnej granicy, ponieważ zgodnie z definicją rekurencyjną każda kolejna liczba $H_{n+1}$ powstaje z poprzedniej liczby $H_n$ przez dodanie ułamka $\frac{1}{n+1}$.
-
○
W systemie liczbowym Fibonacciego, zbudowanym w oparciu o twierdzenie Zeckendorfa, do jednoznacznej reprezentacji liczb całkowitych dodatnich wykorzystuje się wszystkie liczby Fibonacciego $F_k$, dla $k \geq 0$.
Pytanie 109: Zaznacz zdania prawdziwe:
-
○
Liczby harmoniczne rzędu $r$, dla $r > 1$, tworzą ciąg rozbieżny.
-
○
W ciągu liczby Stirlinga drugiego rodzaju mogą pojawić się liczby niebędące liczbami całkowitymi.
-
✓
Każdej $n$-elementowej permutacji bez powtórzeń ze zbioru $n$-elementowego odpowiada pewien układ cykli i każdemu układowi cykli odpowiada pewna $n$-elementowa permutacja bez powtórzeń ze zbioru $n$-elementowego.
-
○
Liczby Fibonacciego są liczbami opisanymi zależnością rekurencyjną rzędu trzeciego, ponieważ w definicji występują trzy elementy ciągu.
-
○
Liczby Eulera związane są z liczbą cykli Eulera w grafie.
Pytanie 110: Poprawna zasada włączania i wyłączania dla 3 dowolnych zbiorów ma postać:
-
○
$|A_1 \cap A_2 \cap A_3| = |A_1| \cdot |A_2| \cdot |A_3|$
-
○
$|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cup A_2| - |A_1 \cup A_3| - |A_2 \cup A_3| + |A_1 \cup A_2 \cup A_3|$
-
○
$|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cup A_2 \cup A_3|$
-
✓
$|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3|$
-
○
$|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2 \cap A_3|$
Pytanie 111: Zaznacz zdania prawdziwe:
-
○
Zasada włączania i wyłączania mówi, że liczba elementów pewnego zbioru $S$, $|S| = N$, które nie spełniają żadnego z warunków $c_i$, $1 \leq i \leq t$, jest równa $N = N - N(c_1) - N(c_2) - ... - N(c_t)$, gdzie $N(c_i)$ oznacza liczbę elementów $S$ spełniających warunek $c_i$.
-
✓
Zasada włączania i wyłączania dla zbioru $S$ i warunków $c_i$, $1 \leq i \leq t$, spełnionych przez pewne elementy ze zbioru $S$ ma postać: $N(\overline{c_1, c_2, \dots, c_t}) = |S| - \sum_{1 \leq i \leq t} N(c_i) + \sum_{1 \leq i < j \leq t} N(c_i, c_j) - \sum_{1 \leq i < j < k \leq t} N(c_i, c_j, c_k) + ... + (-1)^t N(c_1, c_2, \dots, c_t)$.
-
○
Zasada włączania i wyłączania w postaci alternatywnej dotyczy pewnego zbioru $S$, dla którego zdefiniowane są warunki $c_i$, $1 \leq i \leq t$, które muszą być spełnione przez wszystkie elementy zbioru $S$.
-
○
Symbol $N(c_i c_j)$ występujący w zasadzie włączania i wyłączania oznacza liczbę elementów ze zbioru $S$ spełniających warunki $c_i \land c_j$ i równocześnie niespełniających pozostałych warunków $c_k$ ($1 \leq i, j \leq t$, $k \neq i$, $k \neq j$).
-
○
Dowód zasady włączania i wyłączania w postaci alternatywnej jest oparty o prawa teorii mnogości.
Pytanie 112: Zaznacz zdania prawdziwe:
-
○
Zasada szufladkowa Dirichleta mówi, że jeśli skończony zbiór $S$ jest podzielony na $k$ rozłącznych niepustych podzbiorów, to każdy z tych podzbiorów zawiera $|S|/k$ elementów lub więcej.
-
○
Dowód zasady szufladkowej Dirichleta wykorzystuje pojęcie uporządkowanego podziału zbioru.
-
○
„Klasyczna” zasada szufladkowa Dirichleta w żaden sposób nie wynika z uogólnionej zasady szufladkowej Dirichleta, ponieważ dotyczy zbiorów o odmiennych własnościach.
-
✓
Z zasady szufladkowej Dirichleta wynika, że jeśli skończony zbiór $S$ jest podzielony na $k$ rozłącznych niepustych podzbiorów, to średnia liczność tych zbiorów wynosi $|S|/k$.
-
○
Uogólniona zasada szufladkowa Dirichleta określa wartość średniej arytmetycznej liczb elementów zbiorów $A_1, \dots, A_k$ będących rozłącznymi podzbiorami pewnego skończonego zbioru $S$.
Pytanie 113: Średnia liczność zbiorów $A_1, A_2, A_3, A_4, A_5$ będących podzbiorami zbioru $10$ elementowego $S$, takimi, że każdy element $S$ należy do dokładnie $4$ podzbiorów:
-
✓
wynosi dokładnie $8$.
-
○
wynosi dokładnie $10$.
-
○
wynosi mniej niż $8$.
-
○
wynosi co najmniej $10$.
-
○
nie może być określona.
Pytanie 114: Zaznacz zdania prawdziwe:
-
○
Każda macierz o wymiarze $p \times q$ zbudowana z elementów ze zbioru $\{1, \dots, n\}$, gdzie $\min(p, q) < n$, w której w żadnym wierszu elementy się nie powtarzają jest prostokątem łacińskim.
-
✓
Rozszerzanie prostokąta łacińskiego $p \times n$ o jeden wiersz wymaga wyznaczenia dowolnego systemu różnych reprezentantów rodziny zbiorów $\{A_1, \dots, A_n\}$, gdzie zbiór $A_i$ zawiera elementy dotychczas niewystępujące w kolumnie $i$ ($1 \leq i \leq n$).
-
○
Rozszerzając prostokąt łaciński $p \times q$, do kwadratu $n \times n$ należy w nowej kolumnie umieścić wszystkie elementy $i = 1, \dots, n$, dla których liczba wystąpień spełnia warunek $L(i) > p + q - n$.
-
○
Pewne prostokąty łacińskie $p \times n$, w których liczba wystąpień niektórych elementów jest zbyt mała, nie mogą być rozszerzone do kwadratu łacińskiego $n \times n$.
-
○
Kwadratem grecko-łacińskim, czyli kwadratem Eulera, nazywamy złożenie dwóch dowolnych kwadratów łacińskich o takim samym rozmiarze.
Pytanie 115: Zaznacz zdania prawdziwe:
-
○
Wielomian szachowy $r_B(x) = 1 + r_1x + r_2x^2 + ... + r_kx^k + ... + r_nx^n$, to funkcja, której wartość oznacza liczbę możliwych rozmieszczeń $n$ wzajemnie nieatakujących się wież na szachownicy o wymiarze $x \times x$.
-
○
Jeśli szachownica $B$ składa się z dwóch niezależnych obszarów $C$ i $D$, to wówczas $r_B(x) = r_C(x) + r_D(x)$.
-
✓
Jeśli w wielomianie szachowym $r_B(x) = 1 + r_1x + r_2x^2 + ... + r_kx^k + ... + r_nx^n$ dla szachownicy $B$ o wymiarze $n \times n$ współczynnik $r_n = 0$, to na szachownicy $B$ nie można rozmieścić $n$ wzajemnie nieatakujących się wież.
-
○
Dekompzycja wielomianów szachowych jest możliwa wyłącznie wówczas, jeśli daną szachownicę można podzielić na dwa rozłączne obszary niemające wspólnych wierszy ani kolumn.
-
○
Szachownicę $B$ można zdekomponować, poprzez wybór pewnego pola dopuszczalnego $s$, na dwie szachownice $B^1$ i $B^2$, takie że w $B^1$ niedostępny jest wiersz, a w $B^2$ niedostępna jest kolumna zawierająca pole $s$.
Pytanie 116: Zaznacz funkcję tworzącą, która może być wielomianem szachowym pewnej szachownicy o wymiarze $5 \times 5$:
-
○
$r_B(x) = 2 + 7x + 16x^2 + 13x^3 + 3x^4 + 0x^5$.
-
✓
$r_B(x) = 1 + 7x + 16x^2 + 13x^3 + 3x^4 + 0x^5$.
-
○
$r_B(x) = 1 + 7x + 16x^2 + 13x^3 + 3x^4 + 1x^6$.
-
○
$r_B(x) = 1 + 26x + 16x^2 + 13x^3 + 3x^4 + 0x^5$.
-
○
$r_B(x) = 0 + 7x + 16x^2 + 13x^3 + 3x^4 + 0x^5$.