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?

  • 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
    @Zev I also tried the non-working approach first, mathematicians are trained for symmetry.2011-10-12