IR-TST 2012 Problem 12

We call a subset $B$ of natural numbers loyal if there exists natural numbers $i\le j$ such that $B=\{i,i+1,\ldots,j\}$ . Let $Q$ be the set of all loyal sets. For every subset $A=\{a_1<a_2<\ldots<a_k\}$ of $\{1,2,\ldots,n\}$ we set $$f(A)=\max_{1\le i \le k-1}{a_{i+1}-a_i} \text{and} g(A)=\max_{B\subseteq A, B\in Q} |B|.$$ Furthermore, we define $$F(n)=\sum_{A\subseteq \{1,2,\ldots,n\}} f(A) \text{and} G(n)=\sum_{A\subseteq \{1,2,\ldots,n\}} g(A).$$ Prove that there exists $m\in \mathbb N$ such that for each natural number $n>m$ we have $F(n)>G(n)$ . (By $|A|$ we mean the number of elements of $A$ , and if $|A|\le 1$ , we define $f(A)$ to be zero).

Proposed by Javad Abedi