Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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