Results 1 to 2 of 2

Math Help - Partitioning integers into pairs so that the sum of each pair is prime.

  1. #1
    Newbie
    Joined
    Oct 2009
    From
    In limbo
    Posts
    18

    Partitioning integers into pairs so that the sum of each pair is prime.

    Show that, for every positive integer n, the numbers between 1 and 2n can be partitioned into pairs so that the sum of each pair is a prime number.

    I tried a few examples, and I figured that an odd number must be paired up with an even number, which isn't much. You can split the numbers 1 to 2n into {1,3,...2n-1} and {2,4,...,2n}, and then somehow pick one number from each set such that all have prime sums, but I am kind of stuck.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Black's Avatar
    Joined
    Nov 2009
    Posts
    105
    Prove by induction.

    The case n=1 is trivial.

    Suppose that for n = 1,2,\dots,m-1, the integers 1,2,\dots,2n-1,2n can be partitioned in pairs (x_1,y_1),(x_2,y_2),\dots,(x_n,y_n) s.t. \forall j, x_j+y_j = prime.

    For n=m, we have the integers 1,2,\dots,2m-1,2m. By the Bertrand-Chebyshev theorem \exists p=prime s.t. 2m<p<4m \Longrightarrow p-2m<2m. Therefore we have the following pairs:

    (p-2m,2m), (p-2m+1,2m-1),\dots, ((p-1)/2,(p+1)/2).

    This takes care of the integers p-2m to 2m. For the rest, note that p-2m-1 is an even number (odd-odd=even) and p-2m-1<2m-1 \Longrightarrow p-2m-1 \le 2m-2 = 2(m-1). By the induction hypothesis, we can partition the remaining integers into pairs s.t. the sum of each pair is prime. Q.E.D.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 01:37 PM
  2. Replies: 1
    Last Post: May 16th 2011, 08:54 PM
  3. Find a pair of integers
    Posted in the Algebra Forum
    Replies: 0
    Last Post: October 27th 2009, 11:33 PM
  4. Replies: 3
    Last Post: July 30th 2009, 01:19 AM
  5. Replies: 2
    Last Post: February 28th 2009, 02:52 PM

Search Tags


/mathhelpforum @mathhelpforum