3. Problem: Let $\left\{x_{1}, x_{2}, x_{3}, \ldots, x_{n}\right\}$ be a set of $n$ distinct positive integers, such that the sum of any 3 of them is a prime number. What is the maximum value of $n$ ?
Solution: First we show that $n=4$ is possible with an example. The example $\left\{x_{1}, x_{2}, x_{3}, x_{4}\right\}=\{1,3,7,9\}$ satisfies the problem because:
- $1+3+7=11$ is prime,
- $1+3+9=13$ is prime,
- $1+7+9=17$ is prime, and
- $3+7+9=19$ is prime.

We still have to prove that $n \geq 5$ is impossible.
Consider any set $\left\{x_{1}, x_{2}, x_{3}, \ldots, x_{n}\right\}$ such that the sum of any 3 of them is a prime number. Also consider the three "pigeonholes" modulo 3; the residue classes 0,1 and 2 . If all three pigeonholes were non-empty, then it would be possible to choose three numbers - one from each pigeonhole. This would result in a sum which is $0+1+2 \equiv 0(\bmod 3)$, and since the numbers are distinct positive integers, this sum would be $>3$. Thus the sum would not be prime which is a contradiction. Hence at least one of the pigeonholes must be empty. i.e.
The numbers $\left\{x_{1}, \ldots, x_{n}\right\}$ are distributed amongst (at most) two different residue classes modulo 3 .

Now assume for the sake of contradiction that $n \geq 5$. By the pigeonhole principle at least one residue class contains at least 3 of the numbers. The sum of any three numbers from the same residue class is always a multiple of 3 and so this is a contradiction.
Therefore $n<5$ as required.

Comment: The example $\{1,3,7,9\}$ is not the only example that satisfies the problem with $n=4$. Here are many other examples: $\{1,5,7,11\},\{3,5,11,15\},\{1,3,13,15\}$, $\{3,9,11,17\},\{5,9,15,17\}, \ldots$ Searching for an example when $n=4$ is much easier if you conjecture that all the $x_{i}$ must be odd.