2
$\begingroup$

Let $a_i$, $1 \leq i \leq 5$ denote five positive real numbers such that $\sum_{i =1}^{5}a_i = 100$. Show that there exist a pair $a_i,a_j$ such that $|a_i-a_j|\leq 10$. Is there a proof using pigeon hole principle. I think i have a proof but it does not involve pigeon hole principle. My proof is:

Suppose there exist no such pair $a_i,a_j$. Assume that $a_1 < a_2 < a_3 < a_4 < a_5$, then $a_1 \in [0,20]$. As $a_i > a_{i-1} +10$ $ \forall 1 \leq i \leq 4$, we have $100 = \sum_{i=1}^{5}a_i > 5a_i +100$. Hence by contradiction the claim cannot be true.

$\endgroup$
  • $\begingroup$ This is a question in the book "walk through combinatorics" in the chapter Pigeon hole principle. $\endgroup$ – Nubres Feb 27 '14 at 16:22
  • $\begingroup$ Your solution doesn't invoke the pigeonhole principle explicitly, but implicitly. I.e., when you say that $a_1 \in [0, 20]$. $\endgroup$ – vonbrand Feb 27 '14 at 17:48
1
$\begingroup$

It is easy to turn your proof to a pigeon hole principle argument.

Let $a_1<a_2<a_3<a_4<_5$, then

$$100=(a_5-a_4)+2(a_4-a_3)+3(a_3-a_2)+4(a_2-a_1)+5a_1$$

Applying pigeon hole principle to $(a_5-a_4)$, 2 copies $(a_4-a_3)$, 3 copies $(a_3-a_2)$, 4 copies $(a_2-a_1)$.

$\endgroup$

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.