Mongolian Mathematical Olympiad

Answer: $2^{n(n-1)/2}$. Let $N=2^n$ and $v_2(a)=s$ if and only if $2^s\mid a$ and $2^{s+1}\nmid a$, for a positive integer $a$. Let $v_2(A)=\{v_2(a)\mid a\in A\}$ for the set $A$. Claim: A set $A$ is good if and only if $v_2(A)=\{0,1,\dots ,n-1\}$. First we show that sets of the form $A_n=\{2^i{b}_i\mid b_i\text{ odd},0\le i\le n-1\}$ are good. For $n=1$, this is trivial. For $n\ge 1$, assume $A_n$ is good: $$\{S(X)(\mathrm{mod}N)\mid X\subseteq A_n\}=\{0,1,\dots ,N-1\}(\mathrm{mod}N),$$ and $$\{S(X)(\mathrm{mod}2N)\mid X\subseteq A_{n+1}\}=\{S(X),S(X)+N(\mathrm{mod}2N)\mid X\subseteq A_n\}.$$ This implies $$\{S(X)(\mathrm{mod}2N)\mid X\subseteq A_{n+1}\}=\{0,1,\dots ,2N-1\}(\mathrm{mod}2N).$$ Hence, $A_{n+1}$ is good. Assume that $A=\{a_1,a_2,\dots ,a_n\}$ is good, and $M=2^N-1$. Since $2^N\equiv 1(\mathrm{mod}M)$ and $$\{S(X)(\mathrm{mod}N)\mid X\subseteq A\}=\{0,1,\dots ,N-1\}(\mathrm{mod}N),$$ we have $$\prod _{j=1}^n(2^{a_j}+1)=\sum _{X\subseteq A}{2}^{S(X)}\equiv \sum _{k=0}^{N-1}{2}^k\equiv 0(\mathrm{mod}M).$$ Note $M={\prod }_{i=0}^{n-1}(2^{2^i}+1)$. Therefore, for any $0\le i\le n-1$, there exists $1\le j\le n$ such that $d=\gcd (2^{2^i}+1,2^{a_j}+1)\ne 1$. Thus $2^{2^i}\equiv 2^{a_j}\equiv -1(\mathrm{mod}d)$, and $2^{2^{i+1}}\equiv 2^{2^{a_j}}\equiv 1(\mathrm{mod}d)$, implying $2^{i+1}\mid 2^{a_j}$. Since $2^s\equiv 1(\mathrm{mod}d)$ where $s\le i+1$, $s>i$. Therefore, $s=i+1$, and $a_j=2^i{b}_i$, where $b_i$ is odd. Thus, $\{0,1,\dots ,n-1\}\subseteq v_2(A)$, and $|v_2(A)|=n$. Thus, the number of good sets such that all elements are less than $2^n$ is: $$2^{n-1}\times 2^{n-2}\times \cdots \times 2^0=2^{\frac{n(n-1)}{2}}.$$