Problem OM 78.P.5

% Geometry, Stereometry, Polyhedra, GraphTheory, Combinatorics

\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{tikz}
\usetikzlibrary{calc,shapes.geometric}

\usepackage{xcolor}
\definecolor{polyblue}{RGB}{30, 100, 180}
\definecolor{polyred}{RGB}{200, 40, 40}
\definecolor{polygreen}{RGB}{40, 140, 60}
\definecolor{polyplane}{RGB}{70, 130, 180}

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

\setmainfont{Linux Libertine O}

\newtheorem{theorem}{Twierdzenie}[section]
\newtheorem{lemma}{Lemat}[section]

\newcommand{\Name}{Hostek}
\newcommand{\Email}{your.email@example.com}
\newcommand{\ProblemNumber}{LXXVIII OM, etap 1, zadanie p5}

\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*{Treść zadania}

Dany jest wielościan wypukły $\mathcal{W}$. Załóżmy, że każdy wierzchołek wielościanu $\mathcal{W}$ jest wierzchołkiem parzystej liczby ścian. Płaszczyzna $\Pi$ przecina wnętrze wielościanu $\mathcal{W}$ i nie przechodzi przez żaden z jego wierzchołków. Przecięcie płaszczyzny $\Pi$ i wielościanu $\mathcal{W}$ jest pewnym wielokątem. Wykazać, że ten wielokąt ma parzyście wiele boków.

\bigskip

\section*{Rozwiązanie}

Niech $V$ oznacza zbiór wierzchołków wielościanu $\mathcal{W}$, a $E$ zbiór jego krawędzi. Parę $G = (V, E)$ traktujemy jako graf krawędziowy wielościanu.

\paragraph{Krok 1: Stopnie wierzchołków.}
Wybierzmy dowolny wierzchołek $v \in V$. Wielościan $\mathcal{W}$ jest wypukły, zatem wokół wierzchołka $v$ krawędzie i ściany tworzą naprzemienny cykl: każda ściana stykająca się z $v$ leży pomiędzy dwiema krawędziami wychodzącymi z $v$, a każda krawędź o końcu w $v$ rozdziela dokładnie dwie ściany o wierzchołku $v$. 

Wynika stąd, że liczba krawędzi wychodzących z wierzchołka $v$ (czyli jego stopień $\deg(v)$ w grafie $G$) jest dokładnie równa liczbie ścian zbiegających się w $v$. Z założenia zadania wynika więc, że:
\[
\deg(v) \equiv 0 \pmod 2 \quad \text{dla każdego } v \in V.
\]

\paragraph{Krok 2: Podział wierzchołków przez płaszczyznę $\Pi$.}
Płaszczyzna $\Pi$ nie przechodzi przez żaden wierzchołek wielościanu i dzieli przestrzeń $\mathbb{R}^3$ na dwie otwarte półprzestrzenie $\Pi^+$ i $\Pi^-$. Dzieli to zbiór wierzchołków $V$ na dwa rozłączne podzbiory:
\[
X = V \cap \Pi^+ \quad \text{oraz} \quad Y = V \cap \Pi^-.
\]
Ponieważ płaszczyzna $\Pi$ przecina wnętrze $\mathcal{W}$, oba zbiory $X$ i $Y$ są niepuste.

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=1.1, line join=round, line cap=round]
    \coordinate (T) at (0, 3.0);       
    \coordinate (S) at (0, -2.8);      
    \coordinate (A) at (-2.6, -0.6);   
    \coordinate (B) at (0.6, -1.2);    
    \coordinate (C) at (2.4, 0.4);     
    \coordinate (D) at (-0.8, 1.0);    

    \coordinate (P1) at ($(T)!0.52!(A)$);
    \coordinate (P2) at ($(T)!0.52!(B)$);
    \coordinate (P3) at ($(T)!0.52!(C)$);
    \coordinate (P4) at ($(T)!0.52!(D)$);

    \draw[thick, dashed, gray!70] (D) -- (S);
    \draw[thick, dashed, gray!70] (A) -- (D);
    \draw[thick, dashed, gray!70] (D) -- (C);
    \draw[thick, dashed, gray!70] (D) -- (P4);
    \draw[thick, polyblue] (P4) -- (T);

    \fill[polyplane, opacity=0.22] (-3.8, 1.9) -- (3.2, 2.5) -- (3.8, 0.3) -- (-3.2, -0.3) -- cycle;
    \draw[polyplane!80!black, dashed] (-3.8, 1.9) -- (3.2, 2.5) -- (3.8, 0.3) -- (-3.2, -0.3) -- cycle;
    \node[polyplane!90!black, font=\bfseries] at (3.2, 2.1) {$\Pi$};

    \fill[orange!35, draw=orange!90!black, line width=1.5pt] (P1) -- (P2) -- (P3) -- (P4) -- cycle;

    \draw[thick, polyblue] (S) -- (A);
    \draw[thick, polyblue] (S) -- (B);
    \draw[thick, polyblue] (S) -- (C);
    \draw[thick, polyblue] (A) -- (B);
    \draw[thick, polyblue] (B) -- (C);
    
    \draw[thick, polyblue] (A) -- (P1);
    \draw[thick, polyblue] (P1) -- (T);
    \draw[thick, polyblue] (B) -- (P2);
    \draw[thick, polyblue] (P2) -- (T);
    \draw[thick, polyblue] (C) -- (P3);
    \draw[thick, polyblue] (P3) -- (T);

    \foreach \p in {P1, P2, P3, P4}
        \fill[polyred] (\p) circle (2.2pt);

    \fill[polyblue] (T) circle (2.5pt) node[above=2pt] {$T \in X$};
    \fill[polyblue] (S) circle (2.5pt) node[below=2pt] {$S \in Y$};
    \fill[polyblue] (A) circle (2.5pt) node[left=2pt] {$A$};
    \fill[polyblue] (B) circle (2.5pt) node[below right=1pt] {$B$};
    \fill[polyblue] (C) circle (2.5pt) node[right=2pt] {$C$};
    \fill[polyblue] (D) circle (2.5pt) node[above left=1pt] {$D$};

    \node[orange!90!black, font=\small\bfseries] at (0, 1.1) {Przekrój};
    \node[polyblue, font=\small] at (2.3, -1.8) {Wierzchołki $Y \subset \Pi^-$};
    \node[polyblue, font=\small] at (-1.8, 2.7) {Wierzchołki $X \subset \Pi^+$};
\end{tikzpicture}
\caption{Przekrój przykładowego wielościanu płaszczyzną $\Pi$. Liczba boków wielokąta przekroju odpowiada liczbie przeciętych krawędzi.}
\label{fig:3d}
\end{figure}

\paragraph{Krok 3: Krawędzie przekroju.}
Przekrój $\mathcal{W} \cap \Pi$ jest wielokątem wypukłym $\mathcal{P}$. Boki tego wielokąta powstają w wyniku przecięcia ścian wielościanu płaszczyzną $\Pi$, natomiast wierzchołki wielokąta $\mathcal{P}$ to dokładnie punkty przecięcia krawędzi wielościanu $\mathcal{W}$ z płaszczyzną $\Pi$.

Krawędź $e = \{u, v\} \in E$ przecina płaszczyznę $\Pi$ wtedy i tylko wtedy, gdy jeden z jej końców leży w $X$, a drugi w $Y$. Oznaczmy zbiór takich krawędzi przez $E(X, Y)$:
\[
E(X, Y) = \bigl\{ \{u, v\} \in E : u \in X,\, v \in Y \bigr\}.
\]
Liczba wierzchołków wielokąta $\mathcal{P}$ wynosi zatem dokładnie $|E(X, Y)|$. Ponieważ w każdym wielokącie liczba boków jest równa liczbie wierzchołków, wystarczy dowieść, że liczba krawędzi $|E(X, Y)|$ jest parzysta.

\paragraph{Krok 4: Zasada podwójnego zliczania.}
Rozważmy sumę stopni w grafie $G$ wszystkich wierzchołków należących do podzbioru $X$:
\[
S = \sum_{v \in X} \deg(v).
\]
Każda krawędź grafu $G$:
\begin{itemize}
    \item łącząca dwa wierzchołki ze zbioru $X$ wnosi do sumy $S$ wkład równy $2$ (jest zliczana przy obu swoich końcach),
    \item łącząca wierzchołek ze zbioru $X$ z wierzchołkiem ze zbioru $Y$ wnosi do sumy $S$ wkład równy $1$ (jest zliczana wyłącznie od strony końca w $X$),
    \item łącząca dwa wierzchołki ze zbioru $Y$ ma wkład równy $0$.
\end{itemize}

Oznaczmy przez $E(X)$ zbiór krawędzi mających oba końce w zbiorze $X$. Wówczas otrzymujemy tożsamość:
\[
\sum_{v \in X} \deg(v) = 2 \cdot |E(X)| + |E(X, Y)|.
\]

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=1.1]
    \draw[thick, fill=polyblue!8, draw=polyblue] (-3.2, 0) ellipse (1.6cm and 2.4cm);
    \node[polyblue, font=\large\bfseries] at (-3.2, 2.7) {$X \subset \Pi^+$};

    \draw[thick, fill=polygreen!8, draw=polygreen] (3.2, 0) ellipse (1.6cm and 2.4cm);
    \node[polygreen!80!black, font=\large\bfseries] at (3.2, 2.7) {$Y \subset \Pi^-$};

    \draw[very thick, dashed, polyplane!80!black] (0, -2.7) -- (0, 2.7);
    \node[polyplane!90!black, font=\bfseries] at (0.3, 2.7) {$\Pi$};

    \coordinate (x1) at (-3.2, 1.3);
    \coordinate (x2) at (-2.5, -0.2);
    \coordinate (x3) at (-3.7, -1.1);

    \coordinate (y1) at (2.6, 1.2);
    \coordinate (y2) at (3.8, 0.2);
    \coordinate (y3) at (2.5, -0.6);
    \coordinate (y4) at (3.4, -1.5);

    \draw[thick, polyblue] (x1) -- (x2);
    \draw[thick, polyblue] (x2) -- (x3);
    \draw[thick, polyblue] (x1) -- (x3);

    \draw[thick, polygreen!70!black] (y1) -- (y2);
    \draw[thick, polygreen!70!black] (y3) -- (y4);
    \draw[thick, polygreen!70!black] (y1) -- (y3);

    \draw[thick, polyred] (x1) -- (y1);
    \draw[thick, polyred] (x1) -- (y2);
    \draw[thick, polyred] (x2) -- (y3);
    \draw[thick, polyred] (x3) -- (y4);

    \coordinate (int1) at ($(x1)!0.5517!(y1)$);
    \coordinate (int2) at ($(x1)!0.4571!(y2)$);
    \coordinate (int3) at ($(x2)!0.5000!(y3)$);
    \coordinate (int4) at ($(x3)!0.5211!(y4)$);

    \fill[polyred] (int1) circle (2.8pt);
    \fill[polyred] (int2) circle (2.8pt);
    \fill[polyred] (int3) circle (2.8pt);
    \fill[polyred] (int4) circle (2.8pt);

    \foreach \pt in {x1, x2, x3}
        \fill[polyblue] (\pt) circle (2.5pt);
    \foreach \pt in {y1, y2, y3, y4}
        \fill[polygreen!70!black] (\pt) circle (2.5pt);

    \node[align=center, font=\small, polyblue] at (-3.2, -3.1) {Krawędzie wewnątrz $X$\\zliczane podwójnie ($2|E(X)|$)};
    \node[align=center, font=\small, polyred] at (0, -3.8) {Cięcie $E(X,Y)$\\(wierzchołki przekroju)};
    \node[align=center, font=\small, polygreen!70!black] at (3.2, -3.1) {Krawędzie wewnątrz $Y$\\niewliczane do sumy};
\end{tikzpicture}
\caption{Interpretacja teoriografowa: zliczanie krawędzi o końcach w zbiorze $X$. Każda krawędź przekraczająca prostą $\Pi$ wyznacza jeden wierzchołek przekroju.}
\label{fig:graph}
\end{figure}

Przekształcając powyższą tożsamość, otrzymujemy:
\[
|E(X, Y)| = \sum_{v \in X} \deg(v) - 2 \cdot |E(X)|.
\]
Ponieważ z założenia dla każdego $v \in X$ liczba $\deg(v)$ jest parzysta, suma $\sum_{v \in X} \deg(v)$ jest parzysta jako suma liczb parzystych. Liczba $2 \cdot |E(X)|$ jest w oczywisty sposób parzysta. 

Różnica dwóch liczb parzystych jest liczbą parzystą, a zatem:
\[
|E(X, Y)| \equiv 0 \pmod 2.
\]
Liczba wierzchołków wielokąta przekroju jest parzysta, skąd natychmiast wynika, że wielokąt ten ma parzyście wiele boków, co należało wykazać. \qed

\end{document}