Problem OM 77.1.12

% AdditiveCombinatorics, Combinatorics, SetTheory

\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{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}{LXXVII OM, etap 1, zadanie 12}

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

Przyjmujemy następujące oznaczenie: jeśli $X$ i $Y$ są podzbiorami zbioru
liczb całkowitych, to $X + Y$ oznacza zbiór wszystkich liczb postaci $x+y$, gdzie
$x \in X$ i $y \in Y$ . Przyjmujemy też $X + Y + Z = (X + Y) + Z$.

Dane są niepuste skończone podzbiory $A$, $B$, $C$ zbioru liczb całkowitych.
Wykazać, że
\[
2 \cdot |A + B + C| + 1 \geq |A + B| + |B + C| + |C + A|
\]

\bigskip

\noindent\textbf{Solution:}

\textbf{Sposób 1. (firmówka)}

Zauważmy, że dla dowolnej liczby całkowitej $x$ i dowolnego podzbioru $X$ 
zbioru liczb całkowitych zbiory $X$ i $\left\{x\right\}+X$ mają tyle samo elementów.

Po prostu w tym drugim zbiorze wszystkie elementy są przesunięte o $x$.
Przykład:
\begin{align*}
    X &= \left\{-3, -2, 4, 5, 8, 9\right\}, \quad  \, x = 2 \\
    \left\{x\right\} + X &= \left\{-1, 0, 6, 7, 10, 11\right\}
\end{align*}

Zapiszmy ten fakcik: (dla $X \subset \mathbb{Z}$, $x\in\mathbb{Z}$)
\begin{equation}
    \label{fz1}
    |X| = |X + \left\{x\right\}|
\end{equation}

Załóżmy więc, b.s.o., że
\[
\min A = \min B = \min C = 0
\]

Czyli zamiast zbiorów $A$, $B$, $C$ rozważamy zbiory $\left\{\min A\right\} + A$, $\left\{\min B\right\} + B$, $\left\{\min C\right\} + C$.

Niech $\max A = a$ oraz $\max B = b$.

Rozważmy następujące cztery zbiory:
\begin{align*}
    X_1 &= \left(\left\{a\right\} + B + C\right) \setminus \left\{a\right\} \\
    X_2 &= \left(A + C\right) \cap (-\infty, a] \\
    X_3 &= \left(A + \left\{b\right\} + C\right) \cap \left(a + b, +\infty\right) \\
    X_4 &= A + B
\end{align*}

Zbiór $X_1$ jest zawarty w $A + B + C$, ponieważ $a \in A$.
Zbiór $X_2$ jest zawarty w $A + B + C$, ponieważ $A + C$ jest zawarty w $A + B + C$, a przecież zbiór $B$ zawiera 0 (zgodnie z naszym założeniem).
Zbiór $X_3$ jest zawarty w $A + B + C$, ponieważ $b \in B$.
Zbiór $X_4$ jest zawarty w $A + B + C$, ponieważ $A + B$ jest zawarty w $A + B + C$, a przecież zbiór $C$ zawiera 0 (zgodnie z naszym założeniem).

Zatem, wszystkie te zbiory są zawarte w $A + B + C$.

Zauważmy, że $X_1$ jest zawarty w przedziale $\left(a, +\infty\right)$
(do każdego elementu zbioru $B + C$ dodajemy $\left\{a\right\}$, ale końcowo usuwamy $a$ z tego zbioru).

Ponadto zbiór $X_2$ jest zawarty w przedziale $(-\infty, a]$ (oczywiste).
Stąd wynika, że zbiory $X_1$ i $X_2$ są rozłączne!

Podobnie zbiory $X_3$ i $X_4$ są rozłączne!
Bo $X_3$ zawiera się w przedziale $(a+b,+\infty)$, a $X_4$ w przedziale $(-\infty, a+b]$.

Stąd, skoro te zbiory są rozłączne i oba zawierają się w zbiorze $A + B + C$, to:
\[
|X_3| + |X_4| \leq |A + B + C|
\]

Tak samo:
\[
|X_1| + |X_2| \leq |A + B + C|
\]

Policzmy ile te zbiory $X_1$ i $X_4$ mają elementów:
\begin{align*}
    |X_1| &= |\left(\left\{a\right\} + B + C\right) \setminus \left\{a\right\}|\\
    &= |\left(\left\{a\right\} + B + C\right)| - 1 \\
    &= |B + C| - 1
\end{align*}

Dla zbioru $X_4$ jest to oczywiste:
\[
|X_4| = |A+B|
\]

Teraz pokażę, że zachodzi taka równość:
\begin{equation}
    \label{z1}
    |X_3| = |\left(A + \left\{b\right\} + C\right) \cap \left(a + b, +\infty\right)| = |\left(A + C\right) \cap \left(a, +\infty\right)|
\end{equation}

Niech $Y = A + C$. Wtedy równość \eqref{z1} możemy zapisać jako:
\[
    |\left(Y + \left\{b\right\}\right)\cap \left(a + b, +\infty\right)| = |Y\cap \left(a, +\infty\right)|
\]

Oznaczmy wzór po prawej stronie jako $Z_R = Y\cap \left(a, +\infty\right)$.

Elementy zbioru po lewej stronie $Z_L = \left(Y + \left\{b\right\}\right)\cap \left(a + b, +\infty\right)$,
to liczby postaci $y + b$, gdzie $y \in Y$, które jednocześnie są większe niż $a + b$.

Rozważmy odwzorowanie $f: Z_R \rightarrow \mathbb{Z}$ dane wzorem
\[
f(x) = x + b
\]

Weźmy dowolny $x \in Z_R$. Wtedy $x \in Y$ oraz $x > a$. 

Z tego wynika, że $x + b \in \left(Y + \left\{b\right\}\right)$ oraz $x + b > a + b$. Zatem:
\begin{equation}
\label{e1}
f(x) \in Z_L
\end{equation}

Odwzorowanie to jest różnowartościowe, bo: 
\begin{equation}
    \label{e2}    
    f(x_1) = f(x_2) \Leftrightarrow x_1 + b = x_2 + b \Longrightarrow x_1 = x_2
\end{equation}

To odwzorowanie $f$ jest ponadto "na" zbiór $Z_L$
(każdy element z $Z_L$ ma postać $y+b$ dla pewnego $y$, a skoro $y + b > a + b$, to $y > a$, więc $y \in Z_R$).
Zapiszmy to:
\begin{equation}
    \label{e3}
    f: Z_R \rightarrow Z_L
\end{equation}

Czyli nasze odwzorowanie jest iniekcją \eqref{e2} i jest ponadto surjekcją \eqref{e3}.
Zatem $f$ jest bijekcją! A skoro jest bijekcją, a przecież zbiory $Z_L$ i $Z_R$ są skończone,
to mają tę samą moc!
\begin{align}
    |Z_L| &= |Z_R| \\
    |\left(A + \left\{b\right\} + C\right) \cap \left(a + b, +\infty\right)| &= |\left(A + C\right) \cap \left(a, +\infty\right)|
\end{align}

Zauważmy, że trudno byłoby obliczyć liczność zbioru $X_2$ albo $X_3$.
Ale za to sumę liczności tych zbiorów dość łatwo obliczyć!
\begin{align*}
    |X_2| + |X_3| &= |\left(A + C\right) \cap (-\infty, a]| + |\left(A + \left\{b\right\} + C\right) \cap \left(a + b, +\infty\right)| \\
    &= |\left(A + C\right) \cap (-\infty, a]| + |\left(A + C\right) \cap \left(a, +\infty\right)| \\
    &= |A + C|
\end{align*}

Wydaje się to intuicyjne, ale przypomnijmy fakcik:
\begin{lemma}
    Dla $D \subset \mathbb{Z}$ oraz $E_1 \subset \mathbb{Z}$ i $E_2 \subset \mathbb{Z}$,
    przy czym $E = E_1 \cup E_2$, zachodzi:
    \[
        \left(D \cap E_1\right) \cup \left(D \cap E_2\right) = D \cap E
    \]
    W szczególności, gdy $E = \mathbb{Z}$ dostaniemy:
    \[
        D \cap E = D
    \]
\end{lemma}

Chyba jest to fakcik oczywisty, ale wydaje mi się, że warto go było rozpisać. 
Można go łatwo uogólnić, ale nie ma potrzeby w tym zadaniu.

Otóż, zapiszmy raz jeszcze co uzyskaliśmy do tej pory:
\begin{align}
    |X_1| + |X_2| &\leq |A + B + C| \label{l1} \\
    |X_3| + |X_4| &\leq |A + B + C| \label{l2} \\
    |X_1| &= |B + C| - 1 \label{l3} \\
    |X_2| + |X_3| &= |A + C| \label{l4} \\
    |X_4| &= |A + B| \label{l5}
\end{align}

Z \eqref{l1} i \eqref{l2} dostaniemy takie coś:
\begin{equation}
    \label{l6}
    2 |A + B + C| \geq |X_1| + |X_2| + |X_3| + |X_4|
\end{equation}

Aby dostać sumę tych czterech zbiorów korzystamy z \eqref{l3}, \eqref{l4} i \eqref{l5}:
\begin{equation}
    \label{l7}
    |X_1| + |X_2| + |X_3| + |X_4| = |A + B| + |A + C| + |B + C| - 1
\end{equation}

Łącząc \eqref{l6} i \eqref{l7}:
\begin{align*}
    2 |A + B + C| &\geq |A + B| + |A + C| + |B + C| - 1 \\
    2 |A + B + C| + 1 &\geq |A + B| + |A + C| + |B + C| \\
\end{align*}

Co należało dowieść. \qed

\textbf{Sposób 2. (papierek)}

Spróbujmy udowodnić to twierdzonko:

\begin{theorem}  
\label{superadd}
Niech $A_1, \dots , A_k$ będą skończonymi, niepustymi zbiorami liczb całkowitych. Niech $A_i'$ będzie dwu- (lub ewentualnie jedno-) elementowym zbiorem zawierającym najmniejszy i największy element zbioru $A_i$. Przyjmijmy
\[   S = A_1 + \dots  + A_k ,  \]
\[   S_i = A_1 + \dots  + A_{i-1} + A_{i+1}+ \dots  + A_k ,  \]
\[   S_i' = A_1 + \dots  + A_{i-1} + A_i' + A_{i+1}+ \dots  + A_k , \]
\[   S' = \bigcup _{i=1}^k S_i' .  \]
Wtedy zachodzi
\begin{equation}
\left| S \right| \geq  \left|S' \right| \geq  {1\over k-1} \sum _{i=1}^k \left|S_i \right|
- {1\over k-1}.
\end{equation}
\end{theorem}

\begin{proof}
\textbf{Krok 1: Redukcja problemu i uproszczenie notacji} \\
Ponieważ obie strony dowodzonej nierówności są niezmiennicze ze względu na przesunięcia (translacje) zbiorów, możemy bez straty ogólności założyć, że najmniejszym elementem każdego zbioru $A_i$ jest $0$. 

Niech $a_i = \max(A_i)$ będzie największym elementem zbioru $A_i$. Wówczas $A_i' = \{0, a_i\}$. Zauważmy, że $S_i' = (0 + S_i) \cup (a_i + S_i)$, skąd wynika, że dla każdego $i$ zbiory postaci $S_i$ oraz $a_i + S_i$ są podzbiorami $S'$.

Aby uprościć zapis progów, według których będziemy dzielić zbiory, wprowadźmy sumy prefiksowe maksimów:
\[ B_m = \sum_{r=1}^m a_r \quad \text{dla } m = 1, \dots, k, \]
oraz przyjmijmy $B_0 = 0$. Zauważmy, że zbiór $S_j$ zawsze zawiera się w przedziale $[0, B_k - a_j]$.

\textbf{Krok 2: Idea dowodu i konstrukcja zbiorów pomocniczych} \\
Skonstruujemy $k-1$ podzbiorów $M_1, M_2, \dots, M_{k-1}$ zawartych w $S'$. Każdy zbiór $M_j$ będzie sumą dwóch rozłącznych części: „dolnej” ($L_j$) oraz „górnej” ($U_j$), zdefiniowanych poprzez obcięcie odpowiednich zbiorów $S_i$ progiem $B_{k-j}$ lub $B_{k-j-1}$.

Dla $j = 1, 2, \dots, k-1$ definiujemy:
\begin{align*}
L_j &= 0 + (S_{k-j+1})_{\leq B_{k-j}} \\
U_j &= a_{k-j} + (S_{k-j})_{> B_{k-j-1}}
\end{align*}
oraz kładziemy $M_j = L_j \cup U_j$. 
*(Oznaczenie $(X)_{\le p}$ oznacza zbiór elementów zbioru $X$ mniejszych lub równych $p$).*

\textbf{Krok 3: Analiza własności zbiorów $M_j$} \\
Najpierw wykażemy, że $M_j \subseteq S'$. 
Z definicji mamy $L_j \subseteq 0 + S_{k-j+1} \subseteq S_{k-j+1}' \subseteq S'$.
Podobnie $U_j \subseteq a_{k-j} + S_{k-j} \subseteq S_{k-j}' \subseteq S'$. Zatem istotnie $M_j \subseteq S'$, skąd wynika, że $|M_j| \leq |S'|$ dla każdego $j$.

Następnie sprawdzimy, że części $L_j$ i $U_j$ są rozłączne.
Z definicji największy element w $L_j$ jest nie większy niż $B_{k-j}$. 
Z kolei najmniejszy element rozważanej części $(S_{k-j})_{> B_{k-j-1}}$ jest ostro większy niż $B_{k-j-1}$ (czyli wynosi co najmniej $B_{k-j-1} + 1$). Po dodaniu przesunięcia $a_{k-j}$, najmniejszy element w $U_j$ jest większy bądź równy:
\[ B_{k-j-1} + 1 + a_{k-j} = B_{k-j} + 1. \]
Ponieważ $\max(L_j) < \min(U_j)$, zbiory te są ściśle rozłączne, co oznacza, że $|M_j| = |L_j| + |U_j|$.

\textbf{Krok 4: Zliczanie elementów (suma teleskopowa)} \\
Zsumujmy moce wszystkich zbiorów $M_j$:
\[ \sum_{j=1}^{k-1} |M_j| = \sum_{j=1}^{k-1} \left( |L_j| + |U_j| \right). \]
Rozpiszmy tę sumę, grupując wyrażenia inaczej – połączymy „górną” część z kroku $j$ z „dolną” częścią z kroku $j+1$:
\[ |M_1| + \dots + |M_{k-1}| = |L_1| + \sum_{j=1}^{k-2} \Big( |U_j| + |L_{j+1}| \Big) + |U_{k-1}|. \]

Przyjrzyjmy się poszczególnym składnikom tej sumy:
\begin{itemize}
    \item \textbf{Wyraz początkowy $|L_1|$:} Ponieważ $\max(S_k) = B_{k-1}$, warunek $\leq B_{k-1}$ jest spełniony przez wszystkie elementy $S_k$. Zatem $|L_1| = |S_k|$.
    \item \textbf{Pary wewnątrz sumy $(|U_j| + |L_{j+1}|)$:}
    Zauważmy, że $U_j$ to zbiór $S_{k-j}$ ograniczony z dołu progiem $> B_{k-j-1}$ (przesunięcie $a_{k-j}$ nie zmienia mocy zbioru). Z kolei $L_{j+1}$ to ten sam zbiór $S_{k-j}$ ograniczony z góry progiem $\leq B_{k-j-1}$. 
    Zatem ich suma mocy daje dokładnie moc całego zbioru: $|U_j| + |L_{j+1}| = |S_{k-j}|$.
    \item \textbf{Wyraz końcowy $|U_{k-1}|$:}
    Dla $j=k-1$ mamy zbiór $U_{k-1} = a_1 + (S_1)_{> B_0}$. Ponieważ $B_0 = 0$, a najmniejszym elementem $S_1$ jest $0$, warunek $>0$ odrzuca dokładnie jeden element z $S_1$. Zatem $|U_{k-1}| = |S_1| - 1$.
\end{itemize}

Podstawiając te obserwacje do naszego równania, otrzymujemy piękną sumę wszystkich zbiorów $S_i$:
\[ \sum_{j=1}^{k-1} |M_j| = |S_k| + \sum_{j=1}^{k-2} |S_{k-j}| + |S_1| - 1 = \sum_{i=1}^k |S_i| - 1. \]

\textbf{Krok 5: Konkluzja} \\
Wiedząc, że dla każdego z $k-1$ zbiorów zachodzi $|M_j| \leq |S'|$, możemy zapisać:
\[ (k-1)|S'| \geq \sum_{j=1}^{k-1} |M_j| = \sum_{i=1}^k |S_i| - 1. \]
Dzieląc obie strony przez $k-1$, otrzymujemy prawą stronę tezy:
\[ |S'| \geq \frac{1}{k-1} \sum_{i=1}^k |S_i| - \frac{1}{k-1}. \]
Oczywista inkluzja $S' \subseteq S$ gwarantuje, że $|S| \geq |S'|$, co w pełni kończy dowód.
\end{proof}

Podsumowując, udowodnienie twierdzenia \ref{superadd} udowadnia tezę, gdyż jest
ona szczególnym przypadkiem tego twierdzenia dla $k=3$.

Co należało dowieść. \qed

Warto zaznaczyć, że twierdzenie \ref{superadd}, jest twierdzeniem 1.1 z "papierka" dostępnego na arxiv: 0707.2707.

\end{document}