Very Difficult Proof - Tilted Forum Project Discussion Community

blizzak · 01-29-2004, 01:52 PM

This question was given to me in an assignment, and I have yet to figure it out:

Show that if the first 10 positive integers are placed around a circle, in any order, there exists three integers in consecutive locations around the circle that have a sum greater than or equal to 17.

the question instructs us to use a previous question to help us solve it, which is basically to prove that one number in a range of numbers is greater than the average of the range. That was easy, it was a contradiction proof:

let a1 + a2 ... + aN be the range of numbers, and A be the average, and assume that the each number is less than the average, so a1 + a2 ... + aN < A X n

divide each side by n:

(a1 + a2 ... + aN) / n < A
but (a1 + a2 ... + aN) / n = A (the average)
therefore it is a contradiction.

my first instinct for the problem was to try and prove the problem by contradiction, that is:
let a1 - a10 be the range; they represent the first 10 integers (in any order
then:
a1 + a2 + a3 < 17
a2 + a3 + a4 < 17
a3 + a4 + a5 < 17

and so on, so each number is used 3 times around the circle
combine the equations and you get:

3(a1 + a2 ... + a10) < 17(10)
but that works out to 165 < 170, which is fine.
Anyone have any idea how to solve this problem?

KnifeMissile · 01-29-2004, 03:26 PM

You were on the right track but you didn't listen to the advice of the question. Try to use the previous lemma to prove this question.

First, lets think about all the possible groups of these consequtive integers that are arranged around this circle. We want to show that there necessarily exists a group whose elements sum to a number greater than or equal to 17. So, because we're trying to prove a property of this set of groups (that there exists one with our special property), lets take a look at the nature of these groups, in general.

So, lets ask the question "what is the average of each group's average?" This may sound like a funny question but it's easy enough to answer because each group is the same size. Therefore, the average of their averages is simply the average of all the different group's elements. If you are not convinced of this I'll leave this fact as an exercise for the reader. This is your homework, after all.
You've established, yourself, that the sum of all the elements of all the groups is 165 and that there are 30 of them. So, that makes the average 165 / 30 = 5.5. This is not surprising since it is also the average of the consecutive integers 1 through 10.

Now, I don't want to do your homework for you (you are supposed to learn this stuff) but you should be wondering how to apply your lemma (at least one element must be greater than the average) to this situation. Then the proof should become obvious to you.

If you totally give up, come back and I will show you the answer.
Good luck!

KnifeMissile · 01-29-2004, 06:58 PM

Actually, I've been talking this over with my boss and there's a more direct way of proving it than what I was doing, although it's very much along the same lines.

Instead of looking at an average of averages, simply examine the average of the sums of group elements and try to apply the lemma on that. It's equivialent to what I was suggesting but skips an uneccesary step.

It seems like every time I find a way there's always a better one...

01-29-2004, 01:52 PM	#1 (permalink)
blizzak Crazy	Very Difficult Proof This question was given to me in an assignment, and I have yet to figure it out: Show that if the first 10 positive integers are placed around a circle, in any order, there exists three integers in consecutive locations around the circle that have a sum greater than or equal to 17. the question instructs us to use a previous question to help us solve it, which is basically to prove that one number in a range of numbers is greater than the average of the range. That was easy, it was a contradiction proof: let a1 + a2 ... + aN be the range of numbers, and A be the average, and assume that the each number is less than the average, so a1 + a2 ... + aN < A X n divide each side by n: (a1 + a2 ... + aN) / n < A but (a1 + a2 ... + aN) / n = A (the average) therefore it is a contradiction. my first instinct for the problem was to try and prove the problem by contradiction, that is: let a1 - a10 be the range; they represent the first 10 integers (in any order then: a1 + a2 + a3 < 17 a2 + a3 + a4 < 17 a3 + a4 + a5 < 17 and so on, so each number is used 3 times around the circle combine the equations and you get: 3(a1 + a2 ... + a10) < 17(10) but that works out to 165 < 170, which is fine. Anyone have any idea how to solve this problem? __________________ Fueled by oxytocin!

01-29-2004, 03:26 PM	#2 (permalink)
KnifeMissile Location: Waterloo, Ontario	You were on the right track but you didn't listen to the advice of the question. Try to use the previous lemma to prove this question. First, lets think about all the possible groups of these consequtive integers that are arranged around this circle. We want to show that there necessarily exists a group whose elements sum to a number greater than or equal to 17. So, because we're trying to prove a property of this set of groups (that there exists one with our special property), lets take a look at the nature of these groups, in general. So, lets ask the question "what is the average of each group's average?" This may sound like a funny question but it's easy enough to answer because each group is the same size. Therefore, the average of their averages is simply the average of all the different group's elements. If you are not convinced of this I'll leave this fact as an exercise for the reader. This is your homework, after all. You've established, yourself, that the sum of all the elements of all the groups is 165 and that there are 30 of them. So, that makes the average 165 / 30 = 5.5. This is not surprising since it is also the average of the consecutive integers 1 through 10. Now, I don't want to do your homework for you (you are supposed to learn this stuff) but you should be wondering how to apply your lemma (at least one element must be greater than the average) to this situation. Then the proof should become obvious to you. If you totally give up, come back and I will show you the answer. Good luck!

01-29-2004, 06:58 PM	#3 (permalink)
KnifeMissile Location: Waterloo, Ontario	Actually, I've been talking this over with my boss and there's a more direct way of proving it than what I was doing, although it's very much along the same lines. Instead of looking at an average of averages, simply examine the average of the sums of group elements and try to apply the lemma on that. It's equivialent to what I was suggesting but skips an uneccesary step. It seems like every time I find a way there's always a better one...