Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given an $n >0$ is it possible to partition the set $\mathcal{P} = \{1,2, \cdots, 2n\}$ into $n$ pairs $(a_{i},b_{i})$ such that $a_{i} + b_{i}$ is a prime?

share|cite|improve this question
@Nuno: I have removed the set theory related tag altogether. – Aryabhata Nov 23 '10 at 6:45
@Moron: I agree. I thought of removing the tag set-theory, but let it go. Thanks for the change. – Nuno Nov 23 '10 at 12:09
up vote 12 down vote accepted

Yes. The proof is by strong induction. The base case is obvious. By Bertrand's postulate there exists a prime $p$ between $2n+1$ and $4n$, so pick the pairs $\{ p-2n, 2n \}, \{ p-2n+1, 2n-1 \}, ...$ and so forth. Now it remains to pair up the numbers $\{ 1, 2, ... p-2n-1 \}$, which is possible by the inductive hypothesis.

share|cite|improve this answer
I think the way you partitioned the set is a bit wrong. You can create the pairs ranging from $<p-2n,2n>...<p-n,n>$. The remaining subset yet to be partitioned is $\{p-(n-1),..,1\}$ which by induction you have the necessary partition. – Ory Band Nov 22 '13 at 21:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.