Problem done/OMJ/demo/omj.demo.6.tex

\fontsize{15}{15}\selectfont

Problem Statement

W pewnej grupie składającej się z sześciu osób każdy lubi dokładnie trzy inne osoby, przy czym jeśli osoba $A$ lubi osobę $B$, to niekoniecznie $B$ lubi $A$. Rozstrzygnij, czy wynika z tego, że pewne dwie osoby wzajemnie się lubią.

Solution:

Rozpatrzmy relację lubienia jako skierowaną – jeśli osoba $A$ lubi osobę $B$, to rysujemy skierowaną krawędź z $A$ do $B$.

Ponieważ mamy $6$ osób, a każda z nich lubi dokładnie $3$ inne osoby, to łączna liczba skierowanych krawędzi wynosi: \[ 6 \cdot 3 = 18. \]

Potencjalne wzajemne relacje (czyli takie, że $A$ lubi $B$ i $B$ lubi $A$) odpowiadają parom osób $(A, B)$, dla których istnieją obie skierowane krawędzie między $A$ i $B$. Taka para tworzy więc cykl długości $2$ w grafie skierowanym.

Zauważmy, że wśród $6$ osób istnieje dokładnie $\binom{6}{2} = 15$ różnych par osób. Dla każdej takiej pary $(A,B)$ mogą istnieć:

żadna relacja (nikt nikogo nie lubi),
relacja jednostronna (np. $A$ lubi $B$, ale nie odwrotnie),
relacja dwustronna (wzajemne lubienie się).

Żeby nie istniaja relacja dwustronna to każda para może mieć przypisany jeden rodzaj krawędzi skierowaniej (albo z $A$ do $B$, albo z $B$ do $A$). Skoro w sumie mamy $18$ skierowanych krawędzi, a tylko $15$ par, to liczba skierowanych krawędzi przekracza liczbę par.

\medskip

Zastosowanie zasady Dirichleta:

Próbujemy umieścić $18$ skierowanych relacji w $15$ parach. Ponieważ $18 > 15$, to z zasady szufladkowej wynika, że przynajmniej jedna para musi zawierać dwie skierowane relacje – czyli dwie osoby wzajemnie się lubią.

\[ \boxed{\text{Odpowiedź: Tak, istnieje co najmniej jedna para osób, które wzajemnie się lubią.}} \qed \]

% Combinatorics, GraphTheory, PigeonholePrinciple

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

\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}{demo OMJ, 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}{15}\selectfont

\section*{Problem Statement}

W pewnej grupie składającej się z sześciu osób każdy lubi dokładnie trzy inne osoby, przy
czym jeśli osoba $A$ lubi osobę $B$, to niekoniecznie $B$ lubi $A$. Rozstrzygnij, czy wynika z tego,
że pewne dwie osoby wzajemnie się lubią.

\bigskip

\noindent\textbf{Solution:}

Rozpatrzmy relację \emph{lubienia} jako skierowaną – jeśli osoba $A$ lubi osobę $B$, to rysujemy skierowaną krawędź z $A$ do $B$.

Ponieważ mamy $6$ osób, a każda z nich lubi dokładnie $3$ inne osoby, to łączna liczba skierowanych krawędzi wynosi:
\[
6 \cdot 3 = 18.
\]

Potencjalne wzajemne relacje (czyli takie, że $A$ lubi $B$ \emph{i} $B$ lubi $A$) odpowiadają parom osób $(A, B)$, dla których istnieją \emph{obie} skierowane krawędzie między $A$ i $B$. Taka para tworzy więc cykl długości $2$ w grafie skierowanym.

Zauważmy, że wśród $6$ osób istnieje dokładnie $\binom{6}{2} = 15$ różnych par osób. Dla każdej takiej pary $(A,B)$ mogą istnieć:
\begin{itemize}
    \item żadna relacja (nikt nikogo nie lubi),
    \item relacja jednostronna (np. $A$ lubi $B$, ale nie odwrotnie),
    \item relacja dwustronna (wzajemne lubienie się).
\end{itemize}

Żeby nie istniaja relacja dwustronna to każda para może mieć przypisany jeden rodzaj krawędzi skierowaniej (albo z $A$ do $B$, albo z $B$ do $A$). Skoro w sumie mamy $18$ skierowanych krawędzi, a tylko $15$ par, to liczba skierowanych krawędzi przekracza liczbę par.

\medskip

\noindent\textbf{Zastosowanie zasady Dirichleta:}

Próbujemy umieścić $18$ skierowanych relacji w $15$ parach. Ponieważ $18 > 15$, to z zasady szufladkowej wynika, że przynajmniej jedna para musi zawierać \emph{dwie} skierowane relacje – czyli dwie osoby wzajemnie się lubią.

\[
\boxed{\text{Odpowiedź: Tak, istnieje co najmniej jedna para osób, które wzajemnie się lubią.}} \qed
\]

\end{document}