Strange Proof Question

  • Thread starter ryou00730
  • Start date
  • #1
29
0

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.
 

Answers and Replies

  • #2
22,089
3,297
I'll get you on the way:

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

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

[tex]\sum_{i=1}^{40}{x_i+x_{i+1}+x_{i+2}}[/tex]
 
  • #3
29
0
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.
 
  • #4
22,089
3,297
Ok, another hint:

[tex]\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}}[/tex]

The evaluation of these three sums does not depend on the order of the 40 elements...
 
  • #5
29
0
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.
 
  • #6
29
0
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)
 
  • #7
22,089
3,297
Yes. So now you need to use the inequality [tex]x_i+x_{i+1}+x_{i+2}\leq 61 [/tex] on the sum. This will provide an upper bound of this sum and will hopefully yield a contradiction.
 
  • #8
29
0
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?
 
  • #9
22,089
3,297
Yes, that's good to.

The way I saw it was:

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

which is a contradiction.
 
  • #10
29
0
Thank you very much for the help. The only thing is I don't see how you got the 40.61 value?
Thanks again.
 
  • #11
22,089
3,297
The sum [tex]\sum_{i=1}^{40}{61}[/tex] means (by definition)

[tex] (61+61+61+...+61)[/tex]

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

[tex]\sum_{i=1}^n{c}=c.n[/tex]
 
  • #12
29
0
Oh 40.61 = 40X61. Ok I followed that, I just didn't see how you got 40.61. That clears everything up. Thanks again.
 
  • #13
22,089
3,297
Ow, Im sorry for the confusion. I should have used other notation :smile:
 

Related Threads on Strange Proof Question

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
3
Views
940
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
677
Replies
6
Views
1K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
3K
Top