Let $S$ be a finite set. $f$ is a function defined on the subset-group $2^S$ of set $S$. $f$ is called $\textsl{monotonic decreasing}$ if when $X \subseteq Y\subseteq S$, then $f(X) \geq f(Y)$ holds. Prove that: $f(X \cup Y)+f(X \cap Y ) \leq f(X)+ f(Y)$ for $X, Y \subseteq S$ if and only if $g(X)=f(X \cup \{ a \}) - f(X)$ is a $\textsl{monotonic decreasing}$ funnction on the subset-group $2^{S \setminus \{a\}}$ of set $S \setminus \{a\}$ for any $a \in S$.
Problem
Source: China TST 2003
Tags: function, induction, algebra unsolved, algebra
solyaris
29.06.2006 16:30
If I am not mistaken this is extraordinarily easy for a Chinese TST. We have to show: (1) $\forall X,Y \subseteq S: f(X \cup Y) + f(X \cap Y) \le f(X) + f(Y)$ $\Leftrightarrow$ (2) $g_a$ is decreasing for any $a$. For (1) $\Rightarrow$ (2) note that it suffices to show that $g_a(X) \ge g_a(X \cup \{b\})$ for all $a \neq b \in S$, $X \subset S \setminus \{a,b\}$. This however follows directly from (1) applied to the sets $X \cup \{a\}$ and $X \cup \{b\}$. For (2) $\Rightarrow$ (1) we use induction on the number $n$ of elements of $X \cup Y$. If $n = 0$ (1) holds trivially. (1) also is trivial if $X=Y$. So w.l.o.g. there is an $a \in S$ such that $a \in X$, $a \notin Y$. By induction hypothesis (1) holds for the sets $Y$ and $X' : = X \setminus \{a\}$. Hence it suffices to show that $f(X') - f(X' \cup Y) \le f(X) - f(X \cup Y)$. But this is the same as $g_a(X' \cup Y) \le g_a(X')$, which holds by (2).
grupyorum
13.08.2019 00:16
A curious note: Such an $f$ is called a submodular set function, and at the forefront of discrete optimization theory these days.