A078476 Time taken to get n people from one side of a bridge to the other where (a) the only flashlight must be carried when crossing; (b) only one or two people may cross at the same time; (c) a pair crosses at the speed of the slowest member; and (d) the k-th person's speed requires k seconds to cross the bridge.

1, 2, 6, 11, 16, 22, 28, 35, 42, 50, 58, 67, 76, 86, 96, 107, 118, 130, 142, 155, 168, 182, 196, 211, 226, 242, 258, 275, 292, 310, 328, 347, 366, 386, 406, 427, 448, 470, 492, 515, 538, 562, 586, 611, 636, 662, 688, 715, 742, 770, 798, 827, 856, 886, 916, 947

Offset

1,2

Comments

Quasipolynomial of order 2. - Charles R Greathouse IV, Mar 26 2013

Links

Table of n, a(n) for n=1..56.

Torsten Sillke, Crossing the bridge.

Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).

Formula

For n>1: a(n)=n^2/4+3n-5+((-1)^n-1)/8.

G.f.: x*(1+2*x^2+x^3-3*x^4)/((1-x)^3*(1+x)). [Colin Barker, Jun 07 2012]

Contribution from Denis Borris, Mar 26 2013: (Start)

n is even: a(n) = (n^2 + 12n - 20) / 4.

n is odd : a(n) = (n^2 + 12n - 21) / 4.

(End)

Example

a(5)=16 since one of the fastest ways is for 1&2 to cross (time 2), 1 to return (1), 4&5 to cross (5), 2 to return (2), 1&3 to cross (3), 1 to return (1) and 1&2 to cross (2) for a total time of 2+1+5+2+3+1+2=16.

Prog

(PARI) a(n)=n^2\4+3*n-5 \\ Charles R Greathouse IV, Mar 26 2013

Crossrefs

Sequence in context: A020966 A193910 A215918 * A217687 A212459 A099056

Adjacent sequences: A078473 A078474 A078475 * A078477 A078478 A078479

Keyword

nonn,easy

Author

Henry Bottomley, Jan 03 2003

Status

approved