%I
%S 6,9,10,11,14,15,16,18,20,21,23,24,25,27,29,30,32,33,35,36,38,39,41,
%T 42,44,45,47,48,50,51,53,54,56,57,59,60
%N Smallest maximum of sum of 3 consecutive terms in any arrangement of [1..n] in a circle.
%C In a problem in the "Bundeswettbewerb 2002" competition there are 12 sticks of lengths 1,...,12 placed in a circle 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 ceiling(3*(n+1)/2), since n*a(n) >= Sum_{i=1..n} (p(i1)+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.
%C From Timothy Rolfe (trolfe(AT)ewu.edu), Jan 24 2010: (Start)
%C Here is the chronology of the clockface problem:
%C 1. Dean S. Clark, "A Combinatorial Theorem on Circulant Matrices," American Mathematics Monthly, December 1985.
%C 2. Martin Gardner's August 1986 column for Isaac Asimov's Science Fiction Magazine, which posed the problem of finding all legal permutations.
%C 3. Timothy Rolfe, "Recurse Around the Clock", Mathematics and Computer Education, Vol. 21, No. 2 (Spring, 1987), pp. 98104.
%C 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.acmicpcpacnw.org/ProblemSet/2002/forweb.zip  specifically, ACMContest/2002/Contest Problems/Final Versions/FinalContestFiles/e_CircPerm/
%C 5. Timothy Rolfe, "Backtracking Algorithms", Dr. Dobb's Journal, Vol. 29, No. 5 (May 2004), pp. 48, 5051.
%C 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 our joint article. (End)
%C From _Jon E. Schoenfield_, Jun 24 2019: (Start)
%C Observations:
%C 1. If we define f(n) = ceiling((3/2)*n) + 3, then a(n) = f(n) for all n < 39 except 3, 5, 6, 9, and 15.
%C 2. a(n) = f(n) for all even n > 6.
%C 3. f(n)1 <= a(n) <= f(n) for all odd n > 3.
%C Conjecture: for all odd n > 15, a(n) = f(n). (End)
%C From _Jon E. Schoenfield_, Jul 07 2019: (Start)
%C If f(n) is defined as above, then for all n >= 3, the following steps generate a permutation p of 1..n such that the maximum of the consecutive triple sums does not exceed f(n):
%C If n mod 9 = 0 then let t = n/3 and u = n/9; for each k in 1..n,
%C p(k) = ceiling(n  (t + 1/2)*r  (3/2)*s) if s < 2*u,
%C 1 + 3*s  (t1)*r otherwise,
%C where r = k mod 3
%C and s = (floor(k/3)  2*r*u) mod t.
%C If n mod 9 = 3 or 6 then let t = n/3; for each k in 1..n,
%C p(k) = ceiling(n  t*r  (3/2)*s) if s < 2*t/3,
%C 1 + 3*s  t*r otherwise,
%C where r = k mod 3
%C and s = (floor(k/3)  ((t*(t mod 3)  1)*r)/3) mod t.
%C If n mod 3 != 0 then for each k in 1..n,
%C p(k) = k+1 if k == n+1 (mod 3),
%C ceiling((n*(((k mod 3) mod 2) + 1)  k) / 2) otherwise.
%C (The maximum of the resulting consecutive triple sums is equal to f(n) for all n >= 3 except at n = 3, 6, 9, and 15; at those values of n, that maximum is less than f.)
%C It is not difficult to prove that, for even values of n > 6, a(n) >= (3/2)*n + 3; that lower bound, together with the upper bound provided by the steps above, demonstrates that a(n) = (3/2)*n + 3 for all even n > 6.
%C It seems to me that there should be a way to prove that, for all odd values of n > 15, a(n) must exceed (3/2)*n + 5/2. If such a proof were found, then it, together with the upper bound provided by the steps above, would demonstrate that a(n) = (3/2)*n + 7/2 for all odd n > 15, and thus a(n) = f(n) = ceiling((3/2)*n) + 3 for all n > 15. (End)
%D de.sci.mathematik, Thread "Zahlenkreis", December 2001
%D Martin Gardner's August 1986 column for Isaac Asimov's Science Fiction Magazine, which posed the problem of finding all legal permutations.
%D Timothy Rolfe, "Backtracking Algorithms", Dr. Dobb's Journal, Vol. 29, No. 5 (May 2004), pp. 48, 5051.
%H ACM International Collegiate Programming Contest, Pacific Northwest Regional Contest, <a href="http://www.acmicpcpacnw.org/ProblemSet/2002/forweb.zip">Problem E</a>, then specifically, ACMContest/2002/Contest Problems/Final Versions/FinalContestFiles/e_CircPerm/.
%H Bundeswettbewerb Mathematik, <a href="http://www.bundeswettbewerbmathematik.de/aufgaben/aufgaben.htm">Problem 2002 (1.4)</a> [Broken link?]
%H Dean S. Clark, <a href="http://www.jstor.org/stable/2323225">A Combinatorial Theorem on Circulant Matrices</a>, American Mathematics Monthly, December 1985.
%H Timothy Rolfe, <a href="http://dl.acm.org/citation.cfm?id=34818">Recurse Around the Clock</a>, Mathematics and Computer Education, Vol. 21, No. 2 (Spring, 1987), pp. 98104.
%H Timothy Rolfe, <a href="http://www.drdobbs.com/architectureanddesign/backtrackingalgorithms/184405652">Backtracking Algorithms</a>, Dr. Dobb's website, May 01 2004.
%H T. J. Rolfe and P. W. Purdom, <a href="http://dx.doi.org/10.1145/1044550.1041664">An Alternative Problem for Backtracking and Bounding</a>, Bulletin of the ACM SIG on Computer Science Education, Vol. 36, No. 4 (December 2004), pp. 8384 [From Milan Stefanovic (stefke381(AT)gmail.com), Nov 19 2008]
%F Let p be a permutation of 1..n and let g(p) be the maximum of the consecutive triple sums p(i1)+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.
%e a(6)=11 because the cycle 145236 has sums 11,10,11,10,11,10 with max=11, and there is no cycle that yields a smaller maximum.
%e This example by Helmut Richter shows that a(14) = 24 is very likely: p = (1811491021256133714) with g(p) = 11+4+9 = 24 as maximal threesum.
%t (* *Warning* This is a heuristic program. Output data are not reliable beyond a(38) *) a[n_] := a[n] = If[n < 17, {6, 9, 10, 11, 14, 15, 16, 18, 20, 21, 23, 24, 25, 27}[[n2]], 3n + 5  a[n  1] ]; Table[a[n], {n, 3, 38}] (* _JeanFrançois Alcover_, Mar 13 2016, using "FindSequenceFunction" *)
%K nice,nonn,more
%O 3,1
%A _Rainer Rosenthal_, Dec 23 2001
%E 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
%E Broken link corrected by _Rainer Rosenthal_, Jun 18 2009
