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.

Give a proof by contradiction to show that if the integers 1, 2, ··· , 99, 100 , are placed randomly around a circle (without repetition), then there must exist three adjacent numbers along the circle whose sum is greater than 152.

Thus, we assume the following and try to show a contradiction exists:

Assume there exists a way to arrange the numbers such that their sum is less than or equal to 152.

I've tried quite a few different approaches that didn't succeed.

Many of you hinted to the following approach (which I have tried unsuccessfully). It's probably best that you attempt it separately before this taints your view of the problem:

Let $x_i$ denote the number at the $i^{th}$ position.

$$ x_1 + x_2 + x_3 \le 152 $$ $$ x_2 + x_3 + x_4 \le 152 $$ $$ etc. $$ $$ x_{99} + x_{100} + x_1 \le 152 $$ $$ x_{100} + x_1 + x_2 \le 152 $$

Summing both sides:

$$ 3\sum\limits_{i=1}^{100} x_i \le 100(152) $$ $$ 3\sum\limits_{i=1}^{100} i \le 100(152) $$ $$ 3(5050) \le 15200 $$ $$ 15 150 \le 15200 $$

This is not a contradiction.

I must be missing something. Thoughts?

share|improve this question
1  
You haven't negated the statement correctly. You want to assume that there exists a way to arrange the numbers such that, for every collection of three adjacent numbers (you omitted this quantifier), their sum is less than or equal to $152$. You might find Tim Gowers' blog posts on basic logic, starting at gowers.wordpress.com/2011/09/25/… , useful. –  Qiaochu Yuan Oct 12 '11 at 15:29
1  
@Zev: A statement is not false just because the negation implies something true. –  Phira Oct 12 '11 at 15:44
    
@Phira: Well, my problem was that I wasn't seeing how anyone below was deriving a contradiction, I shouldn't have said that that necessarily meant the statement was false. But I've realized my problem: I wasn't seeing the part of the argument where we use the fact that $\lceil 151.5\rceil=152$ –  Zev Chonoles Oct 12 '11 at 15:46
    
@Zev No, the ceiling is not sufficient to get greater than 152. I wonder if anyone here actually reads my answer. If you use an average of all triples, it just isn't enough, you need what I wrote in my answer. –  Phira Oct 12 '11 at 15:49
    
@Phira: I have read your answer and upvoted it, and downvoted the incorrect answers. –  Zev Chonoles Oct 12 '11 at 15:52

1 Answer 1

up vote 5 down vote accepted

After making your assumption you would like to group your numbers into groups of threes, but 100 is not divisible by 3.

Decide which number is good to set apart, then apply your assumption to the rest.

share|improve this answer
    
I'm not sure I see your point. Say I set aside 100 and group the remaining 99 numbers in 3 groups, how does that help me? –  David Chouinard Oct 12 '11 at 16:05
2  
@David: 100 is not a good number to set apart; try a different one. –  Zev Chonoles Oct 12 '11 at 16:07
    
@ZevChonoles I don't see why grouping numbers is useful (irrelevant of which number is set aside). Should I be finding the average of triplets for each group? –  David Chouinard Oct 12 '11 at 16:19
    
@David: No, no averages; Phira's answer is much simpler than the (incorrect) approach I and everyone else jumped to initially. Literally: pick one number out of the hundred and set it aside. There are 99 numbers left, hence 33 consecutive triples. Recall what are we assuming about consecutive triples in order to try to reach a contradiction; then add. –  Zev Chonoles Oct 12 '11 at 16:22
    
@Phira: I did misread the question. I have deleted my answer. –  robjohn Oct 12 '11 at 16:45

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.