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}

Zauważmy, że teza w zadaniu jest szczególnym przypadkiem powyższego twierdzenia dla $k = 3$.

Obie strony nierówności są niezmiennicze względem przesunięcia, dlatego możemy założyć, że najmniejszym elementem każdego $A_i$ jest 0. Ponadto oznaczmy największy element $A_i$ przez $a_i$. Wtedy $S$ jest podzbiorem przedziału $[0, a_1+a_2+\dots + a_k].$

Utwórzmy $k-1$ kopii zbioru $S$. W pierwszej kopii zaznaczmy elementy
$0+A_1+\dots +A_{k-1}$. Wszystkie one należą do przedziału $[0,
a_1+\dots +a_{k-1}].$ W pozostałym przedziale $(a_1+\dots
+a_{k-1}, a_1+\dots +a_{k-1}+a_k]$ pierwszej kopii $S$ zaznaczmy elementy $a_{k-1}+A_1+A_2+\dots +A_{k-2}+A_k$, które się w nim znajdują. Elementy te odpowiadają dokładnie elementom $A_1+A_2+\dots +A_{k-2}+A_k$, które są większe od $a_1+\dots +a_{k-2}$. Ten ostatni zbiór oznaczamy przez $(A_1+A_2+\dots +A_{k-2}+A_k)_{>a_1+\dots +a_{k-2}}$.

Następnie, dla $2\leq i \leq k-2,$ w $i$-tej kopii $S$ zaznaczmy elementy
$0+(A_1+A_2+\dots +A_{k-i}+A_{k-i+2}+\dots +A_k)_{\leq a_1+\dots
+a_{k-i}}$, oraz elementy
$a_{k-i}+(A_1+\dots
+A_{k-i-1}+A_{k-i+1}+\dots +A_k)_{>a_1+\dots a_{k-i-1}}.$ Na koniec, w $(k-1)$-szej kopii $S$ zaznaczmy elementy $0+(A_1+A_3+\dots
+A_k)_{\leq a_1}$ oraz elementy $a_1+(A_2+\dots
+A_k)_{>a_1}.$

Zauważmy, że wszystkie zaznaczone elementy należą do $S'$. Ponadto, dla $1\leq i\leq k-2$ liczba zaznaczonych elementów w drugiej części $i$-tej kopii i pierwszej części $(i+1)$-szej kopii $S$ wynosi dokładnie $|A_1+\dots +A_{k-i-1}+A_{k-i+1}+\dots +A_k|$.
Co więcej, liczba zaznaczonych elementów w pierwszej części pierwszej kopii wynosi $|A_1+\dots +A_{k-1}|$, podczas gdy w drugiej części ostatniej kopii wynosi $|A_2+A_3+\dots +A_k|-1$. Niech $M$ oznacza zbiór zaznaczonych elementów. Wówczas, na mocy konstrukcji,
\begin{equation} \label{m}(k-1)|S|\geq (k-1)|S'|\geq |M|= \sum _{i=1}^k \left|S_i
\right|-1\end{equation} co kończy dowód.

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}