NZMO Round Two

Solution:
First we show that $n = 4$ is possible with an example. The example $\{x_{1}, x_{2}, x_{3}, x_{4}\} = \{1, 3, 7, 9\}$ satisfies the problem because:

$\cdot\ 1 + 3 + 7 = 11$ is prime,

$\cdot\ 1 + 3 + 9 = 13$ is prime,

$\cdot\ 1 + 7 + 9 = 17$ is prime, and

$\cdot\ 3 + 7 + 9 = 19$ is prime.

We still have to prove that $n \geq 5$ is impossible.

Consider any set $\{x_{1}, x_{2}, x_{3}, \ldots, x_{n}\}$ 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$ (mod 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 $\{x_{1}, \ldots, x_{n}\}$ 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.