Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Hint: Equation set 2 is not the negation of equation set 1. –  Alexander Thumm Jan 21 '12 at 7:22
9  
Maybe the statement is: "Suppose integers $1,2,3,....,10$ are placed randomly in a circular wheel. Show that there exist three consecutive integers such that their sum is at least $15$." –  Paul Jan 21 '12 at 7:23
    
If the statement of the problem is exactly as you wrote, then three integers that are consecutive in the placement could all small. For example, $1$, $4$, and $5$ could be in that order on the wheel, and their sum is certainly less than $15$. It is also possible that $1$, $2$, and $3$ are in that order on the wheel, though maybe you are confusing consecutive on the wheel, which is the intended interpretation, with consecutive in the ordinary sense. However, I would guess that @Paul's guess is correct, since that is certainly what is proved. Maybe the problem was badly worded. –  André Nicolas Jan 21 '12 at 7:41
    
Thanks fr your inputs.. I can confirm the word consecutive here means one after the other (position wise) on the wheel. NOT n,n+1,n+2. –  redskins80 Jan 21 '12 at 11:34
    
What is the textbook? –  magma Jan 21 '12 at 16:53

3 Answers 3

up vote 1 down vote accepted

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$.

share|improve this answer
    
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. –  redskins80 Jan 22 '12 at 13:48

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.

share|improve this answer
    
right, i know wht ur trying to say. This explanation would make perfect sense if it wer used in some topic of 'formal logic' or boolean algebra in general. But frm wht i understand, r u trying to say tht the negation of 5+10+15>25 is ~5+~10+~15<25? Again, this would make sense in boolean, but in regular old school algebra shouldnt the negative be 5+10+15<25? –  redskins80 Jan 22 '12 at 14:01
    
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 Hardy –  magma Jan 24 '12 at 16:02

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.