Circle of 10

Stump your fellow simians.
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Circle of 10

Post by DanishDynamite »

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?
ceptimus
Posts: 1462
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK

Post by ceptimus »

Usual spoiler box - select the text with your mouse, or press Ctrl-A 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 non-computer proof, but I can't think how to eliminate 26, 27 and 28 as possibilities, except by trial and error.

</td></tr></table>
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Post by DanishDynamite »

:)

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 "computer-like" 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".
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Post by DanishDynamite »

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.
ceptimus
Posts: 1462
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK

Post by ceptimus »

The beauty of the computer version, is that with less than a minute's work, it can be altered to deal with any ten numbers, or indeed many more than ten. :P


:D