5
$\begingroup$

a) Show that if seven integers are selected from the first 10 positive integers, there must be at least two pairs of these integers with the sum 11.

b) Is the conclusion in part (a) true if six integers are selected rather than seven?

I don't know how should I show that.

I know that in the worst situation we choose 1,2,...,7 that we have 7 + 4 = 11 and 5 + 6 = 11 but I don't know what should be the answer of this question

|cite|improve this question
$\endgroup$
6
$\begingroup$

Partition numbers from $1$ to $10$ into the following sets: $\{1,10\}$, $\{2,9\}$, $\{3,8\}$, $\{4,7\}$ and $\{5,6\}$. Now use pigeon hole principle.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ It's a little tricky in that we are asked to show two pairs have sum $11$, and the pigeonhole principle gives one pair by immediate application (even if as few as six integers are selected). The difference between selecting seven and six integers from $1$ to $10$ is that we get (at least) two pairs with sum $11$ in the former case and as few as one pair in the latter case. $\endgroup$ – hardmath Dec 1 '13 at 16:58
  • $\begingroup$ Since we end up with 5 pairs and will be choosing 7 integers we will have an n+2 pigeon hole. We will always have at least two pairs of integers in the selected integers that the sum will be 11. $\endgroup$ – CTS_AE May 31 '17 at 6:18
0
$\begingroup$

HINT. Use the Pigeonhole Principle.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. $\endgroup$ – learner Dec 1 '13 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.