Finding prime elements in a subset Consider the set $S= \{1,2,\cdots,2n\}$. Let $\mathscr{B}$ be a subset of $S$ which contains strictly more than $n$ elements. 


*

*Prove that we can find elements $m,k$ in $\mathscr{B}$ such that $m+k$ is prime. 

 A: We prove by strong induction on $n$ that if a subset $A$ of $S$ is such that no two distinct elements sum to a prime, then $|A| \leq n$. 
This is clearly true when $n=1$, since $A$ is a subset of $\{1, 2\}$, and $1+2=3$ is a prime, so that $|A| \leq 1$.
Suppose that it is true for $1 \leq n \leq k, k\geq 1$, then consider $n=k+1$. By Betrand's postulate, since $2(k+1)>1$, there exists a odd prime $p$ strictly between $2(k+1)$ and $4(k+1)$. Write $p=2(k+1)+l$, where $1 \leq l \leq 2k+1$, $l$ odd. Consider the pairs of numbers $(l, 2(k+1)), (l+1, 2k+1), \ldots , (k+1+\frac{l-1}{2}, k+1+\frac{l+1}{2})$. $A$ must have at most 1 element from each pair, otherwise $A$ will contain 2 numbers which sum to $p$, a prime. Therefore $A$ has at most $\frac{2(k+1)-l+1}{2}$ elements in $\{l, l+1, \ldots , 2(k+1)\}$.
By the induction hypothesis, $A$ has at most $\frac{l-1}{2}$ elements in $\{1, 2, \ldots , l-1\}$. Therefore $|A| \leq \frac{2(k+1)-l+1}{2}+\frac{l-1}{2}=k+1$, so we are done by strong induction.
Therefore if we have a subset of $\{1, 2, \ldots , 2n\}$ with strictly more than $n$ elements, then we can find 2 distinct elements in this subset such that their sum is prime.
