Suppose that $S$ is a set of 2001 positive integers, and $n$ different subsets of $S$ are chosen so that their sums are pairwise relatively prime. Find the maximum possible value of $n$. (Here the "sum" of a finite set of numbers means the sum of its elements; the empty set has sum 0.)
The answer is $2^{2000}+1$. To see that we cannot do better than this, note that at least half of the $2^{2001}$ possible subsets of $S$ have even sums. Indeed, if all elements of $S$ are even, then all subsets have even sums; on the other hand, if there exists some odd $s \in S$, we can divide the subsets of $S$ into pairs of the form $\{T, T \cup\{s\}\}$ for each subset $T$ not containing $s$. Since the sum of $T$ and that of $T \cup\{s\}$ are of opposite parity, each pair contains exactly 1 subset with an even sum. So, in this case, half the subsets of $S$ have even sums. The upshot is that, in either case, there are at most $2^{2000}$ subsets of $S$ with odd sums. Since our chosen subsets can include at most one subset whose sum is even (because no two sums can have a common factor of 2), we cannot choose more than $2^{2000}+1$ subsets altogether.

Now, we must construct an example to show that we can have $n=2^{2000}+1$. To do this, let $k=\left(2^{2000}\right)$ !, and let $S=\left\{k, 2 k, 4 k, 8 k, \ldots, 2^{1999} k, 1\right\}$. We consider the $2^{2000}$ subsets containing the element 1 , plus the one subset $\{k\}$. It is evident that $k$, the sum of the last subset, is relatively prime to the sum of any subset containing 1 , since this latter sum is of the form $a k+1$ for some $a$. So now we just need to prove that any two distinct subsets containing 1 have relatively prime sums. Well, any such set consists of several distinct powers of 2 , multiplied by $k$, plus 1 . The sum of these powers of 2 is some number $a, 0 \leq a<2^{2000}$. Thus the subset's sum is $a k+1$. However, it follows from the uniqueness of binary representation that, for each possible value of $a$, there is only one subset whose sum is $a k+1$. Consequently, if we choose another, different subset (also containing 1), its sum is $b k+1$ for some $b, 0 \leq b<2^{2000}$ with $a \neq b$. Now suppose $a k+1$ and $b k+1$ are not relatively prime; then they have some common prime factor $p$. So $p \mid a k+1$ and $p \mid b k+1$, hence $p \mid(a k+1)-(b k+1)=(a-b) k$. Then, $p \mid a-b$ or $p \mid k$. But $a-b$ is nonzero and has absolute value $<2^{2000}$, so $a-b$ is one of the factors in the product $1 \cdot 2 \cdot 3 \cdots 2^{2000}=k$, and we get $a-b \mid k$. Thus, we are guaranteed that $p$ divides $k$. But then $p$ cannot divide $a k+1$, so we have a contradiction. We conclude that our subset sums are, in fact, pairwise relatively prime, completing the proof.