Define $A^i$ to be the symmetric difference of $A$ and the set $\{x \in \mathbb{N} \mid \min(A) < x < \max(A)\}$; if $|A| < 2$ then just set $A^i = A$. What this operation does is fix the minimum and maximum elements but take the complement of everything in between. Since $(A^i)^i = A$, this is a one-to-one correspondence among sets of natural numbers. For a subset $A$, let $B$ be the largest loyal subset of $A$, and let $k = B \cap \{\min(A), \max(A)\}$. Then $f(A^i) - g(A) = 1 - k$. This is because the largest value of $a_{i+1} - a_i$ in $A^i$ corresponds to the largest loyal subset $B$ in $A$. Usually $a_{i+1} - a_i$ will be one higher than $|B|$, unless if $B$ contains either of the max or min when $a_{i+1} - a_i$ will shrink by one for each. Let $S_k$ be the set of all subsets of $\{1, 2, \ldots k\}$ with $1,k \in S_k$, and let $s_k = \sum_{A \in S_k} f(A) - g(A)$. It can be computed that $s_0 = 0, s_1 = s_2 = s_3 = s_4 = s_5 = -1$. However we claim that $s_k \geq 2^{k-6} - 1$ for all $k \geq 6$. Consider all subsets $A$ in $S_k$ with $1,3,4,k \in A$ but $2,k-1 \notin A$. All such subsets $A$ have their largest loyal subset containing neither $1$ nor $k$, so $f(A^i) - g(A) = 1$ for them. There are $2^{k-6}$ such subsets. On the other hand, the only subset for which $f(A^i) - g(A) = -1$ is when $A = \{1, 2, \ldots k\}$. Therefore when we sum over all subsets we get at least $2^{k-6} - 1$. Consider the value of $F(n) - G(n)$. Let $T_{i,j}$ be all subsets with $\min(A) = i$ and $\max(A) = j$. Then the sum of $f(A) - g(A)$ over all subsets in $T_{i,j}$ is $s_{j-i}$. For each value of $j-i$ there are $n+1-(j-i)$ ways to pick $i,j$. So we get that \[F(n) - G(n) = ns_1 + (n-1)s_2 + (n-2)s_3 + \cdots + 2s_{n-1} + s_n.\] Only $s_1, s_2, s_3, s_4, s_5$ are negative, and these first five terms sum to $-5n-10$. On the other hand $s_n \geq 2^{n-6} - 1$, and a simple induction shows $2^{n-6} > 5n+11$ for all $n \geq 13$. Thus, $F(n) - G(n) > 0$ for all $n \geq 13$, so $m = 13$ solves the problem. (this is not the smallest such $m$ of course)

Nice! May I ask what's the motivation behind this argument? How did you find this solution? I only thought of just taking complements (which doesn't work), instead of the bijection you used.

I also tried complements at first. My motivation was that it didn't go so well, but it was close enough that I was sure I could tweak it. I thought about how if the definition of $f(A)$ allowed for using $0$ or $n+1$ as an $a_i$ the complements argument would work flawlessly. Then I tried to modify the definition I already had to match that idealized scenario, and figured out that I could just use the min and max elements the set already had as the equivalent of a $0$ and $n+1$.

I think simply taking complements can bring us to solution. Note that this is only sketch of a solution, there will be a lot of vagueness and won't gain much points for such solution in contest, but I write it only to enlighten my simple idea. Let's say that set A is average if its greatest subset of consecutive elements is neither on its start nor its end and complement of A has the same property. If B is complement of A and they are "average" we have $f(A)+f(B)=g(A)+g(B)+2$. Let $h(A)=f(A)+f(B)-g(A)-g(B)$. So if A is average, $h(A)=2$ and our goal is to prove that $\sum h(A)>0$ for sufficiently large $n$. The main idea of my solution was that if we are looking on very big sets, little of them aren't average. For convenience let's assume that if our set isn't average, its longest series of consecutive elements (or consecutive numbers which are NOT in A) is on its start. We will later fix this assumption. For example consider presence of elements from set $\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}$ in our sets. Firstly, consider case, when not all of them are in $A$. If A is average, $h(A)=2$ and if A isn't average $h(A) \geq -16$ (16 instead of 9, 10, 11 or whatever, because we are dealing with problem when something can be sufficiently large, so it really doesn't matter). But if $n$ is sufficiently large, ratio of sets which aren't average, to all possible sets, can be arbitrarily small. Let's call it $\epsilon$. So if we sum up $h(A)$ for such $A's$, we will get something about $(2^n-2^{n-10}-2^n \cdot \epsilon)\cdot 2 - 16 \cdot 2^n \cdot \epsilon =2^{n} ( (1- 2^{-10}- \epsilon) \cdot 2 - 16 \epsilon)$, so it can be very large. There are still cases, when there are all of $\{ 1, 2, ..., 10 \}$ in A, but they also don't change very much. Let's assume that in our set A are all of $\{ 1, 2, ..., k \}$, but $k+1$ not (and now we don't care about ending). $h(A) \geq -k-7$, but only out of $2^{k+1}$ sets has such a property. So we can estimate sum of $h(A)$ in such a way $\sum h(A) \geq 2^n ( \frac{-k-7}{2^{k+1}})$. And now sum it up for all possible $k$. And we are able to say that $ \frac{17}{2^{11}}+\frac{18}{2^{12}}+...$ is still very little in comparison to $2^{n} (1- 2^{-10}- \epsilon) \cdot 2$. We didn't care about ending, and what if there aren't any of 1, 2, ..., 10 in A, so there are all of them in its complement, but we can repeat this reasoning and see that contributions of all of these "bad cases" for us can be arbitrarily small and $h(A)=2$ for "nearly all" of sets. See, what I'm getting at? If you see a fatal error or have any doubts, which can break this solution, please write it. I'm aware that it's possible in some places there should be $2^{11}$ instead of $2^{10}$ or other typos, but as I said before, they are trifling matters, because we still can make everything bad for us arbitrarily small. And if you understand my idea and succesfully read this post to the end, I'll be pleased if you let me know about it (maybe in PM), to ensure me that I'm right.

If we define F(13)>G(13) then we can use induction to solve this problem. Let F(n+1)=2F(n)+T(n) G(n+1)=2F(n)+K(n) We can count K(n): It is the number of subset A of 1,2,..n sastifying x,...n is in A is the max loyal subset. With each A to increase for K(n) we consider {1,2...n} / A and when n+1 add to it T(n) is increase at least 1. So done.

That my solution maybe long. Let $S=${$1,2,3,...,n$} $A \in S$ , and $A=$ {$a_{1},a_{2},...,a_{k}$} Let $B_{A}=${$x\mid a_{i}<x<a_{i+1}$} Hence $f(A)=g(B_{A})+1$ Let $B(u,v)\in S$ and $B(u,v) $ have u is minnimal element, and v is max elements. Then $F(n)=\sum_{A\in S} f(A)=2^{n}+ \sum_{0<u,v<n+1} (u-1)(n-v)g(B(u,v))$ Let $H(n+1)=F(n+1)-F(n)-(G(n+1)-G(n)$ We have $F(n+1)-F(n)=2^{n}+\sum_{0<u,v<n+1} (u-1)g(Bu,v)=H(n+1)+\sum_{v<n}g(Bu,v)+(2^{n-1} + \sum_{v=n}g(Bu,v)$(*) $G(n+1)-G(n)=\sum_{v=n+1} g(Bu,v)=\sum_{v<n}g(Bu,v)+ \sum_{v=n+1, n\in Bu,v}g(Bu,v)$(**) With n>5 then $ \sum_{v=n+1, n\in Bu,v}g(Bu,v) < 2^{n-1} + \sum_{v=n}g(Bu,v)$(***) (because have $2^{n-1}$ set Bu,v have n and n+1 , and n>5 then have least 2 set haven,n+1 and loyal not have n and n+1) Hence n>5 and (*) (**) (***) $H(n+1)\geq H(n)+1$ Hence have n such that $H(n)>0$ and hence have m such that $F(n)>G(n)$ all n>m we are done

Antimonyarsenide, ah recursive methods works too. Well you don't need them. You can just replace $1$ and $n$ with the max and min of the subset which ends up working even if the set does not contain $1$ or $n$. That's what I did, and also what MellowMellon did. I guess recursion style methods are more motivated than this, but when doing the problem I decided against recursion since I knew the problem writers had a different way in mind. I would argue my way is more elegant. I posted my solution here: http://www.artofproblemsolving.com/blog/82627. Copying all the LaTeX is annoying. Once again it's basically the same as MellowMellon's solution. His motivation turns out to be pretty much the exact same as mine. Great minds think alike, I guess.