login
A162762
Minimal number of floors an elevator must move to transport n passengers initially waiting at floors i = 1, ..., n to their destinations, floor n+1-i (= n, ..., 1), if the elevator can transport at most C = 2 persons at a time and starts at floor 1, and no one may get off the elevator before reaching their destination.
3
0, 2, 4, 6, 8, 14, 18, 22, 26, 34, 40, 46, 52, 62, 70, 78, 86
OFFSET
1,2
COMMENTS
If n is odd, the passenger at floor (n+1)/2 is already at his or her destination and does not need to be transported.
Without the additional constraint that no passenger may (temporarily) get off before reaching his or her destination, there would be smaller solutions, cf. example section and A162761 and A162764. - M. F. Hasler, May 01 2019
An upper bound is provided by the following simple algorithm: Transport the first C persons to the last C floors, then those there down to the first C floors; if not finished, go to floor C+1, consider this as the new ground floor and start over with the same algorithm for n' = n - 2*C. This gives a(n) <= 2n - 2 + C + a(n - 2C) for n > 2C+1; a(n) = 2n - 2 otherwise. For C = 2, this upper bound coincides with all known terms, and yields the same sequence as the g.f. proposed in 2014. For C > 2, it needs an adjustment for n = 2C + {2,3}, cf. A162763 and A162764. - M. F. Hasler, May 15 2019
FORMULA
Empirical g.f.: 2*x^2*(x^2-x+1)*(x^3-x-1) / ((x-1)^3*(x+1)*(x^2+1)). - Colin Barker, Jun 21 2014
a(n) = 2n - 2 for n < 2C + 2, a(n) <= 2n - 2 + C + a(n - 2C) otherwise, with equality for all known terms and the above g.f. - M. F. Hasler, May 15 2019
EXAMPLE
For n = 2, the value a(2) = 2 means the elevator needs to move only 2 floors to transport everyone to their destinations: the elevator loads the person at floor 1 and moves to floor 2 (up 1 floor), unloads and loads one person at floor 2, then moves to floor 1 (down 1 floor) and unloads.
From M. F. Hasler, Apr 29 2019: (Start)
Up to n = 5, we have a(n) = 2(n-1) since the passengers on the lower half can all be loaded and moved to their destinations as the elevator travels up to floor n, and then similarly for the remaining passengers as the elevator travels back down to floor 1.
For n = 6 we can take the passengers from floors 1 and 2 to their destinations (moving 5 floors up), then those at floors 6 and 5 (moving 5 floors down), then take the person at floor 3 to floor 4 (+ 2 + 1 floor) and finally take person 4 to floor 3, for a total of a(6) = 14 floors. One can check that there is no faster solution, unless one allows a passenger to get off and on again. E.g., having picked up the persons at floor 6 and 5, one could drop off person 5 at floor 3 (after 5 + 3 floors moved), take person 3 to floor 4 and person 4 to floor 3 (+ 2 floors), and finally person 5 and 6 to floor 2 and 1 (+ 2 floors), for a total of only 5 + 3 + 2 + 2 = 12 < a(6).
For n = 7 we can keep the same plan, inserting an additional floor where the elevator never will stop in the middle between floors 3 and 4. This adds 4 floors to the total distance, for a(7) = 18.
For n = 8, one solution is to go 1 -> 8 -> 1 -> 6 -> 3 (loading and dropping passengers whenever possible) for a total of a(8) = 7 + 7 + 5 + 3 = 22.
Again, the same solution "spaced out" between floor 4 and 5 yields a(9) = 26.
For n = 10, doing 1 -> 10 -> 1 -> 8 -> 3 -> 6 -> 5 yields a(10) = 9 + 9 + 7 + 5 + 3 + 1 = 34. Then again, a(11) = a(10) + 6 = 40.
For n = 12, doing 1 -> 12 -> 1 -> 10 -> 3 -> 8 -> 5 yields a(12) = 11 + 11 + 9 + 7 + 5 + 3 = 46, and a(13) = a(12) + 6 = 52. (End)
PROG
(PARI) A162762(n, C=2)=2*n-2+if(n\2>C, A162762(n-2*C)+C) \\ Proved to be an upper bound (cf. comments), only conjectured to be exact for all n. - M. F. Hasler, May 15 2019
CROSSREFS
Cf. A162761, A162763 and A162764 for analogs with capacity C = 1, 3 and 4.
Sequence in context: A173144 A356702 A005250 * A156097 A288793 A049015
KEYWORD
nonn,more
AUTHOR
Do Zerg (daidodo(AT)gmail.com), Jul 13 2009
EXTENSIONS
Edited by M. F. Hasler, May 01 2019
STATUS
approved