1
$\begingroup$

Choosing $7$ numbers from $[1,2,...,11]$ will give us $2$ that have sum $12$. I tried:

There are only $5$ pairings possible:

$(7,5),(8,4),(9,3),(10,2),(11,1)$

Suppose I pick $6$, and then not to be a pair I will need to draw exactly 1 number from each of the above pairs. Suppose I picked, $7,8,9,10,11$. I will use up $6$ numbers. Thus any number that is left belongs to some pair.

How can I put this into mathematical terms and prove it?

$\endgroup$
2
$\begingroup$

Well, we don't necessarily have to put this in strictly mathematical terms but we can phrase the question as:

Prove that for any set of $7$ numbers chosen from the set $\{1, 2, 3, ..., 11\},$ there exists at least one pair of two numbers that sum to $12.$

We can formally prove this by contradiction. Imagine that we can find a set of $7$ numbers with no two elements with a sum of $12.$ We have $6$ boxes - one of which can hold up to $1$ number. Then our proposition is that each of $b_{1}, b_{2}, b_{3}, ..., b_{6}$ is less than or equal to $1.$ In other words, $b_{n} \le 1.$ Then $$\sum_{n = 1}^{6} b_{n} \le 6.$$

But we have seven numbers. Our proposition has to be false, and we are finished.

$\endgroup$
  • $\begingroup$ Can you explain what do you mean by each box can hold 1 number? $\endgroup$ – GRS Mar 9 '16 at 17:46
  • $\begingroup$ I meant that one box can hold up to 1 number. It can only hold $6.$ Because $6 + 6 = 12,$ and there is only 1 $6$ in the set. $\endgroup$ – K. Jiang Mar 10 '16 at 0:27

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.