1 We write $\{a, b, c\}$ for the set of three different positive integers $a, b$, and $c$. By choosing some or all of the numbers $a, b$ and $c$, we can form seven nonempty subsets of $\{a, b, c\}$. We can then calculate the sum of the elements of each subset. For example, for the set $\{4,7,42\}$ we will find sums of $4,7,42,11,46,49$, and 53 for its seven subsets. Since 7,11 , and 53 are prime, the set $\{4,7,42\}$ has exactly three subsets whose sums are prime. (Recall that prime numbers are numbers with exactly two different factors, 1 and themselves. In particular, the number 1 is not prime.)
What is the largest possible number of subsets with prime sums that a set of three different positive integers can have? Give an example of a set $\{a, b, c\}$ that has that number of subsets with prime sums, and explain why no other three-element set could have more.
Solution:
The answer is five.
For example, the set $\{2,3,5\}$ has $2,3,5,5,7,8$, and 10 as its sums, and the first five of those are prime. If you're worried about 5 appearing twice in that list, then try $\{2,3,11\}$ which has $2,3,11,5,13,14$, and 16 as its subsets' sums, so now we see five different primes.
No set can have more than five prime subset sums because for any set $\{a, b, c\}$ :
- If the set contains three even numbers, then clearly it can have only one prime subset sum, namely 2 if it is in the set.
- If the set contains two even numbers $a$ and $b$ then $a, b$, and $a+b$ are all even. Since they are distinct positive integers, only one of $a$ and $b$ can be equal to 2 , and $a+b>2$, so we have at least two non-prime sums and thus at most five prime subset sums.
- If the set contains one even number $a$ then $a, b+c$, and $a+b+c$ are all even. Again, only $a$ can be equal to 2 and thus prime, so we have at least two non-prime sums as in the previous case.
- If the set contains zero even numbers (and thus three odd numbers) then $a+b, a+c$, and $b+c$ are all even, and since the numbers are distinct positive integers then none of these three sums can equal 2 , so none of those are prime. Thus the set has at most four prime subset sums.

In any case, the maximum number of prime subset sums is five.

There are various ways to shorten the above argument. For example, once you have found a set with five prime subset sums, you can check whether 6 is possible by looking at two cases: either two or three of the elements of the set have to be prime.