|
| |
|
|
A066385
|
|
Smallest maximum of sum of 3 consecutive terms in any arrangement of [1..n] in a circle.
|
|
0
| |
|
|
6, 9, 10, 11, 14, 15, 16, 18, 20, 21, 23, 24, 25, 27, 29, 30, 32, 33, 35, 36, 38, 39, 41, 42, 44, 45, 47, 48, 50, 51, 53, 54, 56, 57, 59, 60
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 3,1
|
|
|
COMMENTS
| In a problem in the "Bundeswettbewerb 2002" competition there are 12 sticks of lengths 1,..,12 put in a ring in random order. It has to be proved that there are at least 3 consecutive sticks with total length not less than 20. A closer look shows that the total length is at least a(12)=21. The problem of the contest is a consequence of the following observation: every term a(n) is at least ceil(3*(n+1)/2), since n*a(n) >= sum{i=1..n}(p(i-1)+p(i)+p(i+1)) = 3*sum{i=1..n}(i) =3*n*(n+1)/2. So in the case n=12 we have (total length) >= a(12)=21 >= 20.
Comment from Timothy Rolfe (trolfe(AT)ewu.edu), Jan 24 2010: (Start)
Here is the chronology of the clockface problem:
1. Dean S. Clark, "A Combinatorial Theorem on Circulant Matrices," American Mathematics Monthly, December 1985.
2. Martin Gardner's August 1986 column for Isaac Asimov's Science Fiction Magazine, which posed the problem of finding all legal permutations.
3. Timothy Rolfe, "Recurse Around the Clock", Mathematics and Computer Education, Vol. 21, No. 2 (Spring, 1987), pp. 98-104.
4. In the Pacific Northwest regional contest as part of the ACM International Collegiate Programming Contest, the problem was problem E. Navigate from http://www.acmicpc-pacnw.org/ProblemSet/2002/forweb.zip --- specifically, ACMContest/2002/Contest Problems/Final Versions/FinalContestFiles/e_CircPerm/
5. Timothy Rolfe, "Backtracking Algorithms", Dr. Dobb's Journal, Vol. 29, No. 5 (May 2004), pp. 48, 50-51.
It was [5] that caused Paul W. Purdom, Jr., of Indiana University, Bloomington, to correspond with me, proposing a bounding function. This is what that generated are joint article. (End)
|
|
|
REFERENCES
| ACM International Collegiate Programming Contest, Pacific Northwest Regional Contest, Problem E. Navigate from http://www.acmicpc-pacnw.org/ProblemSet/2002/forweb.zip --- specifically, ACMContest/2002/Contest Problems/Final Versions/FinalContestFiles/e_CircPerm/
Dean S. Clark, "A Combinatorial Theorem on Circulant Matrices," American Mathematics Monthly, December 1985.
de.sci.mathematik, Thread "Zahlenkreis", December 2001
Martin Gardner's August 1986 column for Isaac Asimov's Science Fiction Magazine, which posed the problem of finding all legal permutations.
Timothy Rolfe, "Recurse Around the Clock", Mathematics and Computer Education, Vol. 21, No. 2 (Spring, 1987), pp. 98-104.
Timothy Rolfe, "Backtracking Algorithms", Dr. Dobb's Journal, Vol. 29, No. 5 (May 2004), pp. 48, 50-51.
T. J. Rolfe and P. W. Purdom, "An Alternative Problem for Backtracking and Bounding", Bulletin of the ACM SIG on Computer Science Education, Vol. 36, No. 4 (December 2004), pp. 83-84 [From Milan Stefanovic (stefke381(AT)gmail.com), Nov 19 2008]
|
|
|
LINKS
| Bundeswettbewerb Mathematik, Problem 2002 (1.4)
|
|
|
FORMULA
| Let p be a permutation of 1..n and let g(p) be the maximum of the consecutive triple sums p(i-1)+p(i)+p(i+1), where p(0)=p(n) and p(n+1)=p(1). a(n) is the minimum of all the g(p) taken over all permutations p.
|
|
|
EXAMPLE
| a(6)=11 because cycle 1-4-5-2-3-6- has sums 11,10,11,10,11,10 with max=11.
This example by Helmut Richter shows that a(14) = 24 is very likely: p = (1-8-11-4-9-10-2-12-5-6-13-3-7-14-) with g(p) = 11+4+9 = 24 as maximal three-sum.
|
|
|
CROSSREFS
| Sequence in context: A140052 A070598 A124257 * A103092 A104523 A091886
Adjacent sequences: A066382 A066383 A066384 * A066386 A066387 A066388
|
|
|
KEYWORD
| nice,nonn
|
|
|
AUTHOR
| Rainer Rosenthal (r.rosenthal(AT)web.de), Dec 23 2001
|
|
|
EXTENSIONS
| Terms a(1) - a(20) are from the cited reference. The rest, a(21) - a(38) are obtained using the program from the same reference. Milan Stefanovic (stefke381(AT)gmail.com), Nov 19 2008
Broken link corrected by Rainer Rosenthal (r.rosenthal(AT)web.de), Jun 18 2009
|
| |
|
|
