# Prove by contradiction

Let

$$A = \cfrac {r_1 + r_2 + r_3 + \ldots + r_n}{n}$$

be the average of the real numbers $r_1, \ldots , r_n$. Prove there exists $i$ such that $r_i \ge A$.

So this is obviously true because the average is always going to be smaller than, or equal to, the largest number in the series (say, $r_i$).

However I'm not sure how to prove it by contradiction. I believe we would first make the assumption that there does NOT exist an $i$ such that $r_i \ge A$ (and then prove this to be false).

I'm not sure about the math to prove it, or how to write it. Any help would be greatly appreciated!

-
Suppose each $r_i < A$. Then $r_1 + r_2 + \dots+r_n < A + A + \dots + A$. What does that contradict? – Michael Biro Mar 7 '13 at 20:02
The question says nothing about $r_n$ being the largest element. Are you sure it's obvious that $A \le r_n$? – Erick Wong Mar 7 '13 at 20:03
Use "obvious" very sparingly! Usually if it is truly obvious, it does not require much, if any, explanation. Otherwise it is kind of annoying :) – rschwieb Mar 7 '13 at 20:08
@ErickWong Yeah I just realized that. I meant to say that the average will be smaller than the biggest number. I'll edit my question – Tur1ng Mar 7 '13 at 20:35

## 2 Answers

Proof by contradiction always involves starting from the negation of the conclusion and arguing towards a contradiction.

So, begin by assuming that such an $i$ does not exist. In other words, $r_i < A$ for all $i$.

Can you put a (strict) upper bound on the sum $r_i + \cdots r_n$? What does that inequality tell you about $\dfrac{r_1 + \cdots + r_n}{n}$? Why is that a contradiction?

-
Strictly speaking, a proof by contradiction always starts with assuming *both the truth of the hypothesis AND the negation of the conclusion, then arguing toward contradiction. To assume only the negation of the conclusion/desired result, and arguing to the conclusion that the assumption must therefore be false is proving the contrapositive: where you prove $p \rightarrow q$ by proving $\lnot q \rightarrow p$. – amWhy Mar 7 '13 at 20:22
oops: proof by contrapositive: proving $\lnot q \rightarrow \lnot p$ and therefore, $p \rightarrow q$. – amWhy Mar 7 '13 at 21:34

There is no need to prove it by contradiction.

Let $m = \max_i r_i$. Then $A = \frac{r_1+\cdots r_n}{n} \leq \frac{m+\cdots m}{n} = m$. Since $m = r_k$ for some $k$, we have $A \le r_k$ for some $k$.

If you must have contradiction, let $m$ be as above. If $m <A$, then you have $A = \frac{r_1+\cdots r_n}{n} = m < A$, which is an immediate contradiction.

-
I removed my previous comment because it looks like an irrelevant non-sequitur now that you've changed your answer so much. – Sammy Black Mar 7 '13 at 20:39
@SammyBlack: No, your comment was a relevant non sequitur. – copper.hat Mar 8 '13 at 0:44