It cant be proven, since it is false. [Oups, see below, the op statement may be true].

---my original reply

Hint: prime counting function π(n)

Eg: Let k = 100. Your set is thus 1,2,..., 200.

You want to partition this into 100 pairs {a_i, b_i}, such as their sum is prime.

The sum of a pair has a minimum of 3 and a max that can be 101 to 399.

But π(399) = 78. IOW, there are only 78 primes from 1 to 399. (There are less than that from 1 to 101).

But you need 100 of them, thus impossible. QED.

--end of my original reply.

BUT.... I see now...Above I assumed that the a_i + b_i gives distinct (prime) values. You did not require that.

Again, for k=100, we can chose many pairs such that their sum is 199 say: {1,198}, {2,197}...{99,100}.

This has a max of 99 pairs. In fact, you always have less than k pairs; you have at maximum k-1 pairs. Hence impossible. BUT if you consider the possibilities of pairs such as {2,197} and {2, 3} in the same set, then you can trivially generate more pairs, hence possible. And if the a+b is allowed be be greater than 2k (that is not excluded in the op, hence is permitted), then by the theorem m<p<2m, just chose that p as to generate your pairs, as other replies have pointed out.

# Prime pairs?

Prove that the set { 1, 2, ..., 2k} can be partitioned into k distinct pairs {a_i, b_i} such that for each i, ( a_i + b_i) is prime

## 6 Answers

- 12
- There's a proof here that uses a high-powered theorem, so it's not particularly satisfying. http://mathhelpforum.com/number-theory/1...

Can anyone give a simpler proof?20 - I agree with rotchm.

Take k = 60.

There are 60/2 = 30 pairs, so we need 30 primes less than 2x60 = 120. And we cannot use 2 because no pair of numbers 1 to 60 add to 2.

The 30th prime number, excluding 2, is 127.

Not possible when k = 60, so not true.03 - This is a famous problem, risen to the status of conjecture. All attempts to mathematically prove it have come up empty.05
- i think try to diagram the math problem it might help.Partitions are the number of ways a number can be added up02
- The proof is by induction on n.

For n = 1 the result is trivial.

{1+2} = 3

For n > 1, let p be a prime satisfying 2n < p < 4n. Since 4n is not prime we have p = 2n + m for 1 ≤ m < 2k. Pair 2n with m, 2n−1 with m+1, and continue up to n+⌈k⌉ with n+⌊k⌋ (this last is a valid pair since m is odd).

This deals with all of the numbers in {m, m+1, …, 2n}; the inductive hypothesis deals with {1, 2, …, m−1} (again since m is odd).40

### Trending

- What are the definitions of relative extrema and absolute extrema?
- HOW TO SOLVE 8X^2 + 7X = -2?
- Why is x*2 + x*2 = 2x*2 instead of x*4?
- When there is no linear association between two variables, the r-value will be close to -1. True or false?
- What is the number one problem in todays world?
- How many dozen are in 60?
- Will I ever use Algebra in life to pay bills or do basic human functions?
- Two consecutive numbers have a sum of 123. What are the two numbers?
- How long is one square inch?
- The sum of two numbers is -36. Their difference is 68. Find the numbers?