Proving Summation of Consecutive Integers Greater Than 61 on a Circular Disk

[ryou00730]

Homework Statement

The integers 1 thru 40 are painted on the outside
rim of a circular disk, in “random” order. Prove that some consecutive
set of three integers must have a sum that is greater than 61. Hint: this
question is not about induction, but about summations of sequences.

Homework Equations

n/a

The Attempt at a Solution

I have no idea where to even start on this one.

 

[micromass]

I'll get you on the way:

Let the elements on the disk be numbered \{x_1,...,x_{40}\}. For conveniece we also put x_{41}=x_1,~x_{42}=x_2,.... Assume that for every i:
x_i+x_{i+1}+x_{i+2}\leq 61

Now try to evaluate the following sum in two ways (one way is the inequality above):

\sum_{i=1}^{40}{x_i+x_{i+1}+x_{i+2}}

 

[ryou00730]

I don't know how I would calculate that sum though, considering we don't know which integers are next to each other... or would i take the case of the three integers are all at least about 20?... I don't really follow.

 

[micromass]

Ok, another hint:

\sum_{i=1}^{40}{(x_i+x_{i+1}+x_{i+2})}=\sum_{i=1}^{40}{x_i}+\sum_{i=1}^{40}{x_{i+1}}+\sum_{i=1}^{40}{x_{i+2}}

The evaluation of these three sums does not depend on the order of the 40 elements...

 

[ryou00730]

Thank you, completely missed that, so in this case the individual sums are all equal, and the sum is 820 for each individual sum, so 2460 in total.

 

[ryou00730]

and I also notice, when I divide this total sum by 40 (the number of possible "i" s, I get 61.5), which is greater than 61)

 

[micromass]

Yes. So now you need to use the inequality x_i+x_{i+1}+x_{i+2}\leq 61 on the sum. This will provide an upper bound of this sum and will hopefully yield a contradiction.

 

[ryou00730]

so I'm dividing the total by 40, because really I just added up the sum of 120 randomly selected numbers (3 of each number), so by dividing by 40, I get the sum of 3 such randomly selected numbers, and this yields 61.5, which is a contradiction because we assumed it was less than or equal to 61?

 

[micromass]

Yes, that's good to.

The way I saw it was:

2460=\sum_{i=1}^{40}{x_i+x_{i+1}+x_{i+2}}\leq \sum_{i=1}^{40}{61}=40.61=2400

which is a contradiction.

 

[ryou00730]

Thank you very much for the help. The only thing is I don't see how you got the 40.61 value?
Thanks again.

 

[micromass]

The sum \sum_{i=1}^{40}{61} means (by definition)

(61+61+61+...+61)

where you take the sum 40 times. Thus this equals 40.61.

In general (and I suggest you remember this, as it will come in handy), if you summate a constant, then

\sum_{i=1}^n{c}=c.n

 

[ryou00730]

Oh 40.61 = 40X61. Ok I followed that, I just didn't see how you got 40.61. That clears everything up. Thanks again.

 

[micromass]

Ow, I am sorry for the confusion. I should have used other notation