Problem OMJ 22.1.5

% NumberTheory

\documentclass[a4paper,12pt]{article}

\usepackage[left=2cm, top=2cm, right=2cm, bottom=1cm, includeheadfoot,
    headheight=50pt]{geometry}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{float}
\usepackage[most]{tcolorbox}
\usepackage{enumitem}
\usepackage{graphicx}

\usepackage{polyglossia}
\setmainlanguage{polish}

\usepackage{amsmath, amsthm}

\usepackage{fontspec}
\usepackage{unicode-math}

\setmainfont{Linux Libertine O}

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

\newcommand{\Name}{Hostek}
\newcommand{\Email}{your.email@example.com}
\newcommand{\ProblemNumber}{XXII OMJ, etap 1, zadanie 5}

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

\section*{Problem Statement}

W pewnej krainie żyją smoki, a każdy z nich ma dokładnie 1 lub 4 głowy oraz dokładnie
2 lub 5 nóg. Czy możliwe jest, że wszystkie smoki żyjące w tej krainie mają łącznie dokładnie
210 głów i dokładnie 211 nóg? Odpowiedź uzasadnij.

\bigskip

\noindent\textbf{Solution:}

Oznaczmy przez $\lambda$ liczbę smoków. Przez $x \geq 0$ oznaczmy liczbę smoków, które mają jedną głowę. Czyli liczba smoków, które mają cztery głowy jest równa $\lambda - x$.

Podobnie oznaczmy przez $y$ liczbę smoków, które mają dwie nogi. Czyli liczba smoków, które mają pięć nóg jest równa $\lambda - y$.

Zapiszmy zatem dwa równania: pierwsze równanie na łączną liczbę głów
\begin{equation}
    \label{e1}
    210 = x + 4(\lambda - x)
\end{equation}

Drugie równanie na łączną liczbę nóg:
\begin{equation}
    \label{e2}
    211 = 2y + 5(\lambda - y)
\end{equation}

Przekształćmy \eqref{e1}:
\begin{align*}
    210 &= x + 4(\lambda - x) \\
    210 &= x + 4\lambda - 4x \\
    210 &= 4\lambda - 3x \\
    3x &= 4\lambda - 210
\end{align*}

Zapiszmy to równanie:
\begin{equation}
    \label{e3}
    3x = 4\lambda - 210
\end{equation}

Ważny fakcik: skoro operujemy na liczbach całkowitych to skoro po lewej stronie równania \eqref{e3} mamy liczbę podzielną przez 3 to żeby zachodziła równość prawa strona też musi być podzielna przez 3. Rozpiszmy to:
\begin{align*}
    4\lambda - 210 &\equiv 0 \pmod{3} \\
    4\lambda &\equiv 0 \pmod{3} \\
    \lambda &\equiv 0 \pmod{3}
\end{align*}

Otrzymaliśmy taki warunek:
\begin{equation}
    \label{e4}
    \lambda \equiv 0 \pmod{3}
\end{equation}

Zapamiętajmy go. Teraz rozpiszmy równanie \eqref{e2}:
\begin{align*}
    211 &= 2y + 5(\lambda - y) \\
    211 &= 2y + 5\lambda - 5y \\
    211 &= 5\lambda - 3y \\
    3y &= 5\lambda - 211
\end{align*}

Zapiszmy to równanie:
\begin{equation}
    \label{e6}
    3y = 5\lambda - 211
\end{equation}

Analogicznie jak wyżej, skoro to są liczby całkowite to musi być:
\begin{equation}
    \label{e7}
    5\lambda - 211 \equiv 0 \pmod{3}
\end{equation}

Rozpiszmy to:
\begin{align*}
    5\lambda - 211 &\equiv 0 \pmod{3} \\
    2\lambda - 1 &\equiv 0 \pmod{3} \\
    2\lambda &\equiv 1 \pmod{3} \\
    \lambda &\equiv 2 \pmod{3}
\end{align*}

Tu był, być może, trudny do zrozumienia krok: dlaczego $2\lambda \equiv 1 \pmod{3}$ implikuje $\lambda \equiv 2 \pmod{3}$?

Można to udowodnić na kilka sposobów. Tutaj użyję przypadkologii: czyli rozpiszmy wszystkie możliwe reszty z dzielenia $\lambda$ przez 3 (przy okazji zaznaczę tutaj, że z otrzymanego wcześniej warunku \eqref{e4} nie musimy tego dowodzić, bo wystarczy wstawić wartość $\lambda$ uzyskaną w \eqref{e4})
\begin{itemize}
    \item $\lambda \equiv 0 \pmod{3}$: wtedy mamy, że $2\lambda \equiv 0 \pmod{3}$
    \item $\lambda \equiv 1 \pmod{3}$: wtedy mamy, że $2\lambda \equiv 2 \pmod{3}$
    \item $\lambda \equiv 2 \pmod{3}$: wtedy mamy, że $2\lambda \equiv 4 \equiv 1 \pmod{3}$
\end{itemize}

Jak widać z powyższego rozpisania przypadków $2\lambda \equiv 1 \pmod{3}$ implikuje $\lambda \equiv 2 \pmod{3}$.

Powiem jeszcze przy okazji, że powyższe można było wykazać używając małego twierdzenia Fermata, bo 3 i 2 są względnie pierwsze.

Więc otrzymaliśmy:
\begin{equation}
    \label{e8}
    \lambda \equiv 2 \pmod{3}
\end{equation}

Zauważmy, warunki \eqref{e4} i \eqref{e8} są sprzeczne, zatem warunek z zadania jest niemożliwy.

\textbf{Odpowiedź: } Nie jest możliwe, aby wszystkie smoki żyjące w tej krainie miały łącznie dokładnie
210 głów i dokładnie 211 nóg.

\textit{Dodatek: małe twierdzenie Fermata}

Z małego twierdzenia Fermata mamy, że, gdy $a$ jest liczbą względnie pierwszą z $p$ (przy czym $p$ musi być liczbą pierwszą) to: 
\[
    a^{-1} \equiv a^{p - 2} \pmod{p}
\]

Zatem możemy zapisać poniższe używając $p=3$:
\[
    a^{-1} \equiv a^{3 - 2} \pmod{3}
\]

Upraszczając dostajemy:
\[
    a^{-1} \equiv a \pmod{3}
\]

Więc:
\begin{align*}
    2\lambda &\equiv 1 \pmod{3} \\
    \lambda &\equiv 1 \cdot 2^{-1} \pmod{3} \\
    \lambda &\equiv 1 \cdot 2 \pmod{3} \\
    \lambda &\equiv 2 \pmod{3}
\end{align*}

\textit{Dodatek 2:}

Zauważmy, że możemy takie coś zrobić (bo: $2 \equiv -1 \pmod{3}$):
\begin{align*}
    2\lambda &\equiv 1 \pmod{3} \\
    -\lambda &\equiv 1 \pmod{3} \\
    \lambda &\equiv -1 \pmod{3} \\
    \lambda &\equiv 2 \pmod{3}
\end{align*}

\textbf{Drugi sposób: }

Zauważmy, że dostaliśmy dwa warunki:
\[
\begin{cases}
    \lambda &\equiv 0 \pmod{3} \\
    2\lambda &\equiv 1 \pmod{3}
\end{cases}
\]

Wstawmy ten pierwszy do drugiego:
\begin{align*}
    2 \cdot 0 &\equiv 1 \pmod{3} \\
    0 &\equiv 1 \pmod{3}
\end{align*}

Dostaliśmy sprzeczność! To pokazuje, że nie jest możliwe, aby wszystkie smoki żyjące w tej krainie miały łącznie dokładnie
210 głów i dokładnie 211 nóg.

\end{document}