1
$\begingroup$

So we were asked to solve a question in class about proof by contradiction...

Q) Suppose integers $1,2,3,\dots,10$ are placed randomly in a circular wheel. Show that the sum of any three consecutive integers is at least $15$.

Logical Answer: NO, because $1+2+3 = 6 < 15$.

Textbook Answer: PROVED. How?....

Let $A_r$ be the number positioned in the wheel at $r$-th position. Equation Set 1:

$\begin{align*} &A_1+A_2+A_3 \ge 15\\ &A_2+A_3+A_4 \ge 15\\ &A_3+A_4+A_5 \ge 15\\ &\qquad\qquad\qquad\vdots\\ &A_{10}+A_1+A_2 \ge 15 \end{align*}$

So, continuing proof by contradiction, lets assume Equation Set 1 is NOT true. Which implies--

Equation Set 2-

$\begin{align*} &A_1+A_2+A_3 < 15\\ &A_2+A_3+A_4 < 15\\ &A_3+A_4+A_5 < 15\\ &\qquad\qquad\qquad\vdots\\ &A_{10}+A_1+A_2 < 15 \end{align*}$

Now, adding all equations in Equation Set 2 we get

$3(A_1+\cdots+A_{10}) < 15\cdot10$

$\frac{3n(n+1)}2 < 150\;,$ where $n=10$ (cuz sum of $n$ integers is $n(n+1)/2$)

$3\cdot55 < 150$

$165 < 150$

Which is FALSE and is a contradiction to what we assumed (Equation set 2). Therefore our assumption is wrong and Equation Set 1 holds TRUE.

Which means sum of $3$ nos should be at least $15$. BUT logically thinking, a simple example of $1+2+3$ does not satisfy. What is the problem? Please Help!

  • 0
    @redskins80 What I meant was I didn't hit enter (or didn't mean to or something), but it DID appear. So, you responded to it and I noticed it was here. Thus, I deleted it.2012-01-22

3 Answers 3

0

The error in the reasoning is "Which implies--", which is wrong. In fact you gave an example (or better: you suggested, since you did not specify all A$i$, but this can easily be completed) in which the first set of equations is NOT satisfied (already the first is false). However, if you actually complete your example, you can check that the second set of equations is not satisfied either. Now I leave it to you to figure out how that could happen, but it clearly is the case.

By the way this is just an instance of a general method to pinpoint the error in any essentially every "proof" that purports to establish a statement for which you have a concrete counterexample at hand. The counterexample must satisfy the hypotheses but not the conclusion of the argument (since that is what makes it a counterexample); now one by one test the truth of the intermediate statements in the counterexample, which must switch from true to false somewhere, and at that point the reasoning must be wrong.

1

The purpoted proof is WRONG. It does not matter if it was in the textbook or not. Why? Because a proof by contradiction starts by negating the thesis. Now here the thesis is a conjuction of statements:

$S_0\land \dots\land S_{9}$

(I have relabelled the positions $0,\ldots,9$, so I can use modular arithmetic notation)

where $S_k$ is: $A_k+A_{k+1}+A_{k+2} \ge 15$ and indices are summed Mod 10.

So the thesis is basically your set 1 (with indices relabelled). It is a conjuction, so its negation is the disjunction of the negation of the $S_k$:

$\neg S_0\lor \dots\lor \neg S_9$

(De Morgan laws).

However the purported proof starts with Set 2, which is:

$\neg S_0\land \dots\land \neg S_9$

So , no conclusion can be drawn from that.

  • 0
    my proof/answer is exactly the same as that by Michael Hardy, but I am using formulas, instead of plain English words. Reread carefully the meaning of my definitions and you will see that it matches the argument given in the answer by Michael Hardy2012-01-24
1

If it is NOT TRUE that all members of a set of numbers are $\ge15$, that's equivalent to saying at least one of them is less than $15$, not that all of them are less than $15$.

  • 0
    if u put it tht way it does make sense. But, if i say that each equation in set 1 is an 'event' (each event being picking up an adjacent triplet and its sum being > 15), then the negation of each event is that the sum of those three is < 15. Looking at it tht ways also makes sense.2012-01-22