Pigeon hole subset problem

Question

For a given N numbers labeled from 1-N, we need to pick M numbers such that there are atleast K pairs of numbers(x,y) which statisfy x+y=N+1? can anyone help me out with this... please?

Answer 1

Hint:

Can you figure it out for $k=1$? What is the worst case scenario for not having any pair of numbers that add up to $N+1$? (further hint: think about what happens if you add two numbers smaller than $\frac{N}{2}$?) What about $k=2$? Can you make a conjecture based on these for larger $k$ as well?

In general and for proof, for $N$ even, try thinking in terms of modulo $\frac{N}{2}$. Try to generalize this idea to $N$ odd as well. (If not comfortable with wording things using modular arithmetic, simply note that each number in $1,\dots,N$ is paired with exactly one other number such that they add to $N+1$, and such a pairing is symmetric.)

Answer 2

If N is even then minimum numbers required to form k pairs are int(N/2 + K) if N is odd then minimum numbers required to form k pairs are int(N/2 + K + 1)