# Tricky proof: sum of adjacent integers

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

I must be missing something. Thoughts?

-
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
@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