How to do Proofs?

Question

I've been given this proof, and am really just lost. I dont know where to start and hope some one could explain as to how this should be done.

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

Answer 1

Unfortunately, there is no general method for doing proofs. If there was, the job of being a mathemtician would be easy. You really just have to think about all the different things you can do to get the type of information you want.

For this one, you know that there are 10 such triples of consecutive locations, and so there are 10 such sums. What happens when you add up all these 10 sums (each of which is a sum of three numbers)? [This was the trick, by the way] What does that say about the size of at least one sum of three?

Answer 2

r_k_stanley is correct but I offer a shorter similar proof. It is also by contradiction meaning that I will try to place numbers so no triple sums to 17. The numbers 10, 9, and 8 give me trouble becaused any two of them sum to 17 or more so I must have 2 spaces between them. This gives a pattern (X for the numbers and 0 for spaces) of:

X 0 0 X 0 0 X 0 0 0

My next problem is placing the 7, if it is within 2 places of either the 10 or the 9 it will sum to 16 or more and the third digit in the sum, whatever it is, will push the sum to 17. Therefore, the 7 can be within 2 spaces of the 8 but not within two of the 9 or 10. The only possible place is the last space in the diagram above. Any other place is within two spaces of two of the already placed numbers. Also the nearby
number (first place in the diagram) must be 8. Now I have:

8 0 0 X 0 0 X 0 0 7

To keep the triple that includes 7 and 8 from reaching 17, I can only use a 1. However, I need a number on either side of the 7 and 8. I only have a single 1 so must use a 2 on the other side. This is the best I can do but the 2 gives 7 + 8 +2 = 17 so I cannot avoid a minimum sum of 17 completing the proof.

Answer 3

Proof by contradiction:

Suppose there were a circle in which every three consecutive integers had a sum of 16 or less.

An integer is present in different three sums:

With each integer on either side.
With the two integers to the left.
With the two integers to the right.

Consider the integer 10.

SPACE-SPACE-10-SPACE-SPACE

The four spaces need to be filled with different integers, the biggest of which may be 5, in order for the sum of three to be 16 or less.

Also, each pair of integers either side of the 10 must have a sum no greater than 6. Therefore the sum of the integers that fill the four spaces is no greater than 12.

If we must select four integers from the range 1-5 that have a total of 12 or less, the number we reject must be 3, 4 or 5.

Now consider the 9.

SPACE-SPACE-9-SPACE-SPACE.

It is possible for the spaces on one side of the 9 to overlap those on the other side of the 10, but this cannot happen on both sides, because the ring would then contain only six integers.

Therefore we have

9-SPACE-SPACE,

where the integers occupying the spaces are different from those occupy the two spaces on either side of the 10.

The sum of the integers occupying the two spaces beside the 9 must be 7 or less.

What numbers do we have to choose from?

6, 7, 8 and only one of 3, 4, and 5.

Since we cannot use both 3 and 4, it is impossible to choose a pair with a total of 7 or less.

This proves that it is impossible to construct a circle in which the sum of any three consecutive integers is 16 or less.

Therefore, when the first ten positive integers are placed around a circle, there will exist three consecutive integers with a sum greater than or equal to 17.

Answer 4

Assume no three integers in consecutive positions total 17 or more.
Then every such set totals a maximum of 16.
There are 10 such sets, and the total of these 10 sets is 160 or less......(1)
In totalling the 10 sets, every integer from 1 to 10 has been used exactly 3 times.
In reality, the integers from 1 to 10 total (1+10)10/2 = 55, and therefore added 3 times over they total 165......(2)
(1) and (2) contradict, and the original assumption is therefore wrong.