A162761 Minimal total number of floors an elevator must move to transport n people initially waiting at floors i = 1, ..., n to their destination floors n-i+1 (= n, ..., 1), when the elevator can hold at most one person at a time and starts at floor 1, and no passenger may get off the elevator before reaching his/her destination.

0, 2, 4, 9, 13, 20, 26, 35, 43, 54, 64, 77, 89, 104, 118, 135, 151, 170, 188, 209, 229, 252, 274, 299, 323, 350, 376, 405, 433, 464, 494, 527, 559, 594, 628, 665, 701, 740, 778, 819, 859, 902, 944, 989, 1033, 1080, 1126, 1175, 1223, 1274, 1324, 1377, 1429

Offset: 1

Author

Do Zerg (daidodo(AT)gmail.com), Jul 13 2009

Keywords

• nonn
• more

Comments

The value a(4) = 9 shows that it is not allowed to unload a passenger before he reaches his destination, cf. examples. This implies that there is no better solution than to transport person 1 to floor n, then person n to floor 1, then person 2 to floor n-1, then person n-1 to floor 2, etc., which yields a(n) = (Sum_{i=1..floor(n/2)} (n+1 - 2*i)*2 + 1) - 1 (for n > 1), equal to the formula conjectured by C. Barker. It would be interesting to consider the variant of optimal solutions involving temporary drop-off of passengers. - M. F. Hasler, Apr 29 2019

Examples

			For n = 3, the elevator must transport person 1 from floor 1 to floor 3 (2 floors) and then person 3 back to floor 1 (+ 2 more floors to go), whence a(3) = 4.
For n = 4, the limited capacity comes into play. The elevator could transport person 1 to floor 2 (1 floor moved), unload person 1 and take person 2 to floor 3 (+ 1 floor), take person 3 to floor 2 (+ 1 floor), take person 1 to floor 4 (+ 2 floors), and take person 4 to floor 1 (+ 3 floors), for a total of 8 floors moved. It appears that this solution, involving a person getting out and back in again, is excluded, and we need to transport, e.g., 1 -> 4, 4 -> 1, 2 -> 3, 3 -> 2, for a total of a(4) = 3 + 3 + 1 + 1 + 1 = 9 floors.
		

Crossrefs

Cf. A162762, A162763 and A162764 for the analog with elevator capacity of C = 2, 3 and 4 persons.

Programs

PARI

A162761(n)=(n^2+n)\2-1-bitand(n,n>1) \\ M. F. Hasler, Apr 29 2019

Formula

a(n) = (n^2 + n + (-1)^n - 3)/2 for n > 1. a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4) for n > 4. G.f.: x^2*(2+x^2-x^3)/((1-x)^3*(1+x)). - Conjectured by Colin Barker, Jun 10 2012, edited and proved by M. F. Hasler, Apr 29 2019

Extensions

Edited and extended by M. F. Hasler, Apr 29 2019