Kombagra 1

$$\left ( \sqrt{x} - \sqrt{y} \right )^{2} \ge 0$$ $$x - 2 \sqrt{x y} + y \ge 0$$ $$x + y \ge 2 \sqrt{x y}$$ $$\frac{x + y}{2} \ge \sqrt{x y}$$ $$✨$$

$$n !^{2} = \left ( n \cdot 1 \right ) \cdot \left ( \left ( n - 1 \right ) \cdot 2 \right ) \cdot \left ( \left ( n - 2 \right ) \cdot 3 \right ) \cdot \cdots \cdot \left ( 1 \cdot n \right )$$

Každý z těchto činitelů $c_{i} \ge n$, $c_{i} = i \cdot \left ( n - i + 1 \right )$. To protože na okrajích $i = 1$ nebo $i = n$ je to zjevně $n$.

V intervalu $i \in \left \lbrace 2 , n - 1 \right \rbrace$ je $\min \left ( i , n - i + 1 \right ) \ge 2$ a $\max \left ( i , n - i + 1 \right ) \ge \frac{n}{2}$

tudíž

$$n !^{2} \ge n^{n}$$

$$n ! \ge n^{\frac{n}{2}}$$

Předem se omlouvám, je to convoluted AF. Obrázek je důležitej, vlastně zavíráme $\ln{\left ( n ! \right )}$ mezi dva integrály $\ln{\left ( n ! \right )}$ co má jiný meze.

Spodní odhad. Pojďme se podívat na to, jak se chová funkce $\ln{\left ( n ! \right )}$.

$\ln{\left ( n ! \right )} = \sum_{i = 1}^{n} \ln{\left ( i \right )} =$ modrá část.

$\ln{\left ( n ! \right )}$ tedy odpovídá modré části. Ta je určitě větší než červená, což je integrál $\ln{x}$ od $1$ do $n$.

Červená:

$$\int_{1}^{n} \ln{\left ( x \right )} dx = \left [ x \cdot \ln{x} - x \right ]_{1}^{n} = n \ln{n} - n + 1$$

Můžeme z logaritmu udělat výsledek itegrálu tím hodnotu zmenšit. $$n ! = e^{\ln{\left ( n ! \right )}} \ge e^{n \ln{n} - n + 1} = n^{n} \cdot \frac{1}{e^{n}} \cdot e = e \left ( \frac{n}{e} \right )^{n}$$

K dokázání horního odhadu nám pomůže zelená část. Je vlastně stejná jako ta modrá, akorát je posunutá doprava. Pokud budeme porovnávat její hodnotu s červenou částí, tak červená bude větší, musíme ji ale také posunout. Integrál bude tedy od $1$ do $n + 1$

$$\ln{\left ( n ! \right )} \le \int_{1}^{n + 1} \ln{\left ( x \right )} dx = \left [ x \cdot \ln{x} - x \right ]_{1}^{n + 1}$$ $$= \left ( n + 1 \right ) \ln{\left ( n + 1 \right )} - n$$

$$n ! = e^{\ln{\left ( n ! \right )}} \le e^{n + 1} \ln{\left ( n + 1 \right )} - n = \frac{\left ( n + 1 \right )^{n + 1}}{e^{n}}$$

Nyní opět evil matematický dosazení aby nám vyšlo to co chceme. Za $n$ dosadíme $n - 1$.

$$n ! = n \cdot \underbrace{\left ( n - 1 \right ) !}_{\text{dis one}} \le n \cdot \left ( \frac{n^{n}}{e^{n - 1}} \right ) = e n \left ( \frac{n}{e} \right )^{n}$$

Celkově tedy

$$e \left ( \frac{n}{e} \right )^{n} \le n ! \le e n \left ( \frac{n}{e} \right )^{n}$$ 🔲

Patří do analýzy nebo tak něco

Spodní odhad

$$\left ( \forall i \in \left \lbrace 0 , \ldots , k - 1 \right \rbrace \right ) \left ( \frac{n - i}{k - i} \ge \frac{n}{k} \right )$$

(důkaz roznásobením). Díky tomu

$$\left ( \begin{matrix} n \\ k \end{matrix} \right ) \overset{\text{def}}{=} \prod_{i = 0}^{k - 1} \frac{n - i}{k - i} \ge \prod_{i = 0}^{k - 1} \frac{n}{k} = \left ( \frac{n}{k} \right )^{k}$$

Horní odhad

Nechť $x = \frac{k}{n}$. Všimni si že $0 \le x \le 1$ protože $k \le n$

Budiž vymyšlený výraz:

$$\left ( \begin{matrix} n \\ 0 \end{matrix} \right ) x^{0} + \left ( \begin{matrix} n \\ 1 \end{matrix} \right ) x^{1} + \ldots + \left ( \begin{matrix} n \\ n \end{matrix} \right ) x^{n} = \left ( 1 + x \right )^{n}$$

Na levé straně vynecháme sčítance za $x^{k}$

$$\left ( \begin{matrix} n \\ 0 \end{matrix} \right ) x^{0} + \left ( \begin{matrix} n \\ 1 \end{matrix} \right ) x^{1} + \ldots + \left ( \begin{matrix} n \\ k \end{matrix} \right ) x^{k} \le \left ( 1 + x \right )^{n}$$

Vydělíme $x^{k}$

$$\frac{1}{x^{k - 0}} \left ( \begin{matrix} n \\ 0 \end{matrix} \right ) + \frac{1}{x^{k - 1}} \left ( \begin{matrix} n \\ 1 \end{matrix} \right ) + \ldots + \frac{1}{x^{k - k}} \left ( \begin{matrix} n \\ k \end{matrix} \right ) \le \frac{\left ( 1 + x \right )^{n}}{x^{k}}$$

Na levé straně je každý koeficient $\ge 1$, takže když je vynecháme tak stranu pouze zmenšíme.

$$\left ( \begin{matrix} n \\ 0 \end{matrix} \right ) + \left ( \begin{matrix} n \\ 1 \end{matrix} \right ) + \ldots + \left ( \begin{matrix} n \\ k \end{matrix} \right ) \le \frac{\left ( 1 + x \right )^{n}}{x^{k}}$$

Všimni si cool feature je že už tam je ten $\left ( \begin{matrix} n \\ k \end{matrix} \right )$ který chceme! Expandujeme $x = \frac{k}{n}$.

$$\left ( \begin{matrix} n \\ 0 \end{matrix} \right ) + \left ( \begin{matrix} n \\ 1 \end{matrix} \right ) + \ldots + \left ( \begin{matrix} n \\ k \end{matrix} \right ) \le \left ( 1 + \frac{k}{n} \right )^{n} \cdot \left ( \frac{n}{k} \right )^{k}$$

(všimni si obrácení zlomku $\frac{k}{n}$ kterým dělíme)

využijeme fakt: $1 + x \le e^{x}$ ($\to 1 + \frac{k}{n} \le e^{\frac{k}{n}}$) pro umlácení pravé strany:

$$\left ( 1 + \frac{k}{n} \right )^{n} \le \left ( e^{\frac{k}{n}} \right )^{n} = e^{k}$$

tedy dostaneme

$$\left ( \begin{matrix} n \\ 0 \end{matrix} \right ) + \left ( \begin{matrix} n \\ 1 \end{matrix} \right ) + \ldots + \left ( \begin{matrix} n \\ k \end{matrix} \right ) \le e^{k} \cdot \left ( \frac{n}{k} \right )^{k}$$

Vlevo zahodíme Binomické koeficienty které nás nezajímají (zase pouze zmenší)

$$\left ( \begin{matrix} n \\ k \end{matrix} \right ) \le \left ( \frac{e n}{k} \right )^{k}$$

🔲

Nejdříve si pořiďme P. $$P := \frac{1 \cdot 3 \cdot 5 \cdot \cdots \cdot \left ( 2 m - 1 \right )}{2 \cdot 4 \cdot 6 \cdot \cdots \cdot \left ( 2 m \right )}$$ Vynásobíme 1 $$P = \frac{1 \cdot 3 \cdot 5 \cdot \cdots \cdot \left ( 2 m - 1 \right )}{2 \cdot 4 \cdot 6 \cdot \cdots \cdot \left ( 2 m \right )} \cdot \frac{2 \cdot 4 \cdot \cdots \cdot \left ( 2 m \right )}{2 \cdot 4 \cdot \cdots \cdot \left ( 2 m \right )}$$ $$= \frac{\left ( 2 m \right ) !}{2^{2 m} \cdot \left ( m ! \right )^{2}}$$ $$= \frac{1}{2^{2 m}} \cdot \left ( \begin{matrix} 2 m \\ m \end{matrix} \right )$$ To nám pomůže, protože v dokazované nerovnosti jsou v čitatelích právě $2^{2 m}$, takže nyní nám stačí dokázat $$\frac{1}{2 \sqrt{m}} \le P \le \frac{1}{\sqrt{2 m}}$$

Horní odhad

Uvažme posloupnost $$\left ( \frac{3}{2^{2}} \right ) \cdot \left ( \frac{3 \cdot 5}{4^{2}} \right ) \cdot \left ( \frac{5 \cdot 6}{6^{2}} \right ) \cdot \cdots \cdot \frac{\left ( 2 m - 1 \right ) \left ( 2 m + 1 \right )}{\left ( 2 m \right )^{2}}$$, ta má ve výsledku v čitateli (skoro) všechna lichá čísla dvakrát a všechna sudá čísla ve jmenovateli dvakrát. Tado posloupnost se tedy rovná $P^{2}$ až na přebytek. Co zbývá? $1$ vlevo a $2 m + 1$ vpravo. $$= \left ( 2 m + 1 \right ) P^{2}$$ Jelikož každý činitel $< 1$, tak dostáváme že $\left ( 2 m + 1 \right ) P^{2} < 1$, tedy $$P^{2} \le \frac{1}{2 m + 1}$$ Zmenšíme jmenovatel, takže zvětšíme pravou stranu. $$P^{2} \le \frac{1}{2 m}$$ $$P \le \frac{1}{\sqrt{2 m}}$$

Spodní odhad je podobný, ale má obrácené čitatele a jmenovatele. Uvažme posloupnost $$\left ( \frac{2 \cdot 4}{3^{2}} \right ) \cdot \left ( \frac{4 \cdot 6}{5^{2}} \right ) \cdot \left ( \frac{6 \cdot 8}{7^{2}} \right ) \cdot \cdots \cdot \frac{\left ( 2 m - 2 \right ) \left ( 2 m \right )}{\left ( 2 m - 1 \right )^{2}}$$, Tato posloupnost se chová skoro stejně jako $\frac{1}{P^{2}}$, až na přebytek v čitateli. Co přebývá? $2$ vlevo a $2 m$ vpravo. Tudíž $$= \frac{1}{2 \cdot \left ( 2 m \right ) \cdot P^{2}}$$ Každý člen je opět $< 1$, takže $\frac{1}{2 \cdot \left ( 2 m \right ) \cdot P^{2}} < 1$ $$P^{2} > \frac{1}{2 \cdot 2 m}$$ $$P > \frac{1}{2 \sqrt{m}}$$ 🔲

Vemme libovolné $L , L ' \in \mathcal{L}$. Nejprve pomocné pozorování:

Ozbrojeni tímto pozorováním, $L$ a $L '$ mají stejnou velikost, definujíc funkci $\varphi : L \to L '$.

Ukážeme, že $\varphi$ je bijekce.

Neformálně: $z$ je náš sniping spot a $x \in L$ jsou body skrz které střílíme do $L '$.

Vemme náš shiny bod $z$ mimo $L \cup L '$ a definujme obraz (terč) $\varphi \left ( x \right )$ pro $x \in L$ jako průnik $L '$ s přímkou která prochází body $x$ a $z$ (bullet trail).

Z axiomů 2 a 3 je terč dobře definovaný. Dvě různá $x , y \in L$ musí mít různé obrazy $varphi(x), $\varphi \left ( y \right )$ jinak by tyto dva bullet traily (přímky) sdílely více než jeden bod. Tudíž $\varphi$ je bijekce.

Nechť libovolný $x \in X$. Jistě máme $L \in \mathcal{L}$ která neobsahuje $x$.

Pro každý $y \in L$ vezmeme přímku procházející $x$ a $y$. To je jistě přímka a jistě prochází $x$ a jistě jich je $n + 1$. Nice.

Ale co kdyby existovala nějaká další zlá přímka $Z$? Taková by musela protnout $x$ ale zároveň každé 2 přímky mají společný bod takže existuje $z \in Z \cup L$ takže $z$ je jedno z $y$ a žádná zlá přímka $Z$ neexistuje.

Vezmeme $L = \left \lbrace x_{0} , \ldots , x_{n} \right \rbrace \in \mathcal{L} \rbrace$ a bod $a$ mimo $L$. Pak vyrobíme přímky $L_{0} , \ldots L_{n}$ kde $L_{i}$ protíná $a$ a $x_{i}$. Každá $L_{i}$ má $n$ dalších bodů mimo $a$, takže dohromady $n + 1$ přímek obsahuje $n$ různých bodů plus samotné $a$. $\left ( n + 1 \right ) \cdot n + 1 = n^{2} + n + 1$.

(Jednotlivá $L_{i}$ nemohou sdílet těchto “$n$ dalších bodů” protože pak by tyto 2 přímky sdíleli 2 body ($a$ a tento jeden další))

Důkaz vypadne automaticky z toho minulého po researchnutí duality.

Budiž FPR $\left ( X , \mathcal{L} \right )$ a jeho duál $\left ( \mathcal{L} , \Lambda \right )$, kde $\Lambda$ je systém podmnožin $\mathcal{L}$. Každý z těchto podmnožin odpovídá nějakému bodu z $X$.

Všimněte si, že pro různé $x \in X$ dostaneme různé podmnožiny $\mathcal{L}$.

Musíme ověřit axiomy FPR pro tento duál.

1. Přeloženo pro duál říká: Existují 4 přímky takové že žádné 3 z nich nemají společný bod. Vezmeme $\left \lbrace a , b , c , d \right \rbrace$ z původního axiomu pro neduál. Z něj vyrobíme 4 přímky: $L_{1} = a b$, $L_{2} = c d$, $L_{3} = a d$, $L_{4} = b c$. Pro tyhle to platí.
2. Je to samé jako 3. pro neduál!
3. Je to samé jako 2. pro neduál!

plyne z pozorování o počtu bodů na přímce a přímek procházející bodem

Nechť máme $\left ( a_{1} , b_{1} , c_{1} \right )$ a $\left ( a_{2} , b_{2} , c_{2} \right )$, 3D vektory v tělese $K$. Oba nenulové.

Jelikož oba nejsou násobky toho druhého, jsou lineárně nezávislé. Takže matice

$$\left ( \begin{matrix} a_{1} & b_{1} & c_{1} \\ a_{2} & b_{2} & c_{2} \end{matrix} \right )$$

má rank 2. Jukněme na sloupce jako 2D vektory. Víme že 3 vektory v 2D prostoru musí být lineárně závislé. Takže existují 3 čísla $x , y , t \in K$ taková že ne všechny najednou jsou 0 kde:

$$x \left ( a_{1} , a_{2} \right ) + y \left ( b_{1} , b_{2} \right ) + t \left ( c_{1} , c_{2} \right ) = \left ( 0 , 0 \right )$$

Pokud toto přepíšeme pro každou souřadnici zvlášť, dostaneme že bod $\left ( x , y , t \right )$ leží na obou přímkách!! (z definice ležení na přímce)

Zároveň ale protože rank matice je 2, musí existovat 2 lineárně nezávislé sloupce. Búno to jsou $\left ( a_{1} , a_{2} \right )$ a $\left ( b_{1} , b_{2} \right )$. To znamená že pro libovolný vektor $\left ( u , v \right )$ má $x \left ( a_{1} , a_{2} \right ) + y \left ( b_{1} , b_{2} \right ) = \left ( u , v \right )$ unikátní řešení.

Takže pokud se koukneme na tamtu rovnici znova:

$$x \left ( a_{1} , a_{2} \right ) + y \left ( b_{1} , b_{2} \right ) + t \left ( c_{1} , c_{2} \right ) = \left ( 0 , 0 \right )$$

pak první 2 čelny jsou zašpendlíkované na místě a jediná vůle je v posledním členu když ho škálujeme $t$čkem. ALE to znamená že rovnice může vycházet jen pro jednu hodnotu $t$!

stejně jako 2 přimky sdílí 1 bod

Třeba: $\left ( 0 , 0 , 1 \right ) , \left ( 0 , 1 , 0 \right ) , \left ( 1 , 0 , 0 \right ) , \left ( 1 , 1 , 1 \right )$ i think

Nejprve pozorování: Budiž ortogonální latinské čtverce $A$ a $B$ oba řádu $n$ a $\pi$ permutace čísel $1 , 2 , \ldots , n$.

Vyrobíme nový latinský čtverec $A '$. Ten bude mít na pozici $\left ( i , j \right )$ číslo $\pi \left ( a_{i j} \right )$ (kde $a_{i j}$ je pozice $\left ( i , j \right )$ v LČ $A$).

Po rozmyšlení je vidět že i $A '$ je ortogonální k $B$. Tudíž:

Představme si latinské čtverce $A_{1} , A_{2} , \ldots , A_{t}$ každé 2 z nich ortogonální.

Pro každé $A_{i}$: permutujme jeho symboly tak aby měl na prvním řádku bylo $1 , 2 , \ldots , n$.

Podle pozorování víme, že i tyto $A '_{1} , A '_{2} , \ldots , A '_{t}$ jsou každý s každým ortogonální.

Jukněme, co může být na pozici $\left ( 2 , 1 \right )$ některého $A '_{i}$:

• určitě ne $1$. Ta už je ve stejném sloupci na $\left ( 1 , 1 \right )$.
• žádné 2 $A '_{i} , A '_{j}$ tam nemůžou mít stejné číslo. Kdyby tam měli stejné číslo, jejich dvojice by na $\left ( 2 , 1 \right )$ měla dvojici $\left ( k , k \right )$ ale ta se už objevila na $k$tém místě prvního řádku! tudíž $2 , 3 , \ldots , n$ mohou být na pozici $\left ( 2 , 1 \right )$ pouze v jednom $A '_{i}$ takže $t \le n - 1$. 🔲

Nejprve sestrojíme FPR řádu $n$ z $n - 1$ navzájem ortogonálních LČ řádu $n$.

Jako template vezmem fancy tvar:

a teď si všimni že tam je dost bodů ale málo čar. Takže podle těch LČ které jsme stále nepoužili budeme proplétat nové přímky tím gridem vpravo dole.

Pro každé $m \in \left \lbrace 1 , 2 , \ldots , n \right \rbrace$ a $k \in \left \lbrace 1 , 2 , \ldots , n - 1 \right \rbrace$ vyrobíme přímku:

$$L_{k m} = \left \lbrace s_{k} \right \rbrace \cup \left \lbrace \left ( i , j \right ) \mid \left ( S_{k} \right )_{i j} = m \right \rbrace$$

Tzn: Začneme přímku v $s_{k}$ a tam kde má LČ $k$ políčko s číslem $m$ appendneme do přímky.

Tohle je určitě FPR (důkaz vymysli na místě). Jde provést pozpátku pro vytvoření LČ z FPR. Stačí vybrat $r$ a $c$ libovolně.🔲

Takový hrátky z cestami. v (i) si pořidíme cestu z $s$ do $t$ a říkáme, že jedna z hran této cesty je v řezu. To je vidět, protože $s$ a $t$ jsou v jiných komponentách.

ve (ii) je to to samé. Máme řez $R$. Pořídíme $A$ a $B$, A bude množina vrcholů do kterých se dá dostat v $G - R$ z $s$ a $B$ bude její doplněk. Pak tvrdíme že $S \left ( A , B \right ) \subset R$. Kdyby nebyl, tak existuje hrana v $\left ( x , y \right ) \in S r$, $x \in A$ a $y \in B$. Pak ale cesta do y nekřižuje R, tedy je ve stejné komponentě jako $s$ a tedy musí být v $A$.

Ano, je to kokotina.

Zadefinujeme přebytek na vrcholu -tj. rozdíl mezi přítokem a odtokem. Tento rozdíl je pak roven $f^{\Delta}{\left ( A , B \right )} = \sum_{v \in B} f^{\Delta}{\left ( v \right )} = f^{\Delta}{\left ( t \right )}$. První rovnost rozborem případů kudy vede hrana, druhá rovnost je triviální - všechny vrcholy mají přebytek 0.

To první jistě plyne z toho druhého

$\Rightarrow$:

Cyklus je jistě vrcholově 2-souvislý. Přidáním ucha nemůže vzniknout vrchol takový že po jeho odebrání se graf rozpadne.

$\Leftarrow$:

Budiž graf $G$ který je vrcholově 2-souvislý. K němu vyrobíme co největší podgraf $H$ který jsme vytvořili z cyklu a přilepování uší.

Tvrdím, že $H$ je indukovaný podgraf. Pokud ne, pak existuje dvojice vrcholů mezi kterýma nevede hrana v $H$ ale vede hrana v $G$. Pak ale $H$ není největší možný. Tudíž $H$ musí být indukovaný.

Předpokládám že existuje vrchol, který je v $G$ ale není v $H$. Jelikož $G$ je souvislý. Musí existovat dvojice vrcholů $u$, $v$ která sousedí a $u$ je v $H$ ale $v$ ne.

Jelikož je $G$ vrcholově 2-souvislý, po odebrání $u$ se nemůže rozpadnout. Tudíž stále existuje cesta z $v$ do $u$. To je ale ucho které jsme měli přidat takže všechny vrcholy $G$ jsou v $H$.

Jelikož $H$ a $G$ mají stejné vrchly a jelikož $H$ je indukovaný podgraf, musí to být stejné grafy. 🔲

Pokud ne, pak je obarveno jen $\le n_{1} + n_{2} + \cdots + n_{t}$ koulí.

(Note: nefunguje pro $K_{5}$. (pentagon s hvězdou uprostřed))

Vem vrchol. Koukni na 5 odchozích vrcholů. 3 z nich musí mít stejnou barvu BÚNO červená.

Teď jukni na tyhle 3 vrcholy. Můžou se stát 2 věci:

• Nějaké 2 mají taky červenou hranu mezi sebou takže výhra
• žádné 2 nemají červenou hranu mezi sebou takže! všechny 3 mají mezi sebou modrou hranu, což tvoří modrý trojúhelník.

Indukcí po $a + b$.

Init: pro $a = 1$ nebo $b = 1$ pak $K_{1}$ funguje haha. (bo $K_{1}$ má 0 hran takže pro ně platí všechno)

Indukční předpoklad:

• $R \left ( a - 1 , b \right ) \le \left ( \begin{matrix} a - 2 + b - 1 \\ a - 2 \end{matrix} \right )$
• $R \left ( a , b - 1 \right ) \le \left ( \begin{matrix} a - 1 + b - 2 \\ a - 1 \end{matrix} \right )$

Budiž $n = R \left ( a - 1 , b \right ) + R \left ( a , b - 1 \right )$ a vem $K_{n}$

Teď to přepíšeme aby to vypadalo holubníkovitě:

$$n - 1 = \underbrace{1 +}_{\text{Jedna extra hrana}} \left ( R \left ( a - 1 , b \right ) - 1 \right ) + \left ( R \left ( a , b - 1 \right ) - 1 \right )$$

Vem $v$, vrchol $K_{n}$, a zase jukni na jeho hrany. Holub tvrdí že bude:

1. $\ge R \left ( a - 1 , b \right )$ červených hran NEBO
2. $\ge R \left ( a , b - 1 \right )$ modrých hran.

Pokud 1. pak z předpokladu víme že:

• buď červený sousedi obsahují červenou $K_{a - 1}$, pak po přidání $v$ dostaneme červenou $K_{a}$
• nebo červený sousedi obsahují modrou $K_{b}$, pak yay.

Jinak 2. pak analogicky pro modré sousedy.

Chňapni $K_{n}$ kde $n \le 2^{\frac{k}{2}}$ a obarvi všechny hrany nezávisle.

Tohle nemusí fungovat obv ALE

Jak často se stane, že když vyberu množinu $X$ o $k$ vrcholech pak mají všechny stejnou barvu? well this: $\left ( \frac{1}{2} \right )^{\left ( \begin{matrix} k \\ 2 \end{matrix} \right )} + \left ( \frac{1}{2} \right )^{\left ( \begin{matrix} k \\ 2 \end{matrix} \right )}$

Jaká je šance že nějaký $k$-prvková množina vrcholů má všechny hrany stejné? well $\le$ než počet $k$-prvkových množin $\cdot P_{\text{fail}}$

něco něco idk nemám rád pravděpodobnost

Indukce podél $p$. Pro $p = 1$, barvíme $\mathbb{N}$ pomocí $t$ barev, takže nějaká barva se objeví nekonečně mnoho krát.

Řekněme že pro $p$, vem $p + 1$.

Nechť $C : \left ( \begin{matrix} \mathbb{N} \\ p + 1 \end{matrix} \right ) \to \left [ t \right ]$ je barvení všech $\left ( p + 1 \right )$-tic pomocí barev $1 , 2 , \ldots , t$.

postavíme podmnožiny $A_{1} \supseteq A_{2} \supseteq A_{3} \supseteq \ldots$ kde $A_{1} = \mathbb{N}$ a $v_{1} , v_{2} , \ldots \in \mathbb{N}$ kde $v_{1} = 1$.

Pak předpokládáĺe že už máme $A_{1} , A_{2} , \ldots , A_{i}$ a $v_{1} , v_{2} , \ldots , v_{i} \in \mathbb{N}$. Definujeme $c ' : \left ( \begin{matrix} A_{i} \, ? \\ p \end{matrix} \right )$ přiřazením barvy $c \left ( Q \cup \right )$ té $p$-tici $Q$.

Indukcí, najdi nekonečnou podmnožinu $A_i+2 sube A_i$ tak že všechny
$p$-prvkové podmnožiny dostanou stejnou barvu.

(sketch) Vem vrchol $x_{0}$ jako kořen. ten má konečně mnoho sousedů. Jukněme na ně. Součet jejich velikostí je nekonečno. takže alespoň jeden ze sousedů musí být nekonečný strom. takže půjdeme tam. Ez done

Vezmeme kovexní obal (covex hull) těchto pěti bodů. (i) Pokud je to pětiúhelník -> jakékoliv 4 dělají konvexní čtyřúhelník. (ii) Pokud je to čtyřúhelník, tak ty čtyři na okraji Předpokládejme tedy že obal je trojúhelník. Ostatní dva body nemůžou ležet na jeho okraji (obecná poloha), ale uvnitř.

Vezmeme tedy jeden a postavíme 6 částí jako na obrázku. Podle toho v jaké části leží $a_{5}$ vybereme zbývající dva vrcholy trojúhelníku společně s $a_{4}$ a máme hotovo. $a_{5}$ opět nemůže ležet mezi částmi, kvůli obecné poloze.

Pořídíme si množinu $S$ $R^{4} \left ( 5 , t \right )$ bodů v rovině. V ní obarvíme všechny čtveřice $c : \left ( \begin{matrix} S \\ 4 \end{matrix} \right ) \to \left [ 2 \right ]$ tak, že

• $c \left ( X \right ) = 1$, tak netvoří konvexní čtyřúhelník
• $c \left ( X \right ) = 2$, tak tvoří konvexní čtyřúhelník

Množství bodů (Ramseyovo číslo) nám teď říká, že:

• existuje pětice taková, že každá čtveřice z pětice má barvu 1 NEBO
• existuje t-tice taková, že každá čtveřize z t-tice má barvu 2.

První případ se nemůže stát, je to přímá negace Happy-ending problému. Takže určitě existuje nějaká t-tice $A_{2}$, ve které $\forall X \in \left ( \begin{matrix} A_{2} \\ 4 \end{matrix} \right ) : c \left ( X \right ) = 2$. Vezměme konvexní obal této $A_{2}$. Pokud má t vrcholů, tak jsme vyhráli. Pokud má měné než t vrcholů, tak existuje nějaký vrchol $z$, co je uvnitř. To znamená že existují nějaké body $x_{1} , x_{2} , x_{3}$ které tvoří trojúhelník ve kterém je $z$ uzavřeno.

Tato čtveřice bodů ale netvoří čtyřúhelník, což je spor, protože mají barvu 2.