Problem done/OMJ/I/1.1.3.tex

% Geometry, MeasureTheory

\documentclass[a4paper,12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{fancyhdr}
\usepackage{lastpage}
% \usepackage{polski}
\usepackage{graphicx}
\usepackage{float}
\usepackage{fontspec}
\usepackage{enumitem}
\usepackage{unicode-math}
\usepackage[most]{tcolorbox}

\setmainfont{Linux Libertine O}
\newfontfamily\russianfont{Linux Libertine O}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]

% dowod, proof
\newtcolorbox{redbox}[1]{
    breakable,
    enhanced jigsaw,
    colback=red!5!white,
    colframe=red!50!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% lemat, lemma
\newtcolorbox{greenbox}[1]{
    breakable,
    enhanced jigsaw,
    colback=green!5!white,
    colframe=green!50!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% twierdzonko, theorem
\newtcolorbox{bluebox}[1]{
    breakable,
    enhanced jigsaw,
    colback=blue!5!white,
    colframe=blue!50!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% zasada, rule 
\newtcolorbox{yellowbox}[1]{
    breakable,
    enhanced jigsaw,
    colback=yellow!5!white,
    colframe=yellow!70!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% Fakcik, fact
\newtcolorbox{purplebox}[1]{
    breakable,
    enhanced jigsaw,
    colback=purple!5!white,
    colframe=purple!90!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% algorithm
\newtcolorbox{orangebox}[1]{
    breakable,
    enhanced jigsaw,
    colback=orange!5!white,
    colframe=orange!70!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

\usepackage[left=2cm, top=2cm, right=2cm, bottom=1cm, includeheadfoot,
    headheight=50pt, a4paper]{geometry}

\newcommand{\Name}{Hostek}
\newcommand{\Email}{your.email@example.com}
\newcommand{\ProblemNumber}{I OMG, etap 1, zadanie 3}

\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{\Name \\ \Email}
\fancyhead[C]{\ProblemNumber}
\fancyfoot[C]{\thepage/\pageref{LastPage}}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\begin{document}
\fontsize{15}{15}\selectfont

\section*{Problem Statement}

W kole o promieniu 10 wybrano 99 punktów. Dowieść, że wewnątrz
koła istnieje punkt odległy od każdego z wybranych punktów o więcej
niż 1.

\bigskip

\noindent\textbf{Solution:}

Niech $K$ będzie naszym kołem o promieniu $R = 10$. Bez straty ogólności załóżmy, że 
to koło ma środek w początku układu współrzędnych. Możemy to koło zdefiniować w 
następujący sposób: (naturalna interpretacja zbioru punktów na płaszczyźnie $\mathbb{R}^2$)
$$
K = \left\{(x,y)\in\mathbb{R}^2: x^2 + y^2 \leq R^2\right\}
$$

Pole powierzchni naszego koła jest równe:
$$
|K| = \pi \cdot R^2 = \pi \cdot 10^2 = 100\pi
$$

\vspace{1cm}

Niech zbiór $P = \left\{P_1, P_2, \ldots, P_{99}\right\}$ będzie zbiorem naszych 99 punktów wewnątrz koła $K$.
Zatem mamy spełniony warunek $P_i \in K$ dla każdego $i \in \left\{1,2,\ldots,99\right\}$

Zauważmy, że warunek by jakiś punkt był odległy o co najwyżej $r = 1$ od jakiegoś punktu $P_i$ 
można przedstawić jako, że ten punkt jest wewnątrz koła o środku w punkcie $P_i$ i promieniu $r$.

Przeto, zdefiniujmy dla każdego punktu $P_i$ w zbiorze $P$ koło $D_i$ o środku w punkcie $P_i$ i promieniu równym $r$:
$$
D_i = \left\{X \in \mathbb{R}^2: d(X,P_i) \leq r = 1\right\}
$$ 

gdzie $d(A,B)$ to odległość Euklidesowa między punktami $A$ i $B$.

Zauważmy, że każde koło $D_i$ ma pole równe:
$$
|D_i| = \pi \cdot r^2 = \pi \cdot 1^2 = \pi
$$

Nasz szukany punkt z zadania (oznaczmy go $Y$) nie może należeć do żadnego koła $D_i$. 
Skoro nie może należeć do żadnego koła $D_i$ to innymi słowy punkt $Y$ nie może należeć do sumy zbiorów $D_i$.
Zdefiniujmy tę sumę następująco:
$$
S = \bigcup_{i=1}^{99} D_i
$$ 

Zanim przejdziemy do dalszych rozważań to udowodnijmy poniższy lemacik:
\begin{greenbox}{Nierówność Boole'a}
\begin{lemma}
    \label{lemma-nierownosc-boolea}
    Niech $D = \left\{D_1, D_2, \ldots, D_k\right\}$ będzie zbiorem $k$ skończonych zbiorów w przestrzeni $\mathbb{R}^2$.
    Wtedy jest spełnione:
    $$
    \left|\bigcup_{i=1}^{k} D_i\right| \leq \sum_{i=1}^{k}|D_i|
    $$
\end{lemma}
\end{greenbox}

\begin{redbox}{Dowód lematu \ref{lemma-nierownosc-boolea}}
\begin{proof}
    Ogólnie to można to udowodnić korzystając z indukcji, jednak tutaj zaprezentuję bardziej elegancki sposób.

    Zdefiniujmy nowy zbiór $E$ zbiorów skończonych o rozmiarze równym $k$ (czyli 
    tyle samo co $D$: $|E| = |D|$) następująco:
    \begin{align*}
        E_1 &= D_1, \\
        E_i &= D_i \setminus \left(\bigcup_{j=1}^{i-1} D_j\right) \quad \text{dla } i = 2, \dots, k.
    \end{align*}

    Zauważmy, że w takiej konstrukcji mamy, że wszystkie zbiory w zbiorze $E$ są parami rozłączne: 
    \begin{equation}
    \label{leq1}
    E_i \cap E_j = \emptyset \quad \text{dla } i \neq j
    \end{equation}

    Ponadto, dla każdego $i$, mamy że zbiór $E_i$ jest podzbiorem $D_i$:
    $$
    E_i \subseteq D_i
    $$

    A to z kolei implikuje (ze względu na monotoniczność pola):
    \begin{align*}
    |E_i| &\leq |D_i| \\
    \Rightarrow \sum_{i=1}^{k}|E_i| &\leq \sum_{i=1}^{k}|D_i|
    \end{align*}

    W konstrukcji również jest zagwarantowane, że zbiory ze zbioru $E$ pokrywają ten 
    sam obszar co zbiory ze zbioru $D$ (czyli, że sumy tych zbiorów są równe):
    \begin{align*}
    \bigcup_{i=1}^{k} D_i &= \bigcup_{i=1}^{k} E_i \\
    \left|\bigcup_{i=1}^{k} D_i\right| &= \left|\bigcup_{i=1}^{k} E_i\right|
    \end{align*}

    Korzystając z addytywności dla zbiorów rozłącznych \eqref{leq1} otrzymujemy:
    $$
    \left| \bigcup_{i=1}^{k} E_i \right| = \sum_{i=1}^{k}|E_i|
    $$

    Czyli łącząc powyższe rzeczy otrzymujemy:
    $$
    \left| \bigcup_{i=1}^{k} D_i \right| = \left| \bigcup_{i=1}^{k} E_i \right| = \sum_{i=1}^{k}|E_i| \leq \sum_{i=1}^{k}|D_i|
    $$
\end{proof}
\end{redbox}

Korzystając z lematu \ref{lemma-nierownosc-boolea} otrzymujemy:
$$
|S| = \left| \bigcup_{i=1}^{99} D_i \right| \leq \sum_{i=1}^{99}|D_i|
$$

Czyli podstawiając $|D_i| = \pi$:
$$
|S| \leq 99\pi
$$

Zbiór punktów, które \textbf{nie} spełniają warunku zadania, to część wspólna koła $K$ oraz zbioru $S$. 
Oznaczmy ten zbiór punktów nie spełniających warunku jako $Z$:
$$
Z = K \cap S
$$

Oczywiście pole tego zbioru nie może być większe niż pole zbioru $S$:
$$
|Z| \leq |S| \leq 99\pi
$$

Zatem, nasz szukany punkt $Y$ musi być w kole $K$, ale nie może być w zbiorze $Z$. Czyli ten zbiór możemy oznaczyć jako: $K \setminus Z$. Obliczmy pole tego zbioru:
\begin{align*}
|K \setminus Z| &= |K| - |K \cap Z| \\
&= |K| - |Z|
\end{align*}

Najmniejsza wartość $|K| - |Z|$ jest osiągana, gdy $|Z|$ jest największe (my wyznaczyliśmy górny limit dla $|Z|$: $99\pi$). Więc powyższe ma najmniejszą wartość:
$$
|K| - |Z| = 100\pi - 99\pi = \pi
$$

Skoro zbiór $K \setminus Z$ ma najmniejsze pole równe $\pi$, to w szczególności to oznacza, że ten zbiór nie jest pusty! $(\pi > 0)$

Skoro nasz $Y$ by był dobry (czyli by spełniał warunek zadania) musi należeć do 
zbioru $K \setminus Z$, a powyżej udało nam się wykazać, że ten zbiór \textbf{nie 
jest} pusty, to udało się udowodnić, że taki punkt $Y$ istnieje.

\end{document}