Problem done/OMJ/I/1.2.2.tex

% Combinatorics, Integers, PigeonholePrinciple, Erdős–Ginzburg–Ziv

\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[most]{tcolorbox}
\usepackage{hyperref}

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

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

\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 2, zadanie 2}

\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}

Danych jest 111 dodatnich liczb całkowitych. Wykaż, że spośród nich można wybrać 11 takich liczb, których suma jest podzielna przez 11

\bigskip

\noindent\textbf{Solution:}

\boxed{
    \textbf{Sposób 1:}
}

\begin{proof}[Dowód]
Rozważmy następujące przypadki:

\begin{enumerate}[label=\textbf{Przypadek \arabic*.}, leftmargin=*]
    \item \textbf{Istnieje reszta modulo 11 występująca co najmniej 11 razy}\\
    Jeśli któraś z reszt $0,1,\ldots,10$ występuje dla co najmniej 11 liczb, to:
    \begin{align*}
        \underbrace{a + a + \cdots + a}_{11 \text{ razy}} &= 11a \\
        &\equiv 0 \pmod{11}
    \end{align*}
    Suma takich liczb jest podzielna przez 11.

    \item \textbf{Każda reszta występuje co najwyżej 10 razy}\\
    Załóżmy nie wprost, że żadna reszta nie występuje 11 razy. Wtedy maksymalna liczba elementów:
    \begin{align*}
        11 \text{ reszt} \times 10 \text{ elementów/resztę} &= 110 \text{ elementów}
    \end{align*}
    Jednak mamy 111 liczb, co daje sprzeczność z założeniem.
\end{enumerate}

\vspace{0.5cm}
\noindent
Zasada szufladkowa Dirichleta wymusza prawdziwość pierwszego przypadku.\\

\noindent
$\therefore$ Zawsze istnieje 11 liczb o sumie podzielnej przez 11.
\end{proof}

\boxed{
    \textbf{Sposób 2:}\text{ (Erdős–Ginzburg–Ziv, zaawansowany)}
}

Twierdzenie Erdős–Ginzburg–Ziv mówi, że dla liczby $n$ zbiór $2n-1$ liczb całkowitych zawiera podzbiór o rozmiarze $n$, w którym suma jego elementów jest podzielna przez $n$. \cite{alon-egz1}

W naszym przypadku $n = 11$, co oznacza, że w zbiorze $21$ liczb można wybrać 11 o sumie podzielnej przez 11.

A my mamy $111 > 21$ liczb.

Co kończy dowód.

\begin{thebibliography}{9}

\bibitem{alon-egz1}
Noga Alon and Moshe Dubiner, 
\textit{Zero-sum sets of prescribed size}, 
\url{https://www.tau.ac.il/~nogaa/PDFS/egz1.pdf}

\end{thebibliography}

\end{document}