login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
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
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; text; internal format)
OFFSET

3,1

COMMENTS

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.

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 our joint article. (End)

From Jon E. Schoenfield, Jun 24 2019: (Start)

Observations:

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.

2. a(n) = f(n) for all even n > 6.

3. f(n)-1 <= a(n) <= f(n) for all odd n > 3.

Conjecture: for all odd n > 15, a(n) = f(n). (End)

From Jon E. Schoenfield, Jul 07 2019: (Start)

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):

If n mod 9 = 0 then let t = n/3 and u = n/9; for each k in 1..n,

p(k) = ceiling(n - (t + 1/2)*r - (3/2)*s) if s < 2*u,

1 + 3*s - (t-1)*r otherwise,

where r = k mod 3

and s = (floor(k/3) - 2*r*u) mod t.

If n mod 9 = 3 or 6 then let t = n/3; for each k in 1..n,

p(k) = ceiling(n - t*r - (3/2)*s) if s < 2*t/3,

1 + 3*s - t*r otherwise,

where r = k mod 3

and s = (floor(k/3) - ((t*(t mod 3) - 1)*r)/3) mod t.

If n mod 3 != 0 then for each k in 1..n,

p(k) = k+1 if k == n+1 (mod 3),

ceiling((n*(((k mod 3) mod 2) + 1) - k) / 2) otherwise.

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

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.

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)

REFERENCES

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, "Backtracking Algorithms", Dr. Dobb's Journal, Vol. 29, No. 5 (May 2004), pp. 48, 50-51.

LINKS

Table of n, a(n) for n=3..38.

ACM International Collegiate Programming Contest, Pacific Northwest Regional Contest, Problem E, then specifically, ACMContest/2002/Contest Problems/Final Versions/FinalContestFiles/e_CircPerm/.

Bundeswettbewerb Mathematik, Problem 2002 (1.4) [Broken link?]

Dean S. Clark, A Combinatorial Theorem on Circulant Matrices, American Mathematics Monthly, December 1985.

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 website, May 01 2004.

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]

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

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.

MATHEMATICA

(* *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" *)

CROSSREFS

Sequence in context: A070598 A262435 A124257 * A226913 A293826 A103092

Adjacent sequences: A066382 A066383 A066384 * A066386 A066387 A066388

KEYWORD

nice,nonn,more

AUTHOR

Rainer Rosenthal, 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, Jun 18 2009

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 06:16 EST 2022. Contains 358649 sequences. (Running on oeis4.)