Test GR4

\newtheorem{thm}{Twierdzenie} \newtheorem{obs}[thm]{Obserwacja} \newtheorem{con}[thm]{Wniosek} \newtheorem{exrr}{Zadanie}

{

\parindent 0mm

#1 \parindent 10mm }{\hfill{ $◻$ }

}

{article} \input{../makraT}

\newpage

\parindent 0mm \beginLarge

Uzupelnij tytul
Współczynniki dwumianowe

\endLarge

\parindent 10mm

\btest

Zależność $(\binom{n}{0}) - (\binom{n}{1}) + \dots + (- 1)^{n} (\binom{n}{n}) = 0$ zachodzi dla:} \ok wszystkich liczb naturalnych $n$ \odp tylko skończenie wielu liczb naturalnych $n$ \odp żadnej liczby naturalnej $n$ \ok wszystkich, poza skończenie wieloma liczbami naturalnymi $n$

Suma elementów $n$ -tego wiersza Trójkąta Pascala bez obu wartości brzegowych to:}

\odp $2^{n}$ . \ok $2^{n} - 2$ . \ok $\sum_{i = 1}^{n} (\binom{n}{i}) - 1$ . \odp $(\binom{2 n}{n})$ .

Współczynnik przy wyrazie $x^{n}$ w rozwinięciu dwumianu $(x + 2)^{2 n}$ to:} \odp $(\binom{2 n}{n})$ . \odp $2^{n} (\binom{n}{2})$ . \ok $(\binom{2 n}{n}) 2^{n}$ . \odp $(\binom{2 n}{n}) 2^{2 n}$ .

$(\binom{- 1}{k})$ dla $k ⩾ 0$ jest równe:} \odp $0$ . \odp $1$ . \odp $(- 1)^{k}$ . \ok $(- 1)^{k + 1}$

Suma $\sum_{i = 0}^{n} 2^{i} (\binom{n}{i})$ wynosi} \odp $2^{n}$ . \ok $3^{n}$ . \odp $(n + 2)^{n}$ . \odp $(\binom{2 n}{n})$ .

Liczba nieporządków na zbiorze $3$ -elementowym to:} \odp $1$ . \ok $2$ . \odp $3$ . \odp $6$ .

$(\binom{n}{a, b, 0, \dots, 0})$ gdzie $a + b = n$ to:} \ok $(\binom{n}{a})$ . \ok $(\binom{n}{b})$ . \odp $(\binom{n}{a + b})$ . \odp $(\binom{n + a + b}{a + b})$ .

Na ile sposobów z grupy $5 n$ osób, złożonej z $3 n$ mężczyzn i $2 n$ kobiet, można wybrać $n$ -kobiet i $n$ -mężczyzn, i dodatkowo z niewybranych mężczyzn wyznaczyć przywódcę?} \odp $((\binom{5 n}{3 n}) (\binom{3 n}{n}) + (\binom{5 n}{2 n}) (\binom{2 n}{n})) \cdot 2 n$ . \ok $(\binom{3 n}{n}) (\binom{2 n}{n}) \cdot 2 n$ . \odp $((\binom{3 n}{n}) + (\binom{2 n}{n})) \cdot 2 n$ . \odp $(\binom{3 n}{n}) (\binom{2 n}{n}) \cdot 3 n$ .

Suma $(\binom{0}{7}) + (\binom{1}{7}) + (\binom{2}{7}) + (\binom{3}{7}) + (\binom{4}{7}) + (\binom{5}{7}) + (\binom{6}{7}) + (\binom{7}{7})$ to:} \odp $0$ . \odp $(\binom{8}{7})$ . \odp $(\binom{7}{8})$ . \ok $(\binom{8}{8})$ .

Współczynnik przy wyrazie $x^{m} y^{n}$ w rozwinięciu dwumianu $(x + y)^{m + n}$ to:} \ok $(\binom{m + n}{m})$ . \ok $(\binom{m + n}{n})$ . \odp $(\binom{m}{n})$ . \odp $\sum_{i = 0}^{m} (\binom{m + n}{i})$ .

\etest

66666666666666666666666666666

{article} \input{../makraT}

\newpage

\parindent 0mm \beginLarge

Uzupelnij tytul
Permutacje i podziały

\endLarge

\parindent 10mm

\btest

Niech $n_{π}, n_{σ}, n_{ρ}$ będą kolejno liczbami permutacji w $S_{7}$ tego samego typu co, odpowiednio, $π = (14) (26) (357)$ , $σ = (1357) (246)$ , $ρ = (12) (34) (56) (7)$ . Wtedy:} \ok $n_{π} ⩽ n_{τ} ⩽ n_{ρ}$ \ok $n_{τ} ⩽ n_{π} ⩽ n_{ρ}$ \odp $n_{ρ} ⩽ n_{π} ⩽ n_{τ}$ \odp $n_{π} ⩽ n_{ρ} ⩽ n_{τ}$

Dla sprzężonych permutacji $π, σ \in S_{13}$ zachodzi:} \ok $π$ i $σ$ mają tyle samo cykli $4$ -elementowych \odp elementy $1$ i $2$ albo są w tym samym cyklu w obu permutacjach,

   albo nie są w tym samym cyklu w obu permutacjach

\ok $π$ i $σ$ mają ten sam typ \ok $π$ i $σ$ mają ten sam znak

Dla $n ⩾ 2$ ,

   podziałowa liczba Stirlinga   ${\begin{array}{c} n \\ 2 \end{array}}$  wynosi:}

\odp $\sum_{k = 1}^{n - 1} (\binom{n}{k}) k! = \sum_{k = 1}^{n - 1} \frac{n!}{k!}$ \odp $n! \sum_{k = 1}^{n - 1} \frac{1}{k (n - k)}$ \odp $n! \sum_{k = 1}^{n - 1} \frac{1}{k (n - k)}$ \ok $\frac{n!}{2} \sum_{k = 1}^{n - 1} \frac{1}{k (n - k)}$

Średnia liczba cykli permutacji $n$ -elementowej (czyli stosunek sumarycznej liczby cykli we wszystkich permutacjach $n$ -elementowych do liczby cykli $n$ -elementowych) to:} \odp $2 n$ \odp $⌊ \frac{n}{\lg n} ⌋ + 1$ \ok $\sum_{k = 1}^{n} \frac{1}{k}$ \odp $\frac{n}{2}$

Podziałowa liczba Stirlinga ${\begin{array}{c} 7 \\ 4 \end{array}}$ wynosi} \odp $90$ \odp $140$ \odp $301$ \ok $350$

Jednomian $x^{n}$ jest równy:} \ok $\sum_{i} {\begin{array}{c} n \\ i \end{array}} x^{\underline{i}}$ \odp $B_{n} x^{\underline{n}}$ , gdzie $B_{n}$ jest $n$ -tą liczbą Bella \odp $\sum_{i} [\begin{array}{c} n \\ i \end{array}] x^{\overline{i}}$ \ok $\sum_{i} {\begin{array}{c} n \\ i \end{array}} (- 1)^{n - i} x^{\overline{i}}$

Na ile sposobów można rozłożyć $a$ rozróżnialnych obiektów do dokładnie $b$ rozróżnialnych szuflad, tak by każda szufladka była niepusta?} \odp $b^{a}$ \odp ${\begin{array}{c} a \\ b \end{array}}$ \ok $b! {\begin{array}{c} a \\ b \end{array}}$ \odp $(\binom{a - 1}{b - 1})$

Na ile sposobów można rozłożyć $a$ nierozróżnialnych obiektów do co najwyżej $b$ rozróżnialnych szuflad?} \odp $(\binom{a - 1}{b - 1})$ \ok $(\binom{b + a - 1}{b - 1})$ \odp ${\begin{array}{c} a \\ b \end{array}}$ \odp $\sum_{i = 1}^{b} {\begin{array}{c} a \\ i \end{array}}$

Gdy $P (n, k)$ jest liczbą rozkładów liczby $n$ na sumy dokładnie $k$ nieujemnych całkowitych składników, to $\lim_{n \to \infty} \frac{P (n, k)}{n^{k}}$ wynosi:} \ok $0$ \odp $\frac{1}{k! (k - 1)!}$ \odp $\frac{1}{k}$ \odp $1$

Na ile sposobów można podzielić zbiór $a$ elementowy na $b + c$ bloków, przy czym $b$ bloków jest wyróżnionych?} \ok ${\begin{array}{c} a \\ b + c \end{array}} (\binom{b + c}{b})$ \ok $\sum_{k} (\binom{a}{k}) {\begin{array}{c} k \\ b \end{array}} {\begin{array}{c} a - k \\ c \end{array}}$ \odp ${\begin{array}{c} a \\ b \end{array}} {\begin{array}{c} a - b \\ c \end{array}}$ \odp ${\begin{array}{c} a \\ b + c \end{array}} b!$

\etest

777777777777777777777777777777777777777777777777777777777

{article} \input{../makraT}

\newpage

\parindent 0mm \beginLarge

Uzupelnij tytul
Funkcje tworzące

\endLarge

\parindent 10mm

\btest

Na ile sposobów można rozmienić $25$ centów za pomocą monet $1$ , $5$ , $10$ oraz $25$ centowych?}

<wrongoption>  $6$  }
<wrongoption>  $12$  }
<rightoption>  $13$  }
<wrongoption>  $49$  }

Funkcja tworząca postaci $G (x) = g_{0} + g_{1} x + g_{2} x^{2} + g_{3} x^{3} + \dots$ ma odwrotną względem mnożenia (splotu), tzn. istnieje funkcja tworząca $U (x)$ taka, że $U (x) G (x) = 1$ }

<wrongoption>jeśli   $g_{0} \neq 1$  }
<rightoption>jeśli   $g_{0} \neq 0$  }
<rightoption>jeśli wszystkie   $g_{i} \neq 0$  }
<rightoption>wtedy i tylko wtedy, gdy   $g_{0} \neq 0$  }

Funkcja $G (x)$ spełniająca

 $G (x) = (\sum_{n = 0}^{\infty} x^{n}) \cdot (1 + x G (x))$

jest funkcją tworzącą:} <wrongoption>ciągu $1, 1, 2, 4, 8, 16, 32, \dots, 2^{n - 1}, \dots$ } <rightoption>ciągu geometrycznego $g_{n} = 2^{n}$ } <wrongoption>nie ma takiego ciągu} <wrongoption>nie istnieje taka funkcja tworząca}

Funkcja $G (x)$ spełniająca

 $G (x) = G^{'} (x)$   oraz   $G (0) = 1$

jest funkcją tworzącą ciągu:} <wrongoption> $g_{n} = \frac{1}{n}$ } <rightoption> $g_{n} = \frac{1}{n!}$ } <wrongoption> $g_{n} = 1$ } <wrongoption> $g_{0} = 1$ oraz $g_{n} = 0$ dla $n > 1$ }

Niech $G (x) = {(1 + x)}^{y}$ , gdzie $y$ jest liczba rzeczywistą. Jeśli $G (x) = \sum_{n = 0}^{\infty} g_{n} x^{n}$ , to:} <wrongoption> $g_{n} = \frac{{(y + n)}^{\underline{n}}}{n}$ } <wrongoption> $g_{n} = \frac{y^{n}}{n!}$ } <wrongoption> $g_{n} = (\binom{y + n}{n}) = \frac{{(y + n)}^{\underline{n}}}{n!}$ } <rightoption> $g_{n} = (\binom{y}{n}) = \frac{y^{\underline{n}}}{n!}$ }

Suma $\sum_{k = 0}^{n} (3 k^{2} - 3 k + 1)$ wynosi:} <wrongoption> $2 n^{3} + 3 n + n$ ,} <rightoption> $n^{3}$ ,} <wrongoption> $(2 n^{3} + 3 n + n) / 6$ ,} <wrongoption> $3 n^{3} - 3 n^{2} + n$ }

Niech $a_{0} = 2$ , $a_{1} = 3$ , $a_{2} = 5$ , oraz $a_{n + 3} = 7 a_{n + 2} - 16 a_{n + 1} + 12 a_{n}$ . Wtedy:} <wrongoption> $a_{n} = (1 - n) 2^{n} + 3^{n}$ } <rightoption> $a_{n} = \frac{1}{\sqrt{5}} ({(\frac{1 + \sqrt{5}}{2})}^{n + 3} - {(\frac{1 - \sqrt{5}}{2})}^{n + 3})$ } <wrongoption> $a_{n} = \frac{1}{\sqrt{5}} ({(\frac{1 + \sqrt{5}}{2})}^{n} - {(\frac{1 - \sqrt{5}}{2})}^{n})$ } <wrongoption>żadna z pozostałych odpowiedzi nie jest prawidłowa}

\etest

8888888888888888888888888888888888888888888888

{article} \input{../makraT}

\newpage

\parindent 0mm \beginLarge

Uzupelnij tytul
Zliczanie obiektów

\endLarge

\parindent 10mm

\btest

Liczby Catalana $c_{n}$ spełniają zależność rekurencyjną:} <wrongoption> $c_{n} = \sum_{k = 1}^{n - 1} c_{k}$ } <wrongoption> $c_{n} = \sum_{k = 1}^{n} c_{k}$ } <wrongoption> $c_{n} = \sum_{k = 1}^{n - 1} c_{k} c_{n - k}$ } <rightoption> $c_{n} = \sum_{k = 1}^{n} c_{k - 1} c_{n - k}$ }

$n$ -ta liczba Catalana to:} <wrongoption> $(\binom{2 n}{n})$ } <rightoption> $\frac{1}{n + 1} (\binom{2 n}{n})$ } <wrongoption> $(\binom{1 / 2}{n}) {(- 4)}^{n}$ } <rightoption> $2 (\binom{1 / 2}{n + 1}) {(- 4)}^{n}$ }

Niech $t_{10}$ będzie liczbą drzew o wysokości $10$ . Wtedy:} <rightoption> $t_{10} \leq 2^{1023}$ } <rightoption> $t_{10} \geq 2^{512}$ } <wrongoption> $t_{10} \leq 2^{10}$ } <wrongoption> $t_{10} \geq 2^{9}$ }

Liczba podziałów liczby $16$ na sumy złożone jedynie ze składników $1, 2, 4, 8, 16$ wynosi:} <wrongoption> $25$ } <wrongoption> $26$ } <rightoption> $35$ } <wrongoption> $165$ }

Funkcja tworząca podziału liczby na sumy jest przedstawialna jako:} <rightoption> $\prod_{k = 1}^{\infty} \frac{1}{1 - x^{k}}$ } <wrongoption> $\sum_{k = 1}^{\infty} \frac{1}{1 - x^{k}}$ } <wrongoption> $\sum_{n = 0}^{\infty} \prod_{k = 1}^{\infty} \frac{1}{1 - x^{n k}}$ } <rightoption> $\prod_{k = 1}^{\infty} \sum_{n = 0}^{\infty} x^{n k}$ }

Funkcja tworząca

 $s_{n} (x) = [\begin{array}{c} n \\ 0 \end{array}] + [\begin{array}{c} n \\ 1 \end{array}] x + [\begin{array}{c} n \\ 2 \end{array}] x^{2} + [\begin{array}{c} n \\ 3 \end{array}] x^{3} + \dots,$

dla cyklowych liczb Stirlinga $[\begin{array}{c} n \\ m \end{array}]$ , ma postać zwartą: } <rightoption> $s_{n} (x) = x^{\overline{n}}$ } <rightoption> $s_{n} (x) = \prod_{k = 0}^{n - 1} (x + k)$ } <wrongoption> $s_{n} (x) = x^{\underline{n}}$ } <wrongoption> $s_{n} (x) = 1 / \prod_{k = 0}^{n - 1} (1 - k x)$ }

Podziałowe liczby Stirlinga spełniają zależność rekurencyjną:} <wrongoption> ${\begin{array}{c} n \\ k \end{array}} = (n - 1) {\begin{array}{c} n - 1 \\ k \end{array}} + {\begin{array}{c} n - 1 \\ k - 1 \end{array}}$ , dla $0 > k > n$ } <wrongoption> ${\begin{array}{c} n + k \\ k \end{array}} = {\begin{array}{c} n + k - 1 \\ k \end{array}} + k {\begin{array}{c} n + k - 1 \\ k - 1 \end{array}}$ , dla $n > 1, k > 0$ } <rightoption> ${\begin{array}{c} n + k \\ k \end{array}} = k {\begin{array}{c} n + k - 1 \\ k \end{array}} + {\begin{array}{c} n + k - 1 \\ k - 1 \end{array}}$ , dla $n > 1, k > 0$ } <wrongoption>żadna z pozostałych odpowiedzi nie jest prawidłowa}

Niech $a_{0} = 1$ , $a_{1} = 0$ oraz $a_{n} = \frac{a_{n - 2}}{n}$ . Funkcja tworząca $A (x) = \sum_{n = 0}^{\infty} a_{n} x^{n}$ ma postać zwartą:} <wrongoption> $A (x) = \sin x$ } <wrongoption> $A (x) = e^{x^{2}}$ } <rightoption> $A (x) = e^{x^{2} / 2}$ } <wrongoption>żadna z pozostałych odpowiedzi nie jest prawidłowa}

\etest

999999999999999999999999999999999999999

{article} \input{../makraT}

\newpage

\parindent 0mm \beginLarge

Uzupelnij tytul
Asymptotyka

\endLarge

\parindent 10mm

\btest

Funkcja $n^{2} \lg n + \frac{n^{2} \sqrt{n}}{\lg n}$ jest:} \odp $Θ (n^{2} \lg n)$ \odp $O (n^{2} \lg n)$ \odp $Θ n^{2} \sqrt{n}$ \ok $O (\frac{n^{2} \sqrt{n}}{\lg n})$

Funkcja $\frac{n^{9}}{\lg^{10} n}$ jest:} \odp $O (n^{\frac{9}{10}})$ \odp $O (n)$ \ok $O (n^{9})$ \ok $Ω (\lg^{10} n)$

Dla $f (n) = 2^{\lg n + 1}$ oraz $g (n) = \lg 2 n - 1$ zachodzi:} \odp $f (x) = ω (g (x))$ \ok $f (x) = Ω (g (x))$ \ok $f (x) = Θ (g (x))$ \ok $f (x) = O (g (x))$ \odp $f (x) = o (g (x))$

Dowolny wielomian $k$ -tego stopnia jest:} \ok $Ω (n^{k})$ \ok $Θ (n^{k})$ \ok $O (n^{k})$ \ok $o (n^{k + ε})$ dla dowolnego $ε > 0$

Dla $f (n) = \frac{\lg n}{n}$ oraz $g (n) = \frac{1}{\sqrt{n}}$ zachodzi:} \odp $f (x) = ω (g (x))$ \odp $f (x) = Ω (g (x))$ \odp $f (x) = Θ (g (x))$ \ok $f (x) = O (g (x))$ \ok $f (x) = o (g (x))$

Dla $f (x) = x^{2}$ oraz $g (x) = x^{2} + \sin x$ zachodzi:} \ok $f (x) = Ω (g (x))$ \ok $f (x) = Θ (g (x))$ \ok $f (x) = O (g (x))$ \odp żadne z pozostałych

Dla $T (n) = 9 T (\frac{n}{3}) + \frac{n^{2}}{\lg n}$ :} \odp możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i $T (n) = Θ (n^{2})$ \odp możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i $T (n) = Θ (n^{2} \lg n)$ \odp możemy skorzystać z trzeciego punktu Tw. o rekurencji uniwersalnej i $T (n) = Θ (\frac{n^{2}}{\lg n})$ \ok żadne z pozostałych

Dla $T (n) = 25 T (\frac{n}{4}) + \frac{n^{2}}{\lg n}$ } \ok możemy skorzystać z pierwszego punktu Tw. o rekurencji uniwersalnej i $T (n) = Θ (n^{\lg_{4} 25})$ \odp możemy skorzystać z drugiego punktu Tw. o rekurencji uniwersalnej i $T (n) = Θ (n^{2})$ \odp możemy skorzystać z trzeciego punktu Tw. o rekurencji uniwersalnej i $T (n) = Θ (\frac{n^{2}}{\lg n})$ \odp żadne z pozostałych

Funkcja spełniająca zależność $T (n) = T (\frac{n}{2}) + 1$ jest:} \ok $Θ (\lg n)$ \ok $Θ (n)$ \ok $O (n)$ \odp żadne z pozostałych

\etest

101010101010101010101010101010101010

{article} \input{../makraT}

\newpage

\parindent 0mm \beginLarge

Uzupelnij tytul
Teoria liczb I

\endLarge

\parindent 10mm

\btest

Liczb naturalnych $n > 1$ w rozkładzie których występują wszystkie liczby pierwsze niewiększe od $n$ jest:} \odp nieskończenie wiele \ok co najmniej jedna \ok skończenie wiele \odp nie ma takich liczb

Liczb pierwszych postaci $91 n + 7$ , dla $n \in ℕ$ jest:} \odp nie ma takich liczb \ok dokładnie jedna \ok skończenie wiele \odp nieskończenie wiele

Jeśli w ciągu postaci ${a n + b}_{n \in ℕ}$ , gdzie $a, b \in ℕ$ , są przynajmniej dwie liczby pierwsze, to} \ok jest ich nieskończenie wiele \odp wszystkie liczby tego ciągu są pierwsze \odp może ich być tylko skończenie wiele \ok $a$ i $b$ są względnie pierwsze

Jeśli $p$ jest dowolną liczbą pierwszą, to sito Eratostenesa zastosowane do liczby $p^{2} + 2$ jako ostatnią skreśli:} \odp $p$ \ok $p^{2}$ \odp $p^{2} + 1$ \odp $p^{2} + 2$

Jeśli $a | b c$ oraz \sf NWD $(a, b) = d$ , to} \ok $\frac{a}{d} | c$ \ok $a | c d$ \ok $\frac{a}{d} ⊥ b$ \ok $\frac{a}{d} ⊥ \frac{b}{d}$

Liczb pierwszych postaci $n^{2} - 1$ , gdzie $n \in ℕ$ , jest:} \odp $0$ \ok $1$ \ok skończenie wiele \odp nieskończenie wiele

Jeśli $a$ i $b$ są liczbami złożonymi to} \odp \sf NWD $(a, b) > 1$ \ok Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \frac{a}{ } \sf NWD $(a, b) ⊥ \frac{b}{}$ \sf NWD Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (a,b)}} \odp jedna z liczb Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \frac{a}{ } \sf NWD Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (a,b)}} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \frac{b}{ } \sf NWD Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (a,b)}} jest pierwsza \odp jeśli $a ⊥ b$ , to przynajmniej jedna z liczb $a - b$ , $a + b$ jest parzysta

Jeśli $a | c$ i $b | c$ , to} \odp \sf NWD $(a, b) > 1$ \odp \sf NWD $(a, b) < c$ \ok jeśli \sf NWD $(a, b) > 1$ , to \sf NWW $(a, b) < c$ \ok \sf NWW $(a, b) ⩽ c$

Rosnący ciąg arytmetyczny rozpoczynający się od $1$ :} \ok zawsze zawiera nieskończenie wiele liczb pierwszych \odp może zawierać tylko skończenie wiele liczb pierwszych \odp zawsze zawiera tylko skończenie wiele liczb pierwszych \odp może nie zawierać żadnej liczby pierwszej

\etest

11111111111111111111111111111111

{article} \input{../makraT}

\newpage

\parindent 0mm \beginLarge

Uzupelnij tytul
Teoria liczb II

\endLarge

\parindent 10mm

\btest

Jeśli $d ⊥ n$ oraz $a c d \equiv_{c n} b c d$ , to} \ok $a \equiv_{n} b$ \ok $a d \equiv_{n} b d$ \ok $a c d \equiv_{n} b c d$ \odp $a c \equiv_{n d} b c$

Równanie $7 x \equiv_{91} 4$ } \odp nie ma rozwiązania \odp ma skończenie wiele rozwiązań \odp zbiór wszystkich jego rozwiązań jest postaci ${13 n + c : n \in N}$ dla pewnego $c \in ℕ$ \ok zbiór wszystkich rozwiązań jest postaci ${91 n + c : n \in ℕ}$ dla pewnego $c \in ℕ$

Układ równań

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x&\equiv_9&8,\\ x&\equiv_{223}&222. \endaligned}

} \ok ma całkowite rozwiązanie mniejsze od 2006 \odp $2006$ jest jego jedynym rozwiązaniem \odp wszystkie jego rozwiązania są postaci $2006 \cdot n$ , gdzie $n \in ℤ$ \ok wszystkie jego rozwiązania są postaci $2007 n + 2006$

Dla $a < b$ warunek $φ (a) ⩽ φ (b)$ zachodzi jeśli} \odp $a ⩽ b$ \ok $a | b$ \odp $a ⊥ b$ \ok $a ⩽ b$ i $b$ jest pierwsza

$1 6^{49}$ {\sf mod} $25$ wynosi:} \odp $1$ \odp $7$ \odp $14$ \ok $21$

$1 4^{111}$ {\sf mod} $15$ wynosi:} \odp $1$ \odp $3$ \odp $12$ \ok $14$

Wiedząc, że $2006 = 2 \cdot 17 \cdot 59$ oblicz $μ (2006)$ : } \ok $- 1$ \odp $0$ \odp $1$ \odp $3$

$(n - 1)!$ modulo $n$ to:} \ok $0$ , jeśli $n$ jest złożona a $- 1$ , jeśli $n$ jest pierwsza \ok $0$ , jeśli $n$ jest złożona a $n - 1$ , jeśli $n$ jest pierwsza \odp $0$ , jeśli $n$ jest złożona a $1$ , jeśli $n$ jest pierwsza \odp zawsze wynosi $1$

\etest

12121212121212121212121212121212

{article} \input{../makraT}

\newpage

\parindent 0mm \beginLarge

Uzupelnij tytul
Grafy I

\endLarge

\parindent 10mm

\btest

Różnych grafów skierowanych bez cykli jednoelementowych w zbiorze $n$ -elementowym jest:} \odp $2^{n^{2}}$ \ok $2^{n^{2} - n}$ \odp $2^{2^{n}}$ \odp $2^{2^{n} - n}$ \odp $2^{(\binom{n}{2})}$

Różnych grafów nieskierowanych bez cykli jednoelementowych w zbiorze $n$ -elementowym jest:} \odp $2^{n^{2}}$ \odp $2^{n^{2} - n}$ \odp $2^{2^{n}}$ \odp $2^{2^{n} - n}$ \ok $2^{(\binom{n}{2})}$

Zaznacz zdania prawdziwe:} \odp W każdym grafie prostym $G = (V; E)$ relacja $E$ musi być zwrotna. \ok W grafie nieskierowanym $G = (V, E)$ relacja $E$ jest symetryczna. \odp Graf nieskierowany to rodzina wszystkich dwuelementowych podzbiorów zbioru wierzchołków. \ok W grafie pełnym każde dwa różne wierzchołki połączone są krawędzią.

Zaznacz zdania prawdziwe dla grafów nieskierowanych:} \ok podgraf indukowany grafu pełnego jest grafem pełnym \ok każdy graf jest podgrafem jakiegoś grafu pełnego \odp każdy graf jest podgrafem indukowanym jakiegoś grafu pełnego \odp graf pełny ma zawsze parzystą liczbę krawędzi \ok w grafie pełnym wszystkie wierzchołki mają ten sam stopień

Jaka jest najmniejsza liczba krawędzi w grafie nieskierowanym o 100 wierzchołkach i trzech składowych spójnych:}

\odp  $99$ 
\ok  $97$ 
\odp  $98$ 
\odp  $100$ 
\odp  $\frac{100 \cdot 99}{3}$

Ile jest krawędzi w pełnym grafie dwudzielnym $K_{1000, 1000}$ :}

\ok  $1000 \cdot 1000$ 
\odp  $1000!$ 
\odp  $(\binom{1000}{2})$ 
\odp  $(\binom{1000}{50})$ 
\odp  $(\binom{2000}{1000})$

W pełnym grafie $100$ -elementowym:} \odp każde drzewo rozpinające ma $100$ krawędzi \odp dokładnie jedno drzewo rozpinające ma $100$ krawędzi \ok każde drzewo rozpinające ma $99$ krawędzi \odp dokładnie jedno drzewo rozpinające ma $99$ krawędzi \odp nie ma drzew rozpinających

W pełnym grafie dwudzielnym $K_{50, 50}$ :} \odp każde drzewo rozpinające ma $50$ krawędzi \odp każde drzewo rozpinające ma $100$ krawędzi \ok każde drzewo rozpinające ma $99$ krawędzi \odp dokładnie jedno drzewo rozpinające ma $99$ krawędzi \odp nie ma drzew rozpinających

W $100$ elementowym grafie o trzech składowych spójnych:} \odp jakiś las rozpinający ma $100$ krawędzi \odp jakiś las rozpinający ma $99$ krawędzi \odp jakiś las rozpinający ma $98$ krawędzi \ok jakiś las rozpinający ma $97$ krawędzi \odp może nie być lasu rozpinającego

Pełny graf $100$ -elementowy:} \ok jest grafem Hamiltonowskim \odp jest grafem Eulerowskim \odp jest spójny \odp jest dwudzielny \ok jest stukolorowalny

Pełny graf dwudzielny $K_{25, 25}$ :} \ok jest grafem Hamiltonowskim \odp jest grafem Eulerowskim \ok zawiera cykl $4$ wierzchołkach jako podgraf indukowany \odp zawiera cykl $6$ wierzchołkach jako podgraf indukowany \ok jest trójkolorowalny

Graf o $2005$ wierzchołkach, z których każdy ma stopień $101$ :} <wrongoption>ma $202505$ krawędzi} <wrongoption>ma $2106$ krawędzi} <wrongoption>ma $405010$ krawędzi} <rightoption>nie istnieje}

Jeśli $𝐆_{1} = (V, E_{1})$ i $𝐆_{2} = (V, E_{2})$ są grafami niespójnymi o tym samym zbiorze wierzchołków $V$ , to:} <rightoption>graf $𝐆_{1} \cup 𝐆_{1}$ może być spójny} <wrongoption>graf $𝐆_{1} \cup 𝐆_{1}$ jest spójny} <rightoption>graf $𝐆_{1} \cap 𝐆_{1}$ może nie być spójny} <rightoption>graf $𝐆_{1} \cap 𝐆_{1}$ nie jest spójny}

Graf $𝐏_{4}$ to graf, który składa się jedynie ze ścieżki odwiedzającej $4$ wierzchołki, czyli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf V}\!\left(\mathbf{P}_4\right)=\left\lbrace a,b,c,d \right\rbrace } oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf E}\!\left(\mathbf{P}_4\right)=\left\lbrace \left\lbrace a,b \right\rbrace,\left\lbrace b,c \right\rbrace,\left\lbrace c,d \right\rbrace \right\rbrace } . W grafie spójnym, w którym nie ma podgrafu indukowanego izomorficznego do $𝐏_{4}$ :} <rightoption>dowolne dwa punkty leżą w odległości co najwyżej trzy} <rightoption>dowolne dwa punkty leżą w odległości co najwyżej dwa} <wrongoption>dowolne dwa punkty leżą w odległości co najwyżej jeden} <wrongoption>każde trzy wierzchołki tworzą klikę $𝒦_{3}$ }

Zaznacz zdania prawdziwe:} <rightoption>Każdy graf pusty jest grafem dwudzielnym.} <wrongoption>Każdy graf pełny jest grafem dwudzielnym.} <wrongoption>Graf $𝒦_{3}$ jest grafem dwudzielnym.} <rightoption>Graf $𝒦_{2}$ jest grafem dwudzielnym.}

Zaznacz zdania prawdziwe:} <rightoption>Każdy graf dwudzielny, który jest zarazem grafem pełnym jest planarny.} <rightoption>Graf $𝒦_{4}$ jest grafem planarnym.} <wrongoption>Graf $𝒦_{5}$ jest grafem planarnym.} <wrongoption>Każdy graf dwudzielny jest grafem planarnym.}

Graf o $100$ wierzchołkach:} <wrongoption>jeśli ma $99$ krawędzi, to jest drzewem.} <wrongoption>jeśli ma $100$ krawędzi, to jest drzewem.} <wrongoption>jeśli ma $4850$ krawędzi, to jest spójny.} <rightoption>jeśli ma $4851$ krawędzi, to jest spójny.}

Na to by graf $𝐓$ był drzewem potrzeba i wystarcza, by:} <wrongoption> $𝐓$ nie zawierał cykli} <rightoption> $𝐓$ był spójny i miał $| V | - 1$ krawędzi} <rightoption>dowolne dwa wierzchołki grafu $𝐓$ były połączone dokładnie jedną drogą} <wrongoption>dowolne dwa wierzchołki grafu $𝐓$ leżały na dokładnie jednym cyklu}

\etest

131313131313131313131313131313

{article} \input{../makraT}

\newpage

\parindent 0mm \beginLarge

Uzupelnij tytul
Grafy II

\endLarge

\parindent 10mm

\btest

Pełny graf dwudzielny $𝒦_{3, 3}$ :} <wrongoption>jest eulerowski} <rightoption>jest hamiltonowski} <wrongoption>jest planarny} <wrongoption>nie jest ani eulerowski ani planarny}

Pełny graf $100$ -elementowy:} \ok jest grafem Hamiltonowskim \odp jest grafem Eulerowskim \odp jest spójny \odp jest dwudzielny \ok jest stukolorowalny

Graf, w którym cykl Hamiltona jest zarazem cyklem Eulera} <wrongoption>sam jest cyklem o parzystej liczbie krawędzi} <rightoption>jest cyklem} <rightoption>ma wierzchołki wyłącznie o stopniu $2$ } <wrongoption>jest sumą dwu grafów o tych samych wierzchołkach ale rozłącznych zbiorach krawędzi, przy czym każdy z nich jest cyklem}

Jeśli graf $𝐆$ jest eulerowski, to:} <wrongoption>graf $𝐆$ jest hamiltonowski} <rightoption>każdy wierzchołek w grafie $𝐆$ ma parzysty stopień} <rightoption>graf $𝐆$ jest sumą grafów o tych samych wierzchołkach ale rozłącznych zbiorach krawędzi, przy czym każdy z nich jest cyklem} <wrongoption>jeśli dodatkowo $𝐆$ jest hamiltonowski, to po usunięciu cyklu Hamiltona graf $𝐆$ dalej jest eulerowski}

Graf o $101$ wierzchołkach:} <wrongoption>w którym wszystkie wierzchołki są stopnia $50$ , jest hamiltonowski} <rightoption>w którym wszystkie wierzchołki są stopnia $51$ , jest hamiltonowski} <wrongoption>w którym dowolne dwa niesąsiednie wierzchołki $v$ i $w$ spełniają $\deg v + \deg w \geq 100$ jest hamiltonowski} <wrongoption>w którym dowolne dwa sąsiednie wierzchołki $v$ i $w$ spełniają $\deg v + \deg w \geq 100$ jest hamiltonowski}

Który z warunków wystarcza na to, by w grafie dwudzielnym $𝐆 = (V_{1} \cup V_{2}, E)$ istniało pełne skojarzenie $V_{1}$ z $V_{2}$ ?} <rightoption>graf $𝐆$ jest hamiltonowski} <wrongoption>graf $𝐆$ jest eulerowski} <wrongoption>w grafie $𝐆$ każdy wierzchołek z $V_{1}$ ma co najmniej dwu sąsiadów} <rightoption>dowolny zbiór niezależny w ma co najwyżej $| V_{2} |$ wierzchołków}

Grafem $100$ -spójnym jest:} <rightoption>graf w którym pomiędzy dowolnymi wierzchołkami istnieje $100$ dróg wierzchołkowo rozłącznych} <wrongoption>graf, którego każdy zbiór rozdzielający ma co najmniej $99$ wierzchołków} <rightoption>klika $𝒦_{101}$ } <wrongoption>pełny graf dwudzielny $𝒦_{100, 100}$ }

W $2$ -spójnym krawędziowo grafie o $20$ wierzchołkach i minimalnej liczbie krawędzi:} <wrongoption>jest dokładnie $38$ krawędzi} <rightoption>jest dokładnie $20$ krawędzi} <rightoption>dowolny wierzchołek ma stopień co najmniej $2$ } <wrongoption>istnieje wierzchołek o stopniu co najmniej $3$ }

\etest

141414141414141414141414141414141414141414

{article} \input{../makraT}

\newpage

\parindent 0mm \beginLarge

Uzupelnij tytul
Grafy III

\endLarge

\parindent 10mm

\btest

Który z grafów przedstawionych na Rysunku Uzupelnic test petersen4| jest planarny?

\beginfigure [!ht] \begincenter \includegraphics{test_petersen4} \caption{ [Rysunek z pliku: test\_petersen4.eps]} \endcenter \endfigure }

<wrongoption>graf przedstawiony na rysunku Uzupelnic test petersen4|.a.} <wrongoption>graf przedstawiony na rysunku Uzupelnic test petersen4|.b.} <wrongoption>graf przedstawiony na rysunku Uzupelnic test petersen4|.c.} <rightoption>graf przedstawiony na rysunku Uzupelnic test petersen4|.d.}

Który z grafów przedstawionych na Rysunku Uzupelnic test klika5| jest homeomorficzny z kliką $𝒦_{5}$ ?

\beginfigure [!ht] \begincenter \includegraphics{test_klika5} \caption{ [Rysunek z pliku: test\_klika5.eps]} \endcenter \endfigure }

<wrongoption>graf przedstawiony na rysunku Uzupelnic test klika5|.a.} <wrongoption>graf przedstawiony na rysunku Uzupelnic test klika5|.b.} <rightoption>graf przedstawiony na rysunku Uzupelnic test klika5|.c.} <wrongoption>graf przedstawiony na rysunku Uzupelnic test klika5|.d.}

Spójny graf planarny o $20$ wierzchołkach, z których każdy jest stopnia $3$ ma:} <wrongoption> $11$ ścian} <rightoption> $12$ ścian} <wrongoption> $22$ ścian} <wrongoption> $24$ ścian}

Ile spójnych składowych ma graf planarny o $121$ wierzchołkach,

 $53$   krawędziach, oraz   $30$   ścianach?}

<rightoption> $98$ } <wrongoption> $99$ } <wrongoption> $100$ } <wrongoption> $143$ }

Niech $𝐆^{*}$ będzie grafem geometrycznie dualnym do grafu płaskiego $𝐆$ . Podzbiór $C$ zbioru krawędzi grafu $𝐆$ jest cyklem w grafie $𝐆$ wtedy i tylko wtedy, gdy zbiór krawędzi dualnych do krawędzi zbioru $C$ } <wrongoption>posiada parzystą liczbę elementów} <wrongoption>posiada nieparzystą liczbę elementów} <wrongoption>jest cyklem grafu $𝐆^{*}$ } <rightoption>jest rozcięciem grafu $𝐆^{*}$ }

Spójny graf prosty, który nie jest pełny,

i w którym wszystkie wierzchołki  mają stopień nie większy niż   $k$  jest:}

<wrongoption> $(k - 1)$ -kolorowalny} <rightoption> $k$ -kolorowalny} <rightoption> $(k + 1)$ -kolorowalny} <rightoption> $2 k$ -kolorowalny}

Iloma kolorami można pokolorować polityczną mapę Europy?} <wrongoption> $3$ } <rightoption> $4$ } <rightoption> $5$ } <rightoption> $6$ }

W grafie prostym zachodzi:} <rightoption> $χ (𝐆) \leq χ_{s} (𝐆) + 1$ } <wrongoption> $χ (𝐆) \leq χ_{s} (𝐆)$ } <wrongoption> $χ (𝐆) \geq χ_{s} (𝐆) + 1$ } <wrongoption> $χ (𝐆) = χ_{s} (𝐆)$ }

Pełny graf dwudzielny $K_{50, 50}$ :} \ok jest grafem Hamiltonowskim \ok jest grafem Eulerowskim \odp jest lasem \ok jest dwukolorowalny \ok jest 49-kolorowalny

\etest

151515151515151515151515151515151515

{article} \input{../makraT}

\newpage

\parindent 0mm \beginLarge

Uzupelnij tytul
Metody algebraiczne w teorii grafów

\endLarge

\parindent 10mm

\btest

Niech $m_{i j}$ oznacza liczbę skierowanych marszrut, nie dłuższych niż $n - 1$ , z wierzchołka $v_{i}$ do $v_{j}$ w grafie skierowanym $𝐆 = ({v_{1}, \dots, v_{n}}, E)$ , a $M$ niech będzie macierzą $⟨ m_{i j} ⟩$ . Wtedy:} <rightoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle M={\sf A}\left( \mathbf{G} \right)^1+{\sf A}\left( \mathbf{G} \right)^2+\ldots+{\sf A}\left( \mathbf{G} \right)^{\left( n-1 \right)} } } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle M={\sf A}\left( \mathbf{G} \right)^{\left( n-1 \right)} } } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle M=n\cdot{\sf A}\left( \mathbf{G} \right) } } <rightoption> $m_{i j} > 0$ wtedy i tylko wtedy, gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( v_i,v_j \right)\in{\sf E}\!\left({\sf TC}\left( \mathbf{G} \right)\right) } }

Zaznacz prawdziwe zależności dla grafu prostego $𝐆$ o macierzy sąsiedztwa Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathbf{G} \right) } , macierzy incydencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf B}\left( \mathbf{G} \right) } , zorientowanej macierzy incydencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf C}\left( \mathbf{G} \right) } oraz macierzy stopni Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf D}\left( \mathbf{G} \right) } :} <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf B}\left( \mathbf{G} \right)\cdot {\sf B}\left( \mathbf{G} \right)^T= {\sf A}\left( \mathbf{G} \right)- {\sf D}\left( \mathbf{G} \right) } } <rightoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf B}\left( \mathbf{G} \right)\cdot {\sf B}\left( \mathbf{G} \right)^T= {\sf D}\left( \mathbf{G} \right)+ {\sf A}\left( \mathbf{G} \right) } } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf B}\left( \mathbf{G} \right) \cdot{\sf A}\left( \mathbf{G} \right) = {\sf C}\left( \mathbf{G} \right) } } <wrongoption> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf C}\left( \mathbf{G} \right)\cdot {\sf C}\left( \mathbf{G} \right)^T= {\sf A}\left( \mathbf{G} \right)- {\sf D}\left( \mathbf{G} \right) } }

Niech $𝐆$ będzie grafem o $10$ wierzchołkach przedstawionym na Rysunku Uzupelnic test alg|, a macierz $M$ , o rozmiarach $9 \times 9$ , będzie minorem (podmacierzą) zorientowanej macierzy incydencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf C}\left( \mathbf{G} \right) } , w którym kolumny odpowiadają krawędziom

 $e_{0}, e_{2}, e_{3}, e_{6}, e_{9}, e_{12}, e_{13}, e_{14}, e_{15}$  .

\beginfigure [!ht] \begincenter \includegraphics{test_alg} \caption{Graf $𝐆$ . [Rysunek z pliku: test\_alg.eps]} \endcenter \endfigure

Wtedy:} <rightoption>macierz $M$ jest nieosobliwa} <wrongoption>macierz $M$ jest osobliwa} <wrongoption>suma elementów w każdej kolumnie macierzy $M$ wynosi $0$ } <wrongoption>macierz $M$ jest antysymetryczna}

Na to by permanent grafu $𝐆$ był niezerowy, wystarcza by:} <rightoption>graf $𝐆$ posiadał cykl Hamiltona} <wrongoption>graf $𝐆$ posiadał cykl Eulera} <wrongoption>graf $𝐆$ był spójny} <rightoption>graf $𝐆$ był grafem dwudzielnym posiadającym skojarzenie doskonałe}

Zaznacz zdania prawdziwe o wartościach własnych grafów:} <wrongoption>Co najmniej jedna z wartości własnych jest liczbą zespoloną.} <wrongoption>Jeśli wszystkie wartości własne są wymierne, to graf jest eulerowski.} <rightoption>Wszystkie wartości własne grafu hamiltonowskiego są rzeczywiste.} <rightoption>Wszystkie wartości własne dowolnego grafu są rzeczywiste.}

Zaznacz prawdziwe związki wartości własnych z maksymalnym stopniem wierzchołka w grafie prostym:} <wrongoption> $λ_{m a x} (𝐆) = Δ (𝐆)$ } <rightoption> $| λ_{m a x} (𝐆) | \leq Δ (𝐆)$ } <rightoption> $λ_{m a x} (𝐆) = Δ (𝐆)$ wtedy i tylko wtedy, gdy któraś spójna składowa grafu $𝐆$ jest grafem regularnym stopnia $Δ (𝐆)$ } <rightoption> $- Δ (𝐆)$ jest wartością własną macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathbf{G} \right) } wtedy i tylko wtedy, gdy $𝐆$ jest regularnym grafem dwudzielnym stopnia $Δ (𝐆)$ }

W grafie regularnym $𝐆$ o $10$ wierzchołkach stopnia $4$ oraz wartościach własnych $λ_{m i n} (𝐆) \approx - 2, 73205$ i $λ_{m a x} (𝐆) = 4$ moc niezależnego podzbioru jest ograniczona z góry przez:} <wrongoption> $2$ } <wrongoption> $3$ } <rightoption> $4$ } <rightoption> $10$ }

Zaznacz zdania prawdziwe wiążące liczbę chromatyczną $χ (𝐆)$ z wartościami własnymi grafu regularnego $𝐆$ :} <rightoption> $χ (𝐆) \geq 1 - \frac{λ_{m a x} (𝐆)}{λ_{m i n} (𝐆)}$ } <wrongoption> $χ (𝐆) = 1 - \frac{λ_{m a x} (𝐆)}{λ_{m i n} (𝐆)}$ } <rightoption> $χ (𝐆) \leq λ_{m a x} (𝐆) + 1$ } <wrongoption> $χ (𝐆) \geq λ_{m a x} (𝐆)$ }

\etest

Test GR4

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia