|
%I #41 Aug 01 2022 22:01:00
%S 0,2,4,9,13,20,26,35,43,54,64,77,89,104,118,135,151,170,188,209,229,
%T 252,274,299,323,350,376,405,433,464,494,527,559,594,628,665,701,740,
%U 778,819,859,902,944,989,1033,1080,1126,1175,1223,1274,1324,1377,1429
%N 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.
%C 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
%F 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
%e 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.
%e 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.
%o (PARI) A162761(n)=(n^2+n)\2-1-bitand(n,n>1) \\ _M. F. Hasler_, Apr 29 2019
%Y Cf. A162762, A162763 and A162764 for the analog with elevator capacity of C = 2, 3 and 4 persons.
%K nonn,more
%O 1,2
%A Do Zerg (daidodo(AT)gmail.com), Jul 13 2009
%E Edited and extended by _M. F. Hasler_, Apr 29 2019
|
