Quiz

Pytanie 1 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

Ś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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

Ś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 z 116

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 z 116

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 z 116

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 z 116

Zaznacz funkcję tworzącą, która $\textbf{może być}$ wielomianem szachowym $\textbf{dopełnienia}$ podanej szachownicy $B$:

$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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

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 z 116

Ś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 z 116

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 z 116

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 z 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$.

Losowa kolejność Reset Start

Korzystanie z serwisu wiąże się z akceptacją regulaminu