mathematics - Dividing the first 20 numbers into 3 lists

Place every number from 1 to 20 into one of three lists $P$, $Q$ or $O$, such that any number from $P$ added to any number from $Q$ gives a prime. What is the fewest number of elements that can be in $O$? Note that $P$ and $Q$ cannot be empty.

Good luck!

Answer

It is possible to solve this without a computer search. The proof of $\min|O|$ is below.

These are all the odd prime numbers $\le20+19=39$; colours important later.

$$\color{red}3,\color{blue}5,\color{green}7,\color{orange}{11},\color{purple}{13},\color{cyan}{17},\color{brown}{19},\color{silver}{23},\color{lightgreen}{29},31,\color{gold}{37}.$$ Let $P$ contain even integers only and $Q$ odd without loss of generality. We can then form the following table, where $\checkmark$ indicates whether the entry is prime and the colours correspond to the prime numbers above. The superscripts next to each number show how many times the total is prime. $$\begin{array}{c|c}+&2^{[7]}&4^{[7]}&6^{[6]}&8^{[5]}&10^{[6]}&12^{[6]}&14^{[5]}&16^{[5]}&18^{[5]}&20^{[4]}\\\hline1^{[7]}&\color{red}\checkmark&\color{blue}\checkmark&\color{green}\checkmark&&\color{orange}\checkmark&\color{purple}\checkmark&&\color{cyan}\checkmark&\color{brown}\checkmark&\\\hline3^{[7]}&\color{blue}\checkmark&\color{green}\checkmark&&\color{orange}\checkmark&\color{purple}\checkmark&&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark\\\hline5^{[6]}&\color{green}\checkmark&&\color{orange}\checkmark&\color{purple}\checkmark&&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark&\\\hline7^{[5]}&&\color{orange}\checkmark&\color{purple}\checkmark&&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark&&\\\hline9^{[6]}&\color{orange}\checkmark&\color{purple}\checkmark&&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark&&&\color{lightgreen}\checkmark\\\hline11^{[6]}&\color{purple}\checkmark&&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark&&&\color{lightgreen}\checkmark&\checkmark\\\hline13^{[5]}&&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark&&&\color{lightgreen}\checkmark&\checkmark&\\\hline15^{[5]}&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark&&&\color{lightgreen}\checkmark&\checkmark&&\\\hline17^{[5]}&\color{brown}\checkmark&&\color{silver}\checkmark&&&\color{lightgreen}\checkmark&\checkmark&&&\color{gold}\checkmark\\\hline19^{[4]}&&\color{silver}\checkmark&&&\color{lightgreen}\checkmark&\checkmark&&&\color{gold}\checkmark&\end{array}$$ Clearly, $|S|=1\implies\max|S^*|=7\implies\min|O|=12$ where $S\in\{P,Q\}$ and $S\cup S^*=P\cup Q$. In particular, this yields the solutions $$[P,Q]=\begin{cases}[\{2\},\{1,3,5,9,11,15,17\}]\\ [\{4\},\{1,3,7,9,13,15,19\}]\\ [\{2,4,6,10,12,16,18\},\{1\}]\\ [\{2,4,8,10,14,16,20\},\{3\}]\end{cases}$$ due to the symmetry of $\checkmark$ in the table. Now, suppose $|S|=2$. It can be seen that $|O|$ is minimised and is equal to $12$ again when $|S^*|=6$, with $S=\{4,10\},\{3,9\}$ as they are the instances where $\checkmark$ appears in both columns/rows the most times. In particular, this yields the solutions $$[P,Q]=\begin{cases}[\{4,10\},\{1,3,7,9,13,19\}]\\ [\{3,9\},\{2,4,8,10,14,20\}]\end{cases}.$$ This means that any further solutions with $|S|>2$ must contain either $\{4,10\}$ or $\{3,9\}$. Again, due to symmetry, only the former case will be considered. Of the rows $1,3,7,9,13,19$, the highest number of checkmarks that appear in columns other than $4,10$ is $16$, with $4$ checkmarks at $1,3,7,13$. Therefore, if $|S|=3$, $\max|S^*|=4$ so $\min|O|=13>12$. As no other column contains checkmarks at all of $1,3,7,13$, it can be concluded that $\min|O|>12\,\forall |S|>2$. The result that $\min|O|=12$ follows. $\square$