Quiz

Pytanie 1 z 60

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_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$, $\{f(x), f(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$, $\{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_2$.

Pytanie 2 z 60

Zaznacz zdanie prawdziwe.

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

Dowód warunku początkowego w pierwszej zasadzie indukcji matematycznej wymaga pokazania prawdziwości zdania $S(n)$ dla dowolnego elementu $n \geq n_0$.

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

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

Pytanie 3 z 60

Zaznacz zdania prawdziwe.

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.

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

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.

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.

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.

Pytanie 4 z 60

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 $\min{|X|, |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$.

Pytanie 5 z 60

Niech $a, b, c \in \mathbb{Z}$. Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.

$[(a|b) \land (b|c)] \Rightarrow c|a$.

$[(a|b) \land (a|c)] \Rightarrow (bx + cy)|a$ dla wszystkich $x, y \in \mathbb{Z}$.

$a|b \Rightarrow a|x^b$ dla każdego $x \in \mathbb{Z}$.

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.

$[(a|b) \land (a|c)] \Rightarrow a|(bx + cy)$ dla wszystkich $x, y \in \mathbb{Z}$.

Pytanie 6 z 60

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:

3-elementowej wariacji bez powtórzeń ze zbioru 4-elementowego.

podziału zbioru na dwa podzbiory.

3-elementowej permutacji bez powtórzeń ze zbioru 4-elementowego.

3-elementowej kombinacji z powtórzeniami ze zbioru 4-elementowego.

3-elementowej wariacji z powtórzeniami ze zbioru 4-elementowego.

Pytanie 7 z 60

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ą:

która nie może być rozwiązana metodą równania charakterystycznego,

dla której równanie charakterystyczne jest równaniem stopnia trzeciego.

niejednorodną,

dla której równanie charakterystyczne jest równaniem kwadratowym,

o stałych współczynnikach,

Pytanie 8 z 60

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 zbiór krawędzi, z których żadne dwie nie mają wspólnego wierzchołka końcowego.

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.

Pytanie 9 z 60

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ą,

rzędu drugiego jednorodną,

rzędu $(n+1)$-szego jednorodną.

rzędu drugiego niejednorodną,

rzędu trzeciego jednorodną,

Pytanie 10 z 60

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 zawierający te elementy przestrzeni $U$, które nie należą do $A$.

Zbiór potęgowy zbioru $A$ jest to zbiór wszystkich podzbiorów zbioru $A$.

Dopełnienie zbioru $A$ jest to zbiór $A \cup U$.

Dopełnienie zbioru $A$ jest to zbiór $A \cap U$.

Dopełnienie zbioru $A$ jest to zbiór $A \setminus U$.

Pytanie 11 z 60

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

W grafie $G$ istnieje droga Eulera wtedy i tylko wtedy, gdy w grafie $H$ istnieje ścieżka Hamiltona.

Pytanie 12 z 60

Zaznacz zdania prawdziwe:

Każda $k$-elementowa kombinacja bez powtórzeń ze zbioru $n$-elementowego odpowiada pewnemu podziałowi tego zbioru na $k$ podzbiorów.

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

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.

Każde rozmieszczenie $k$ identycznych elementów w $n$ rozróżnialnych pudełkach odpowiada $k$-elementowej kombinacji 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$.

Pytanie 13 z 60

Wśród poniższych zdań wskaż wszystkie zdania będące definicjami drzewa.

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 posiada korzeń.

Graf $G=(V,E)$ jest drzewem, jeżeli jest spójny i $|V|=|E|-1$.

Graf $G=(V,E)$ jest drzewem, jeżeli nie zawiera cykli i $|V|=|E|+1$.

Pytanie 14 z 60

Zasada indukcji matematycznej może być zastosowana do dowodzenia twierdzeń $S(n)$, w którym $n$ należy do zbioru:

liczb całkowitych.

liczb naturalnych.

liczb rzeczywistych.

dowolnego podzbioru zbioru liczb wymiernych.

liczb rzeczywistych dodatnich.

Pytanie 15 z 60

Zaznacz obiekt nie będący prostokątem łacińskim ze zbioru $\{1,\ldots,6\}$:

$\begin{bmatrix}3 & 1 & 2 \\2 & 3 & 1 \\1 & 2 & 6\end{bmatrix}$

$\begin{bmatrix}2 & 1 \\3 & 4 \\5 & 6 \\1 & 2 \\6 & 3 \\4 & 5\end{bmatrix}$

$\begin{bmatrix}6 & 5 & 4 & 3 \\3 & 1 & 5 & 1 \\1 & 3 & 2 & 6 \\2 & 3 & 5 & 1\end{bmatrix}$

$[1, 2, 3, 4, 5, 6]$

$\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}$

Pytanie 16 z 60

Pełna poprawna zasada włączania i wyłączania dla 4 zbiorów jest formułą składającą się z:

8 składników.

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.

nieznanej liczby składników, ponieważ ich liczba zależy od liczności tych zbiorów.

15 składników.

Pytanie 17 z 60

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 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 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 ich suma nie może być ani mniejsza, ani 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}$.

Pytanie 18 z 60

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.

$1 + 2x + 3x^2 + 4x^3 + 5x^4 + \dots$ jest wykładniczą funkcją tworzącą sekwencji liczb $1, 2, 3, 4, 5, \dots$.

$1 + 2x + 3x^2 + 4x^3 + 5x^4 + \dots$ jest funkcją tworzącą sekwencji liczb $0, 1, 2, 3, 4, \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 $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 19 z 60

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:

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

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

$1+2^2x+3^2x^2+4^2x^3+...$jest funkcją tworzącą sekwencji liczb $1^2, 2^2, 3^2, 4^2, ...$

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

Pytanie 20 z 60

Zaznacz zdania prawdziwe:

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.

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

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.

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.

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 21 z 60

Zaznacz zdanie prawdziwe.

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

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.

Wyznaczenie wzoru jawnego jest możliwe dla ciągów liczbowych opisanych jedynie zależnościami rekurencyjnymi jednorodnymi.

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.

Pytanie 22 z 60

Niech $A, B$ i $C$ będą podzbiorami pewnej przestrzeni $U$. Wśród poniższych zdań wskaż prawa algebry zbiorów.

$A \cap (A \cup B) = \overline{A}$

$\overline{A \cap B} = \overline{A} \cap \overline{B}$

$A \cup (A \cap B) = A$

$(A \cap B) \cap C = A \cup (B \cap C)$

$\overline{A \cup B} = \overline{A} \cap \overline{B}$

Pytanie 23 z 60

Zaznacz zdanie prawdziwe.

Dowód uogólnionej zasady szufladkowej Dirichleta wymaga zastosowania zwykłej zasady szufladkowej.

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.

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

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

Pytanie 24 z 60

Ś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:

co najwyżej 9.

dokładnie 9.

dokładnie 3.

co najmniej 9.

nie może być określona.

Pytanie 25 z 60

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^6$

$r_B(x) = 1 + 27x + 75x^2 + 145x^3 + 96x^4 + 12x^5$

$r_B(x) = 2 + 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^5$

Pytanie 26 z 60

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 funkcją tworzącą sekwencji liczb $1, 1, \frac{1}{2!}, \frac{1}{3!}, \frac{1}{4!}, \dots$.

$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 wykładniczą funkcją tworzącą sekwencji liczb $1, 1, 1, 1, 1, 1, \dots$.

$e^x$ jest funkcją tworzącą sekwencji liczb $1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, \dots$.

Pytanie 27 z 60

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe.

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

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 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) = 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$.

Pytanie 28 z 60

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 niejednorodną.

liniową ze stałymi współczynnikami rzędu drugiego jednorodną.

liniową ze stałymi współczynnikami rzędu pierwszego jednorodną.

liniową ze stałymi współczynnikami rzędu trzeciego jednorodną.

liniową ze stałymi współczynnikami rzędu trzeciego niejednorodną.

Pytanie 29 z 60

Zaznacz zdania prawdziwe.

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

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 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)}$.

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.

Pytanie 30 z 60

Zaznacz zdania prawdziwe:

W ciągu liczby Stirlinga drugiego rodzaju mogą pojawić się liczby niebędące liczbami całkowitymi.

Liczby Fibonacciego są liczbami opisanymi zależnością rekurencyjną rzędu trzeciego, ponieważ w definicji występują trzy elementy ciągu.

Liczby harmoniczne rzędu $r$, dla $r > 1$, tworzą ciąg rozbieżny.

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 Eulera związane są z liczbą cykli Eulera w grafie.

Pytanie 31 z 60

Wskaż wszystkie zdania prawdziwe:

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ą 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$ i $Q$ mają przeciwne 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$ ma wartość logiczną prawdy zawsze wtedy, gdy $Q$ ma wartość logiczną prawdy.

Pytanie 32 z 60

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 $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 $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 $\operatorname{lcm}(a,b)$ dzieli $c$.

Pytanie 33 z 60

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 \land F_0, p$

$p \rightarrow q, \neg p \lor q$

$p \land T_0, \neg p$

$p \land F_0, F_0$

$p \lor T_0, p$

Pytanie 34 z 60

Zaznacz zdania prawdziwe.

W ciągu liczby Stirlinga drugiego rodzaju mogą pojawić się liczby nie będące liczbami całkowitymi.

Liczby Eulera związane są z liczbą cykli Eulera w grafie.

Liczby harmoniczne rzędu $r$, dla $r > 1$, tworzą ciąg rozbieżny.

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.

Pytanie 35 z 60

Zaznacz zdanie prawdziwe.

Liczby harmoniczne drugiego rzędu $H_n^{(2)}$ są dyskretnym odpowiednikiem funkcji $f(x) = \frac{1}{x}$.

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.

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.

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

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 36 z 60

Zaznacz zdanie prawdziwe.

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

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

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

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

Pytanie 37 z 60

Zaznacz zdanie prawdziwe:

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

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 \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, 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 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.

Pytanie 38 z 60

Ś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 3.

dokładnie 6.

co najmniej 8.

co najwyżej 6.

co najmniej 6.

Pytanie 39 z 60

Zaznacz zdania prawdziwe.

Dowód zasady szufladkowej Dirichleta wykorzystuje pojęcie uporządkowanego podziału zbioru.

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

„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}$.

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.

Pytanie 40 z 60

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:

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.

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)| \geq n - |I|$ dla każdego $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\}$.

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\}$.

Pytanie 41 z 60

Pełna poprawna zasada włączania i wyłączania dla 4 zbiorów składa się z

15 składników.

4 składników, ponieważ są 4 zbiory.

5 składników.

16 składników, ponieważ należy sprawdzić część wspólną każdego zbioru z każdym.

nieskończonej liczby składników.

Pytanie 42 z 60

Zaznacz zdania prawdziwe.

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.

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

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

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

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ą.

Pytanie 43 z 60

Zaznacz zdania prawdziwe.

Dowód zasady włączania i wyłączania w postaci alternatywnej jest oparty o prawa teorii mnogości.

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

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

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

Pytanie 44 z 60

Niech $G=(V,E)$ będzie grafem nieskierowanym bez wierzchołków izolowanych. Wśród poniższych zdań wskaż zdania prawdziwe.

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

$G$ zawiera cykl Hamiltona 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 nieparzystym.

Pytanie 45 z 60

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:

dwóch 3-elementowych permutacji z powtórzeniami, w których poszczególne elementy występują tylko jeden raz.

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.

podziału uporządkowanego zbioru $\{A, B, C, D, E, F\}$, ponieważ elementy w obiektach są ustawione alfabetycznie.

Pytanie 46 z 60

Wskaż wszystkie zdania prawdziwe:

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

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ą.

Pytanie 47 z 60

Zaznacz zdanie prawdziwe.

Liczba wszystkich $k$-elementowych kombinacji z powtórzeniami ze zbioru $n$-elementowego wynosi $\binom{k + n - 1}{n}$ gdzie $k < n$.

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ć 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.

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.

Pytanie 48 z 60

Zaznacz zdania prawdziwe:

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

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

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

Pytanie 49 z 60

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.

Istnieje $b^b$ różnych $b$-wyrazowych wariacji z powtórzeniami ze zbioru $a$-elementowego $(a \leq b$ lub $b < a)$.

Liczba $k$-wyrazowych wariacji z powtórzeniami ze zbioru $n$-elementowego jest nie większa od liczby $k$-wyrazowych wariacji bez powtórzeń.

$k$-wyrazowa wariacja z powtórzeniami ze zbioru $n$-elementowego odpowiada rozmieszczeniu $k$ rozróżnialnych elementów w $n$ rozróżnialnych pudełkach.

Pytanie 50 z 60

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:

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

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 istnieją liczby całkowite $x$ i $y$, takie że $ax + by = 2$.

Pytanie 51 z 60

Wśród poniższych zdań wskaż reguły podstawiania.

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

Pytanie 52 z 60

Zaznacz zdanie prawdziwe.

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

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

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

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.

Pytanie 53 z 60

Wybierz wszystkie poprawne:

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 $\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 wszystkich zawodników.

Pytanie 54 z 60

Zaznacz zdania prawdziwe:

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

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.

Kwadratem grecko-łacińskim, czyli kwadratem Eulera, nazywamy złożenie dwóch dowolnych kwadratów łacińskich o takim samym rozmiarze.

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

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

Pytanie 55 z 60

Zaznacz zdanie prawdziwe.

Dowód poprawności pierwszej zasady indukcji matematycznej opiera się o zasadę dobrego uporządkowania i wykorzystuje technikę sprowadzania do sprzeczności.

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.

Zbiorem dobrze uporządkowanym jest dowolny podzbiór zbioru liczb całkowitych oraz liczb wymiernych, ale nie liczb rzeczywistych.

Zasada dobrego uporządkowania stwierdza, że zbiór liczb całkowitych zawiera element najmniejszy.

Zbiór liczb całkowitych ujemnych jest dobrze uporządkowany.

Pytanie 56 z 60

Wśród poniższych zdań wskaż definicje odpowiednich relacji.

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 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 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 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 57 z 60

Zaznacz zdania prawdziwe:

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

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

„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.

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.

Pytanie 58 z 60

Zaznacz zdania prawdziwe.

Liczba wszystkich $k$-elementowych kombinacji bez powtórzeń z $n$-elementowego zbioru wynosi $\binom{n}{k}$ gdzie $n \leq k$ lub $k < n$

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.

Każde rozmieszczenie $k$ identycznych elementów w $n$ rozróżnialnych pudełkach odpowiada $k$-elementowej kombinacji bez powtórzeń ze zbioru $n$-elementowego.

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żda $k$-elementowa kombinacja bez powtórzeń ze zbioru $n$-elementowego odpowiada pewnemu podziałowi tego zbioru na $k$ podzbiorów.

Pytanie 59 z 60

Zaznacz zdanie prawdziwe.

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

W wielomianie szachowym dla dowolnej szachownicy o wymiarze $n \times n$ mogą wystąpić niezerowe współczynniki $r_k$ dla $k > n$.

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

Pytanie 60 z 60

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 bez powtórzeń ze zbioru 5-elementowego.

4-elementowej kombinacji z powtórzeniami ze zbioru 5-elementowego.

Uporządkowanego podziału zbioru na dwa podzbiory.

5-elementowej wariacji z powtórzeniami ze zbioru 4-elementowego.

4-elementowej wariacji bez powtórzeń ze zbioru 5-elementowego.

Losowa kolejność Reset Start

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