For some unknown reason, ceptimus has written the following numbers on 10 pieces of paper: 1, 3, 4, 5, 7, 9, 11, 13, 15, and 17. Ceptimus now arranges the 10 pieces of paper in a circle such that the highest sum S of any three adjacent numbers is as small as possible.
How small can S get? Need I say, prove it?
Circle of 10

 Posts: 1462
 Joined: Wed Jun 02, 2004 11:04 pm
 Location: UK
Usual spoiler box  select the text with your mouse, or press CtrlA to view it.
<table bgcolor="white"><tr><td>
The lowest 'highest sum' I could obtain was 29 using this configuration (the top row shows the order of paper pieces, and the bottom row the totals).
<pre> 1 3 11 13 4 9 15 5 7 17<br> 21 15 27 28 26 28 29 27 29 25</pre>Needless to say, I used a program to solve it. It took 20 minutes to write the program, and less than a second to run it. Barring bugs in my program, this constitutes a proof, as the program tried all possible arrangements. It's not a very satisfying proof though.
Since each paper number appears in three totals, we know that the sum of the totals will be three times the sum of the paper numbers which is 255. Dividing this across the ten totals gives 25.5 as the 'average total'. As there are no fractions present, 26 is clearly the lowest target we could aim for. There's the start of a noncomputer proof, but I can't think how to eliminate 26, 27 and 28 as possibilities, except by trial and error.
</td></tr></table>
<table bgcolor="white"><tr><td>
The lowest 'highest sum' I could obtain was 29 using this configuration (the top row shows the order of paper pieces, and the bottom row the totals).
<pre> 1 3 11 13 4 9 15 5 7 17<br> 21 15 27 28 26 28 29 27 29 25</pre>Needless to say, I used a program to solve it. It took 20 minutes to write the program, and less than a second to run it. Barring bugs in my program, this constitutes a proof, as the program tried all possible arrangements. It's not a very satisfying proof though.
Since each paper number appears in three totals, we know that the sum of the totals will be three times the sum of the paper numbers which is 255. Dividing this across the ten totals gives 25.5 as the 'average total'. As there are no fractions present, 26 is clearly the lowest target we could aim for. There's the start of a noncomputer proof, but I can't think how to eliminate 26, 27 and 28 as possibilities, except by trial and error.
</td></tr></table>

 Posts: 2608
 Joined: Mon Jun 07, 2004 4:58 pm
 Location: Copenhagen
:)
Your answer is of course correct, ceptimus. I arrived at the same answer in less than 20 minutes just using a pen and paper. My problem was how to prove it. I finally managed to do so in a very "computerlike" and inelegant manner. Turns out there is a very short, very simple, very elegant method of proving it. 4 lines of text.
In the voice of Monsiour Poirot: "All shall be revealed tomorrow".
Your answer is of course correct, ceptimus. I arrived at the same answer in less than 20 minutes just using a pen and paper. My problem was how to prove it. I finally managed to do so in a very "computerlike" and inelegant manner. Turns out there is a very short, very simple, very elegant method of proving it. 4 lines of text.
In the voice of Monsiour Poirot: "All shall be revealed tomorrow".

 Posts: 2608
 Joined: Mon Jun 07, 2004 4:58 pm
 Location: Copenhagen
Well, if you do not wish to see the elegant little proof, do not read any further.
The smallest sum possible S is 29. One possible configuration is the following: 1  9  15  4  5  17  7  3  13  11. The sum of the 9 numbers to the right of the 1 is 84. This will always be true irregardless of configuration. The 9 numbers can be divided into 3 sums of 3 consecutive numbers. The average of these sums is 84/3 = 28. At least one of these sums consists of all odd numbers. Therefore at least one sum must be 29 or more.
QED.
The smallest sum possible S is 29. One possible configuration is the following: 1  9  15  4  5  17  7  3  13  11. The sum of the 9 numbers to the right of the 1 is 84. This will always be true irregardless of configuration. The 9 numbers can be divided into 3 sums of 3 consecutive numbers. The average of these sums is 84/3 = 28. At least one of these sums consists of all odd numbers. Therefore at least one sum must be 29 or more.
QED.

 Posts: 1462
 Joined: Wed Jun 02, 2004 11:04 pm
 Location: UK