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!
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$
Incorrect answer
Oops! The "solution" below is wrong in the following way:
I thought I had a "trivial" solution that gets 9 numbers into $P\cup Q$, but it only appeared to do that because I was an idiot and put one number into both sets without noticing. That solution therefore only actually achieves $|P\cup Q|=8$. I have other "less trivial" solutions that achieve the same, and I have a proof (in the "solution" below) that we can't get $|P\cup Q|=10$. But the possibility of getting 9 is not resolved by what follows.
Unfortunately it's 3:25am local time and I don't have time to attempt a proper fix. My apologies; hopefully someone else will do a less-hilariously-broken job. My incorrect solution follows, because I don't believe in hiding my screwups :-).
First of all,
suppose $P$ contains both an even number $p_0$ and an odd number $p_1$. Then $Q$ can't contain more than one number. (If $q,q'$ are of the same parity then one of the $p$ combines with them to make two different even numbers, which can't both be prime. If $q_0$ is even and $q_1$ odd, then $p_0+q_0,p_1+q_1$ are two different even numbers, which again can't both be prime.) So there can't be more elements of $P$ than primes in some interval of size 20: e.g., $Q=\{1\}$ and $P=\{2,4,6,10,12,16,18\}$. That leaves 12 elements in $O$, and we can't do better under these assumptions.
Obviously the same holds if
$Q$ contains both an even and an odd number.
So the only other possibility is that
one of $P,Q$ is all-even and the other is all-odd. Let's draw up a table showing which even numbers are compatible with which odd numbers:
1 3 5 7 9 11 13 15 17 19 2 x x x . x x . x x . 4 x x . x x . x x . x 6 x . x x . x x . x . 8 . x x . x x . x . . 10 x x . x x . x . . x 12 x . x x . x . . x x 14 . x x . x . . x x . 16 x x . x . . x x . . 18 x . x . . x x . . x 20 . x . . x x . . x .
where
we must pick a set of rows and a set of columns such that all the intersections have "x" rather than ".". We managed 8 elements in $P\cup Q$ before; if we can get 9 or more than one of the sets must contain at least 5 elements. Notice that we can't have both 1 and 20, or both 3 and 18, or ..., or both 19 and 2 -- so we can't get more than 10 numbers in total into $P\cup Q$. Recall that we managed 9 by taking one of P,Q to be {1}, so if we can do better then we must take at least one number from each of these pairs.
Now
suppose, specifically, that we take 20. Then the only odds we can have are 3,9,11,17. If we have all of those then the only evens that work are 2,20 for a total of 6 things in $P\cup Q$, no good. It's fairly easy to see (just by slicing out the relevant columns of the table above) that if we pick three of those four odd numbers we can't get more than three evens possible, for a total of 6 again, and that if we pick two then the best we can do is {3,9} with {2,4,8,10,14,20}, a total of 8: still no better than with one of our sets being a singleton. So there are no better-than-singleton solutions that use 20.
Recall that
to do better than the singleton solution we have to use one number from each of our pairs. In particular, if we don't use 20 then we must use 1. That means we don't use 8,14 and hence must use their partners 13,7. Using 13 rules out both 2 and 12, which means we must use their partners 19,9. Having 19 rules out 6,16 and therefore requires their partners 15,5; having 9 also rules out 12,18 and therefore requires their partners 9 (duh) and 3. But now the only evens remaining are 4,10 and both are incompatible with 5 which we need to have.
So
there is no solution that uses one from each of our pairs {1,20}, {2,19}, etc., and hence no solution that puts 10 or more numbers in $P\cup Q$
and therefore
we can't do better than the "singleton" solution that uses 9
and therefore the smallest possible number of elements in $O$ is
11.
(I bet it's possible to streamline the reasoning above somewhat.)
As it is currently worded:
There is no requirement that $P$ contain any number at all so long as all the other numbers are added to $Q$ or $O$.
Therefore
The minimum number of elements in $O$ is 0.
which can be obtained by
Addding all the numbers to $Q$. $P$ and $O$ are empty sets. There exists no value in $P$ that added to any value from $Q$ fails the condition of being prime, simply because there is no value in $P$ to add to a value in $Q$.
This feels like a non-answer, but it seems valid as far as I can tell.
Computer search solution
A simple search of all combinations of even numbers in P and odd numbers in Q confirms that 8 is the most you can use, so 12 unused in set O is the best you can do. Symmetry between odds and evens means you can generate an odd/even solution from any even/odd solution by incrementing odds and decrementing evens. It's nice to note that there is a pair of arrangements with two elements in the 'short' list.
Solutions.
P1 Q7 sum 8 P (2) Q (1,3,5,9,11,15,17)
P1 Q7 sum 8 P (4) Q (1,3,7,9,13,15,19)
P2 Q6 sum 8 P (4,10) Q (1,3,7,9,13,19)
P7 Q1 sum 8 P (2,4,6,10,12,16,18) Q (1)
P6 Q2 sum 8 P (2,4,8,10,14,20) Q (3,9)
P7 Q1 sum 8 P (2,4,8,10,14,16,20) Q (3)
Code. Not a shining light for correct coding but it runs quickly until you hand it 32 instead of 20. Not much interesting happens with higher numbers. Algorithm is basically loop from 1 to 2^N where N is number of evens, then loop over 2^N again for odds, and for each, check which even and odd numbers are 'present' in the list by checking whether the loop number has that bit set.
// PrimePartition
// partition the numbers 1 to N into two lists such that all sums of one element from each list are prime
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MaxLen 20
int primes[27]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103};
int odds[MaxLen+1];
int evens[MaxLen+1];
void Solve(int MaxList)
{
long i,j,ei,oi,k,pcount,qcount,thiseven,thisodd,thissum,failed,bestsofar=3;
// Loop over first group (evens)
for (i=1; i<(1 << MaxList); i++)
{
// Loop over second group (odds)
for (j=1; j<(1 << MaxList); j++)
{
failed = 0;
pcount = 0;
// check to see whether this group pair satisfies the condition
for (ei=0; ei<MaxList; ei++)
{
if ((1 << ei) & i)
{
pcount++;
thiseven = evens[ei];
qcount = 0;
for (oi=0; oi<MaxList; oi++)
{
if ((1 << oi) & j)
{
qcount++;
thisodd = odds[oi];
thissum = thiseven + thisodd;
// search for ei'th even number plus the oi'th odd number in the prime list
for (k=0; primes[k]<thissum && k<26; k++);
if (primes[k]>thissum || k >= 26)
{
failed=1;
goto failedprimesearch;
}
}
}
}
}
// ignore solutions not as good as best so far
if (pcount+qcount >= bestsofar)
{
bestsofar = pcount+qcount;
printf("P%ld Q%ld sum %ld\n", pcount,qcount,pcount+qcount);
pcount = 0;
// print out the solution
printf("Set P (");
for (ei=0; ei<MaxList; ei++)
{
if ((1 << ei) & i)
{
if (pcount)
printf(",");
pcount++;
printf("%ld", evens[ei]);
}
}
printf(")\n");
qcount = 0;
printf("Set Q (");
for (oi=0; oi<MaxList; oi++)
{
if ((1 << oi) & j)
{
if (qcount)
printf(",");
qcount++;
printf("%ld", odds[oi]);
}
}
printf(")\n\n");
}
failedprimesearch:;
}
}
}
void main(int argc, char **argv)
{
int i,high;
if (argc > 1)
{
high = atoi(argv[1]);
if (high < 5 || high > MaxLen*2)
goto usage;
}
else
{
usage:
printf("Usage: PrimePartition N\n");
printf(" where N is highest number (max %d)\n", 2*MaxLen);
exit(2);
}
for (i=0;i<MaxLen;i++)
{
evens[i] = i*2 + 2;
odds[i] = i*2 + 1;
}
Solve(high/2);
}
List O
4,6,7,8,10,12,13,14,16,18,19,20
List P
2
List Q
1,3,5,9,11,15,17
