3
$\begingroup$

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?

  • 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 http://gowers.wordpress.com/2011/09/25/basic-logic-connectives-and-and-or/ , useful.2011-10-12
  • 1
    @Zev: A statement is not false just because the negation implies something true.2011-10-12
  • 0
    @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$2011-10-12
  • 0
    @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.2011-10-12
  • 0
    @Phira: I have read your answer and upvoted it, and downvoted the incorrect answers.2011-10-12
  • 0
    @David I suggest that you try my approach which was the first answer here.2011-10-12

1 Answers 1

5

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.

  • 0
    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?2011-10-12
  • 2
    @David: 100 is not a good number to set apart; try a different *one*.2011-10-12
  • 0
    @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?2011-10-12
  • 0
    @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.2011-10-12
  • 0
    @Phira: I did misread the question. I have deleted my answer.2011-10-12
  • 0
    @Zev I also tried the non-working approach first, mathematicians are trained for symmetry.2011-10-12