Given that the sum of five positive real numbers is 100. Prove that there are two numbers among them whose difference is at most 10 using PHP.

107 Views Asked by At

I did this:

Assume all numbers have a difference that is bigger than $10$. Let these $5$ numbers be $a>b>c>d>e>0$. So we have $$a>b+10>c+20>d+30>e+40>40$$So, $$a>e+40, \quad b>e+30, \quad c>e+20, \quad d>e+10$$ So $$100=a+b+c+d+e>5e+100>100$$ Contradiction.

But is there a way that we can use to solve this exact same problem using pigeonhole principle (PHP) ?

1

There are 1 best solutions below

0
On

I cannot solve the entire problem using PHP alone. Here is a method which uses PHP as a step.

We prove by induction on $n$ that if there are $n$ positive real numbers whose sum is at most $5n(n-1)$, then there will exist two whose difference is at most $10$. The base case $n=2$ should be obvious.

For the inductive step, there are two cases. Suppose that one of the real numbers is greater than $10(n-1)$. It follows that the sum of the remaining $n-1$ real numbers is at most $$ 5n(n-1)-10(n-1)=5(n-1)(n-2) $$ Therefore, we can apply the induction hypothesis to these remaining $n-1$ numbers to conclude that there exist two of them whose difference is at most $10$.

In the other case, all of the real numbers must be in the range $[0,10(n-1))$. This interval can be partitioned into $n-1$ intervals of length $10$. These intervals are the holes, and the $n$ numbers are the pigeons. By PHP, there are two numbers in the same interval. Clearly, their distance must be at most $10$.