Problem done/OMJ/XXI/21.1.3.tex

% GraphTheory, Combinatorics

\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}
\usepackage{tikz}
\usetikzlibrary{positioning}

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

\section*{Problem Statement}
Każda z pięciu osób napisała na tablicy, ilu znajomych ma wśród czterech pozostałych osób
(jeżeli osoba $A$ zna osobę $B$, to osoba $B$ zna osobę $A$). Cztery z napisanych liczb są równe 1.
Wyznacz wszystkie możliwe wartości piątej liczby. Odpowiedź uzasadnij.
\bigskip

\noindent\textbf{Solution:}

Zauważmy, że skoro relacje są \textbf{symetryczne}, \textbf{obustronne}, tzn. że gdy $A$ zna $B$, to $B$ zna $A$ upraszczają nam parę spraw.

Bo to oznacza, że gdy osoba zna jedną inną osobę to muszą się znać jednocześnie.

To oznacza, że jeśli osoba $A$ zna osobę $B$ i obie znają dokładnie jedną osobę to musi być, że $B$ zna $A$.

Zdefiniujmy w takim razie pojęcie cyklu. Niech cykl oznacza parę osób, które znają dokładnie jedną osobę i siebie wzajemnie. Przy czym w tę definicję nie wliczamy osoby piątej. (patrz rys. \ref{r1})

\begin{figure}[H]
    \centering
    % Definicja stylu dla węzłów (osób)
    \tikzset{person/.style={circle, draw=blue!80, fill=blue!20, thick, minimum size=25pt}}

    \begin{tikzpicture}
        % Rysujemy dwie osoby
        \node[person] (A) at (0,0) {A};
        \node[person] (B) at (2.5,0) {B};

        % Łączymy je linią (znajomością)
        \draw[thick, <->] (A) -- (B);

        % Dodajemy opis pod spodem (poprawiona składnia)
        \node[text width=7cm, align=center, below=0.5cm of A.south west] (desc1) {
            \textbf{Rysunek 1: Czym jest "cykl"}\\
            Osoby A i B znają tylko siebie nawzajem.
            Każda z nich ma dokładnie jednego znajomego.
        };
    \end{tikzpicture}
    \caption{Ilustracja "cyklu" użytego w rozwiązaniu.}
    \label{r1}
\end{figure}

W takim razie możemy teraz rozważać przypadki kolejnych liczby cykli między tymi czterema osobami.

\textbf{Przypadek 1.} Liczba cykli wynosi 0.

Skoro liczba cykli wynosi 0, to cztery osoby nie mogą znać się między sobą. 

A to oznacza, że wszystkie osoby muszą znać się z osobą piątą. Stąd piąta liczba musi być równa 4. (patrz rys. \ref{r3})

\begin{figure}[H]
    \centering
    % Definicja stylu dla węzłów (osób)
    \tikzset{person/.style={circle, draw=blue!80, fill=blue!20, thick, minimum size=25pt}}

    \begin{tikzpicture}
        % Piąta osoba w centrum
        \node[person] (P5) at (0,0) {P5};
        
        % Pozostałe cztery osoby wokół niej
        \node[person] (A) at (0, 2.5) {A};
        \node[person] (B) at (2.5, 0) {B};
        \node[person] (C) at (0, -2.5) {C};
        \node[person] (D) at (-2.5, 0) {D};
        
        % --- Rysujemy znajomości ---
        \draw[thick, <->] (A) -- (P5);
        \draw[thick, <->] (B) -- (P5);
        \draw[thick, <->] (C) -- (P5);
        \draw[thick, <->] (D) -- (P5);

        % Dodajemy opis pod spodem
        \node[text width=10cm, align=center, below=0.2cm of C] {
            \textbf{Rysunek 2: Przypadek "0 cykli"}\\
            Żadna z osób A, B, C, D nie zna się nawzajem.
            Aby każda z nich miała jednego znajomego, wszystkie muszą znać osobę P5.
            W rezultacie P5 ma \textbf{czterech} znajomych.
        };
    \end{tikzpicture}
    \caption{Wizualizacja przypadku, gdy piąta liczba jest równa 4.}
    \label{r3}
\end{figure}

\textbf{Przypadek 2.} Liczba cykli wynosi 1.

W takim razie jedna para osób z naszej czwórki zna się wzajemnie. 

Pozostałe więc muszą się znać z piątą, czyli piąta liczba jest równa 2. (patrz rys. \ref{r2})

\begin{figure}[H]
    \centering
    % Ten styl już jest zdefiniowany, ale dla pewności zostawiam
    \tikzset{person/.style={circle, draw=blue!80, fill=blue!20, thick, minimum size=25pt}}
    
    \begin{tikzpicture}
        % Osoby z "cyklu" po lewej stronie
        \node[person] (A) at (-3, 1) {A};
        \node[person] (B) at (-3, -1) {B};
        
        % Piąta osoba w centrum
        \node[person] (P5) at (0,0) {P5};
        
        % Pozostałe dwie osoby po prawej
        \node[person] (C) at (3, 1) {C};
        \node[person] (D) at (3, -1) {D};
        
        % --- Rysujemy znajomości ---
        
        % Znajomość w ramach "cyklu" (kolor czerwony dla wyróżnienia)
        \draw[thick, <->, red] (A) -- (B) node[midway, left, red, font=\small] {1 cykl};
        
        % Znajomości z piątą osobą
        \draw[thick, <->] (C) -- (P5);
        \draw[thick, <->] (D) -- (P5);

        % Dodajemy opis pod spodem (poprawiona składnia)
        \node[text width=10cm, align=center, below=1cm of P5] {
            \textbf{Rysunek 3: Przykład dla jednego "cyklu"}\\
            Osoby A i B tworzą parę. Osoby C i D, aby mieć jednego znajomego,
            muszą znać osobę P5. W rezultacie P5 ma \textbf{dwóch} znajomych.
        };
    \end{tikzpicture}
    \caption{Wizualizacja przypadku, gdy piąta liczba jest równa 2.}
    \label{r2}
\end{figure}

\textbf{Przypadek 3.} Liczba cykli wynosi 2.

Skoro tak, to osoba piąta nie może znać żadnej z czwórki osób, ponieważ te osoby znają się między sobą. Więc piąta liczba to 0. (patrz rys. \ref{r4})

\begin{figure}[H]
    \centering
    % Styl już zdefiniowany
    \tikzset{person/.style={circle, draw=blue!80, fill=blue!20, thick, minimum size=25pt}}
    
    \begin{tikzpicture}
        % Pierwsza para ("cykl") po lewej
        \node[person] (A) at (-3, 1) {A};
        \node[person] (B) at (-3, -1) {B};
        
        % Druga para ("cykl") po prawej
        \node[person] (C) at (3, 1) {C};
        \node[person] (D) at (3, -1) {D};

        % Piąta osoba na uboczu, na dole
        \node[person] (P5) at (0,-2.5) {P5};
        
        % --- Rysujemy znajomości ---
        \draw[thick, <->, red] (A) -- (B) node[midway, left, red, font=\small] {1 cykl};
        \draw[thick, <->, red] (C) -- (D) node[midway, right, red, font=\small] {2 cykl};
        
        % Dodajemy opis pod spodem
        \node[text width=10cm, align=center, below=0.2cm of P5] {
            \textbf{Rysunek 4: Przypadek "2 cykli"}\\
            Osoby A i B tworzą jedną parę, a C i D drugą.
            Warunek posiadania jednego znajomego jest spełniony dla całej czwórki.
            Osoba P5 nie zna nikogo. W rezultacie P5 ma \textbf{zero} znajomych.
        };
    \end{tikzpicture}
    \caption{Wizualizacja przypadku, gdy piąta liczba jest równa 0.}
    \label{r4}
\end{figure}

Podsumowując, rozważywszy wszystkie przypadki dochodzimy do konkluzji, że piątą liczbą może być jedynie 0, 2 albo 4.

\textbf{Odpowiedź: } Wartość piątej liczby wynosi 0, 2 albo 4.

\end{document}