Problem done/OMJ/I/1.1.6.tex

\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}{I OMG, etap 1, zadanie 6}

\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}{18}\selectfont

\section*{Problem Statement}

Wiadomo, że prawdziwa moneta waży 10 gramów, a fałszywa
9 gramów. Mamy 5 monet o łącznej wadze 48 gramów i dysponujemy wagą elektroniczną. Wykonując ważenie możemy położyć ma wagę
dowolną liczbę wybranych przez nas monet i odczytać ich łączną wagę. Czy wykonując nie więcej niż 3 ważenia możemy zawsze rozpoznać,
które z danych monet są fałszywe, a które prawdziwe?

\bigskip

\noindent\textbf{Solution:}

Odpowiedź: \textbf{Tak, da się!}. Poniżej przedstawiam jedną z możliwości (czyli 
dowodzik konstrukcyjny):

Zauważmy najpierw jedną rzecz: skoro prawdziwa moneta waży 10 gramów a fałszywa 9 
gramów, to skoro mamy łączą wagę 48 gramów to mamy dokładnie trzy prawdziwe monety 
i dwie fałszywe.

Ponumerujmy nasze monety od 1 do 5 i oznaczmy je kolejno: $x_1, x_2, x_3, x_4, x_5$.

Pierwsze ważenie jakie robimy to zawsze monety $x_1, x_2, x_3$. Mamy trzy przypadki:

\begin{enumerate}
    \item Jeśli waga zwróci wynik 30, to znaczy, że wszystkie trzy pierwsze monety 
    są prawdziwe, zatem dwie nieprawdziwe monety to muszą być $x_4$ i $x_5$.
    \item Jeśli waga zwróci wynik 28, to znaczy, że wśród pierwszych naszych 
    trzech monet są dwie fałszywe. W tej wersji robimy dwa dodatkowe ważenia: 
    $x_1$ i $x_2$ (obie monety osobno).

    Jeśli obie $x_1$ i $x_2$ zwrócą wartość 9 to wiemy, że są fałszywe. Jeśli 
    tylko jedna z nich to weź tą co zwróciła wartość 9 oraz monetę $x_3$. (Skoro 
    wśród trzech są dwie fałszywe a jedna zwróciła 10 druga 9 to trzecia musi mieć 
    wartość 9)

    \item Jeśli waga zwróci wynik 29, to znaczy, że wśród pierwszych trzech monet 
    jest jedna fałszywa i wśród dwóch ostatnich jest jedna fałszywa moneta. 
    Wykonujemy wtedy następujące ważenia: $x_1, x_4$ oraz ważenie $x_2, x_4$. 
    Ważenie $x_1, x_4$ oznaczmy numerem 1, a ważenie $x_2, x_4$ numerem dwa.

    Poniżej tabela przedstawiająca każdą możliwość: (skoro ważymy dwa elementy to 
    waga wskaże zawsze albo 18 albo 19 albo 20)

    (kolumny to wartości pierwszego ważenia; Z oznacza, że możliwość jest 
    sprzeczna, czyli nigdy się nie pojawi)

    \begin{tabular}{|c|c|c|c|}
    \hline
    \textbf{2 / 1} & \textbf{20} & \textbf{19} & \textbf{18} \\ \hline
    \textbf{20} & $x_3, x_5$ & $x_1, x_5$ & Z \\ \hline
    \textbf{19} & $x_2, x_5$ & $x_3, x_4$ & $x_1, x_4$ \\ \hline
    \textbf{18} & Z & $x_2, x_4$ & Z \\ \hline
    \end{tabular}
\end{enumerate}

Co kończy dowód \qed

\textbf{Wyjaśnienie wartości w tabeli}

\begin{itemize}
    \item Jeśli pierwsze ważenie daje wynik 20 to znaczy, że monety $x_1$ i $x_4$ 
    są na pewno dobre.
    \begin{itemize}
        \item Jeśli druga zwróci wynik 20, to mamy, że monety $x_1, x_2$ i $x_4$ 
        są na pewno dobre. A skoro jedna w $x_1, x_2, x_3$ jest fałszywa, to musi 
        to być $x_3$. Tak samo, skoro jedna w $x_4, x_5$ jest fałszywa, to musi to 
        być $x_5$.
        \item Jeśli druga zwróci wynik 19, to mamy, że moneta $x_2$ musi być 
        fałszywa (z pierwszego ważenia wiemy, że $x_4$ jest dobra). Tak samo, 
        skoro $x_4$ jest dobra to $x_5$ jest fałszywa. 
        \item Nie może być, że druga zwróci 18, bo z pierwszego wiemy, że $x_4$ 
        jest dobra, a w takiej konfiguracji wyszłoby, że jest zła. Nie może być 
        moneta jednocześnie prawdziwa i fałszywa (jest to nielogiczne).
    \end{itemize}
    \item Jeśli pierwsze ważenie daje wynik 19, to znaczy, że wśród monet $x_1, x_4$ jest jedna fałszywa.
    \begin{itemize}
        \item Jeśli druga zwróci 20, to wiemy, że moneta $x_4$ jest prawdziwa, a 
        $x_1$ musi być fałszywa. Czyli po prostu $x_1, x_5$.
        \item Jeśli druga zwróci 19, to wiemy, że moneta $x_4$ jest fałszywa 
        (ponieważ wiemy, że monety $x_1$ i $x_2$ nie mogą być jednocześnie 
        fałszywe). Drugą fałszywą monetą jest $x_3$ (skoro $x_4$ jest fałszywa to 
        stąd wynika, że monety $x_1$ i $x_2$ są prawdziwe)
        \item Jeśli druga zwróci 18, to wiemy, że moneta $x_4$ jest fałszywa oraz, 
        że moneta $x_2$ jest fałszywa.
    \end{itemize}
    \item Jeśli pierwsze ważenie daje wynik 18, to znaczy, że monety $x_1, x_4$ są fałszywe.
\end{itemize}

\textbf{Zabawny fakcik:} W treści zadania jest literówka!

\end{document}