Matematyka dyskretna 2/Test 3: Własności podziałowe i Twierdzenie Ramsey'a

Komoda ma $10$ szuflad. Pierwsza jest w stanie pomieścić $1$ koszulę, druga $2$ i w ogólności $i$ -ta szuflada jest w stanie pomieścić $i$ koszul. Do przechowania jest $46$ koszul. Wtedy:

nie da się pomieścić wszystkich koszul w komodzie Źle

wszystkie szuflady będą w pełni zapełnione Źle

co najmniej jedna z szuflad będzie w pełni zapełniona Dobrze

któraś szuflada może być pusta Dobrze

Graf o $524288$ wierzchołkach zawiera jako podgraf indukowany:

klikę ${\mathcal {K}}_{9}$ lub antyklikę ${\mathcal {A}}_{9}$ Dobrze

klikę ${\mathcal {K}}_{10}$ lub antyklikę ${\mathcal {A}}_{10}$ Dobrze

klikę ${\mathcal {K}}_{512}$ lub antyklikę ${\mathcal {A}}_{512}$ Źle

klikę ${\mathcal {K}}_{1024}$ lub antyklikę ${\mathcal {A}}_{1024}$ Źle

Jeśli graf $\mathbf {G}$ ma nieskończenie wiele wierzchołków, to:

istnieje liczba naturalna $n\in \mathbb {N}$ taka, że graf $\mathbf {G}$ zawiera jako podgraf indukowany klikę ${\mathcal {K}}_{n}$ lub antyklikę ${\mathcal {A}}_{n}$ Dobrze

dla dowolnej liczby naturalnej $n\in \mathbb {N}$ graf $\mathbf {G}$ zawiera jako podgraf indukowany klikę ${\mathcal {K}}_{n}$ lub antyklikę ${\mathcal {A}}_{n}$ Dobrze

dla dowolnej liczby naturalnej $n\in \mathbb {N}$ graf $\mathbf {G}$ zawiera jako podgraf indukowany klikę ${\mathcal {K}}_{n}$ oraz antyklikę ${\mathcal {A}}_{n}$ Źle

graf $\mathbf {G}$ zawiera jako podgraf indukowany przeliczalną klikę ${\mathcal {K}}_{\mathbb {N} }$ lub przeliczalną antyklikę ${\mathcal {A}}_{\mathbb {N} }$ Dobrze

Dla dowolnych $n,m,p\in \mathbb {N}$ istnieje liczba $q$ taka, że:

dla każdego zbioru $X$ o co najmniej $q$ elementach i dowolnego rozbicia ${\mathcal {P}}_{n}\!\left(X\right)={\mathcal {A}}_{1}\cup \ldots \cup {\mathcal {A}}_{m}$ , istnieje $p$ -elementowy podzbiór $Y$ zbioru $X$ taki, że ${\mathcal {P}}_{n}\!\left(Y\right)\subseteq {\mathcal {A}}_{i}$ przy pewnym Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i=1,\ldots,t} Dobrze

dla każdego zbioru Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle X} o co najmniej Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle n} elementach i dowolnego rozbicia Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \mathcal{P}_{r}\!\left( X \right)=\mathcal{A}_1\cup\ldots\cup\mathcal{A}_t} , istnieje Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle q} -elementowy podzbiór Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle Y} zbioru Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle X} taki, że Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \mathcal{P}_{r}\!\left( Y \right)\subseteq \mathcal{A}_i} przy pewnym Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i=1,\ldots,t} Dobrze

dla każdego zbioru Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle X} o co najmniej $q$ elementach i dowolnego rozbicia ${\mathcal {P}}_{n}\!\left(X\right)={\mathcal {A}}_{1}\cup \ldots \cup {\mathcal {A}}_{m}$ , istnieje $\left\lceil q/m\right\rceil$ -elementowy podzbiór $Y$ zbioru $X$ taki, że ${\mathcal {P}}_{n}\!\left(Y\right)\subseteq {\mathcal {A}}_{p}$ Źle

Żadna z pozostałych własności nie musi zachodzić Źle

Liczba Ramseya ${\mathsf {R}}\!\left(3,4\right)$ to:

$6$ Źle

$9$ Dobrze

$14$ Źle

co najwyżej $10$ Dobrze

Liczba Ramseya ${\mathsf {R}}_{r}\!\left(4,4\right)$ spełnia:

${\mathsf {R}}_{r}\!\left(4,4\right)\leq {\mathsf {R}}_{r-1}\!\left({\mathsf {R}}_{r}\!\left(3,4\right),{\mathsf {R}}_{r}\!\left(4,3\right)\right)+1$ Dobrze

${\mathsf {R}}_{r}\!\left(4,4\right)\leq {\mathsf {R}}_{r-1}\!\left({\mathsf {R}}_{r}\!\left(3,4\right),{\mathsf {R}}_{r}\!\left(4,3\right)\right)$ Źle

${\mathsf {R}}_{r}\!\left(4,4\right)\leq {\mathsf {R}}_{r-1}\!\left({\mathsf {R}}_{r-1}\!\left(3,4\right),{\mathsf {R}}_{r-1}\!\left(4,3\right)\right)+1$ Źle

${\mathsf {R}}_{r}\!\left(4,4\right)\leq {\mathsf {R}}_{r-1}\!\left({\mathsf {R}}_{r-1}\!\left(3,4\right),{\mathsf {R}}_{r-1}\!\left(4,3\right)\right)$ Źle