Problem done/OMJ/XXI/21.1.1.tex

% NumberTheory, DiophantineEquations, Integers

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

\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}{XXI OMJ, etap 1, zadanie 1}

\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}
Jaś ma monety o łącznej wartości równej dokładnie 100 złotych, przy czym każda z tych
monet jest dwuzłotówką albo pięciozłotówką. Wykaż, że Jaś może spośród tych monet wybrać
takie, których łączna wartość jest równa dokładnie 50 złotych.
\bigskip

\noindent\textbf{Solution:}

Oznaczmy, że Jaś ma $a$ monet dwuzłotowych i $b$ monet pięciozłotowych, przy czym
$$a,b\in\mathbb{Z}_{\geq 0}$$

Z treści zadania wynika, że musi być spełnione następujące równanie:

\begin{equation}
    \label{eq1}
    100 = 2a + 5b
\end{equation}

Rozważmy dwa przypadki ze względu na parzystość $b$.

\textbf{Przypadek 1. } $b$ nieparzyste. Zapiszmy $b$ jako: $b=2k+1$, gdzie $k\in\mathbb{Z}_{\geq 0}$.

Podstawmy tę wartość $b$ do równania \eqref{eq1}:

\begin{align*}
    100 &= 2a + 5b \\
    100 &= 2a + 5(2k+1) \\
    100 &= 2a + 10k + 5 \\
    100 - 2a - 10k &= 5 \\
    2(50 - a - 5k) &= 5
\end{align*}

Zauważmy ważną rzecz: wyrażenie po lewej stronie jest parzyste, natomiast wyrażenie po prawej stronie jest nieparzyste. \textbf{Sprzeczność!}

Sprzeczność ta dowodzi, że $b$ \textbf{musi być} parzyste. Dlatego rozważmy przypadek 2.

\textbf{Przypadek 2.} $b$ parzyste.

Skoro $b$ jest parzyste to rozważmy kolejne dwa podprzypadki:

\textbf{Przypadek 2.a} $5b \geq 50$

W tym przypadku, skoro $5b \geq 50$ to gdy weźmiemy tylko monety pięciozłotowe (równe sumą do 50) to otrzymamy 50. Możemy tyle wziąć ze względu na to, że $5b \geq 50$, czyli z założenia tego podprzypadku.

\textbf{Przypadek 2.b} $5b \leq 40$

Zauważmy, że te dwa podprzypadki się uzupełniają, bo skoro $5b$ nie może być równe 50 oraz $b$ jest parzyste to nie może być równe 45 ani nic pomiędzy $41 a 49$.

Skoro tak, to weźmy wszystkie monety pięciozłotowe, a następnie uzupełnijmy sumę do 50 monetami dwuzłotowymi. Zauważmy, że to nam wystarczy, gdyż z założenia zadania mamy, że
$$100=2a+5b$$

Skoro tak, to na pewno nam wystarczy monet dwuzłotowych, a skoro $b$ jest parzyste to po wzięciu wszystkich monet pięciozłotowych suma będzie parzysta, więc trzeba ją będzie uzupełnić o parzystą liczbę, a wzięcie iluś tam monet dwuzłotowych zawsze da parzystą sumę.

Podsumowując, rozważenie wszystkich przypadków jednoznacznie dowodzi, że spośród monet dwuzłotowych i pięciozłotowych sumujących się do stu złotych można wybrać takie, których łączna wartość jest równa dokładnie pięćdziesiąt złotych. Co należało dowieść.


\end{document}