Bulgarian National Mathematical Olympiad

If $A\cup B=M$ and $A\cap B=\varnothing$, then at most one of the sets $A$ and $B$ is good (otherwise $M$ is not good). Therefore the number of the good sets does not exceed half of the number of all subsets, i.e. $2^{n-1}$.

We will prove that the above estimate is sharp. Let $n=2k+1$ and $p$ be a prime such that $p>\frac{n(n-1)}{2}$. Let $p^k=a_1+a_2+\cdots +a_{n-1}+a_n$, where $a_i=i$ for $i=1,2,\dots ,n-1$ and $a_n=p^k-\frac{n(n-1)}{2}$. Then $(a_i,p)=1$ for every $i$. Consider the set $$M=\{p{a}_i\mid i=1,2,\dots ,n\}.$$ Then the sum of the elements of $M$ is equal to $p^{k+1}$. It is easy to see that the good subsets are exactly those with at most $k+1$ elements. They are exactly $2^{n-1}$.