[I got this problem from Jay Misra, who got it from Gerard Huet.]

For any even number N, partition the integers from 1 to N into pairs such that the sum of the two numbers in each pair is a prime number.

Hint: Chebyshev proved that the following property (Bertrand’s Postulate) holds: for any k > 1, there exists a prime number p in the range k < p < 2*k.