login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A066385 Smallest maximum of sum of 3 consecutive terms in any arrangement of [1..n] in a circle. 0

%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(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.

%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. 98-104.

%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.acmicpc-pacnw.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, 50-51.

%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 - (t-1)*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, 50-51.

%H ACM International Collegiate Programming Contest, Pacific Northwest Regional Contest, <a href="http://www.acmicpc-pacnw.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.bundeswettbewerb-mathematik.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. 98-104.

%H Timothy Rolfe, <a href="http://www.drdobbs.com/architecture-and-design/backtracking-algorithms/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. 83-84 [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(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.

%e a(6)=11 because the cycle 1-4-5-2-3-6- 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 = (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.

%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}[[n-2]], 3n + 5 - a[n - 1] ]; Table[a[n], {n, 3, 38}] (* _Jean-Fran├ž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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 4 01:54 EDT 2020. Contains 334812 sequences. (Running on oeis4.)