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ę ${{𝒦}}_9$ lub antyklikę ${{𝒜}}_9$ Dobrze

klikę ${{𝒦}}_{10}$ lub antyklikę ${{𝒜}}_{10}$ Dobrze

klikę ${{𝒦}}_{512}$ lub antyklikę ${{𝒜}}_{512}$ Źle

klikę ${{𝒦}}_{1024}$ lub antyklikę ${{𝒜}}_{1024}$ Źle

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

istnieje liczba naturalna $n\in \mathbb{\mathbb{N}}$ taka, że graf $\mathbf{𝐆}$ zawiera jako podgraf indukowany klikę ${{𝒦}}_n$ lub antyklikę ${{𝒜}}_n$ Dobrze

dla dowolnej liczby naturalnej $n\in \mathbb{\mathbb{N}}$ graf $\mathbf{𝐆}$ zawiera jako podgraf indukowany klikę ${{𝒦}}_n$ lub antyklikę ${{𝒜}}_n$ Dobrze

dla dowolnej liczby naturalnej $n\in \mathbb{\mathbb{N}}$ graf $\mathbf{𝐆}$ zawiera jako podgraf indukowany klikę ${{𝒦}}_n$ oraz antyklikę ${{𝒜}}_n$ Źle

graf $\mathbf{𝐆}$ zawiera jako podgraf indukowany przeliczalną klikę ${{𝒦}}_{\mathbb{\mathbb{N}}}$ lub przeliczalną antyklikę ${{𝒜}}_{\mathbb{\mathbb{N}}}$ Dobrze

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

dla każdego zbioru $X$ o co najmniej $q$ elementach i dowolnego rozbicia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{n}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_m } , istnieje $p$ -elementowy podzbiór $Y$ zbioru $X$ taki, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{n}\!\left( Y \right)\subseteq \mathscr{A}_i } przy pewnym $i=1,\dots ,t$ Dobrze

dla każdego zbioru $X$ o co najmniej $n$ elementach i dowolnego rozbicia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{r}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_t } , istnieje $q$ -elementowy podzbiór $Y$ zbioru $X$ taki, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{r}\!\left( Y \right)\subseteq \mathscr{A}_i } przy pewnym $i=1,\dots ,t$ Dobrze

dla każdego zbioru $X$ o co najmniej $q$ elementach i dowolnego rozbicia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{n}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_m } , istnieje $\lceil q/m\rceil$ -elementowy podzbiór $Y$ zbioru $X$ taki, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{n}\!\left( Y \right)\subseteq \mathscr{A}_p } Źle

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

Liczba Ramseya Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( 3,4 \right) } to:

$6$ Źle

$9$ Dobrze

$14$ Źle

co najwyżej $10$ Dobrze

Liczba Ramseya Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}_{r}\!\left( 4,4 \right) } spełnia:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}_{r}\!\left( 4,4 \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r}\!\left( 3,4 \right),{\sf R}_{r}\!\left( 4,3 \right) \right)+1 } Dobrze

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}_{r}\!\left( 4,4 \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r}\!\left( 3,4 \right),{\sf R}_{r}\!\left( 4,3 \right) \right) } Źle

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}_{r}\!\left( 4,4 \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r-1}\!\left( 3,4 \right),{\sf R}_{r-1}\!\left( 4,3 \right) \right)+1 } Źle

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}_{r}\!\left( 4,4 \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r-1}\!\left( 3,4 \right),{\sf R}_{r-1}\!\left( 4,3 \right) \right) } Źle

Liczby Ramseya Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( n,n \right) } spełniają:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle n2^{n/2}\left( \frac{1}{e\sqrt{2}}-{\sf o}\!\left( 1 \right) \right)\leq{\sf R}\!\left( n,n \right) } Dobrze

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle n2^{2n}\left( \frac{1}{e\sqrt{2}}-{\sf o}\!\left( 1 \right) \right)\leq{\sf R}\!\left( n,n \right) } Źle

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( n,n \right)\geq { 2n-2 \choose n-1 } } Dobrze

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( n,n \right)\geq { 2n \choose n } } Źle