Iranian Mathematical Olympiad

We divide subgroups into three groups

1) Subset $\varnothing$ such that $f(\varnothing )=g(\varnothing )=0$.

2) One element subsets. Of course we know that for an arbitrary element of this group like $X$, $f(X)=0$ and $g(X)=1$. So for one element subsets we have ${\sum }_{|A|=1}(f(A)-g(A))=-n$.

3) Subsets with at least two elements. For subsets in group 3. For integers $1\le i\le j\le n$ let $A_{ij}$ be the collection of such binary strings of length $n$ that the first $1$ lies in the $i$'s place and the last $1$ lies in the $j$'s place. Hence, if $i<j$ and $X=a_1{a}_2\cdots a_n\in A$ then $a_{i+1},\dots ,a_j$ can be $0$ or $1$ so $|A_{ij}|=2^{j-i-1}$. For $a\in \{0,1\}$ let $\bar{a}=1$ if $a=0$ and $\bar{a}=0$ if $a=1$.

For every $X=a_1{a}_2\cdots a_n\in A_{ij}$ we define $\bar{X}=a_1\cdots a_i{\bar{a}}_{i+1}\cdots {\bar{a}}_{j-1}{a}_j\cdots a_n$. (We change the numbers between first and last $1$.) Now we compare $f(\bar{X})$ and $g(X)$. (There is bijection between binary strings of length $n$ and subsets of $\{1,2,...,n\}$ so we can define $f$ and $g$ on binary strings.)

For the largest block of $1$'s in $X$ we have three cases:

Case 1. The largest block contains places $i$ and $j$. So $a_i=a_{i+1}=\cdots =a_j=1$, hence $f(\bar{X})=j-i$ and $g(X)=j-i+1$. Thus $f(\bar{X})-g(X)=-1$.

Case 2. The largest block contains exactly one of places $i$ or $j$. So for example for some $k$ ($i\le k<j$), $a_i=a_{i+1}=\cdots =a_k=1$ and $a_{k+1}=0$. Therefore we deduce that $g(X)=k-i+1$ and $f(\bar{X})\ge k-i+1$. Hence $f(\bar{X})-g(X)\ge 0$.

Case 3. The largest block contains none of $i$ and $j$. So for example for some $k$ and $l$ ($i<k\le l<j$) we have $a_k=0,a_{k+1}=\cdots =a_{l-1}=1$ and $a_l=0$. Thus $g(X)=l-k-1$ and $f(\bar{X})\ge l-k$. Hence $f(\bar{X})-g(X)\ge 1$.

Note that for each $1\le i<j\le n$ one of elements of $A_{ij}$ satisfies the condition of case 1 and there are $2^{n-4}-1$ binary strings $X=a_1{a}_2\cdots a_n$ such that $a_1=a_n=0$ and $a_2=a_{n-1}=0$ also they have another $1$.

$$\sum _{\begin{array}{c}X\in A_{ij}\\ 1\le i<j\le n\end{array}}(f(\bar{X})-g(X))\ge (-1{)}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}+(+1)(2^{n-4}-1).$$

Our conclusions are summed up in the following result.

$$\sum _X(f(X)-g(X))\ge 2^{n-4}-1-\left(\genfrac{}{}{0ex}{}{n}{2}\right)-n.$$

But it is very easy to prove by induction that for $n\ge 10$ we have $$2^{n-4}>\left(\genfrac{}{}{0ex}{}{n}{2}\right)+n+1\text{and this implies the assertion.}\square$$