|
%I #38 May 18 2019 19:36:24
%S 0,2,4,6,8,14,18,22,26,34,40,46,52,62,70,78,86
%N 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.
%C 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.
%C 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
%C 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
%F 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
%F 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
%e 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.
%e From _M. F. Hasler_, Apr 29 2019: (Start)
%e 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.
%e 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).
%e 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.
%e 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.
%e Again, the same solution "spaced out" between floor 4 and 5 yields a(9) = 26.
%e 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.
%e 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)
%o (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
%Y Cf. A162761, A162763 and A162764 for analogs with capacity C = 1, 3 and 4.
%K nonn,more
%O 1,2
%A Do Zerg (daidodo(AT)gmail.com), Jul 13 2009
%E Edited by _M. F. Hasler_, May 01 2019
|
