|
%I #58 May 19 2019 03:58:27
%S 0,2,4,6,8,10,12,14,16,22,26,32,36,40,44
%N Minimal total number of floors that an elevator must move to get n persons waiting, respectively, on floors i = 1, 2, ..., n, to their destination floors n-i+1 (= n, n-1, ..., 1), if the elevator can hold up to C = 4 persons at a time and starts at floor 1, and no passenger may get off the elevator before reaching his destination.
%C From _Jon E. Schoenfield_, Dec 21 2013, edited by _M. F. Hasler_, May 01 2019: (Start)
%C For n > 1, let k = floor((n-2)/(2*C)); the following simple algorithm for transporting persons to floors demonstrates an upper bound of a(n) <= 2*(k+1)*(n-1-C*k), if passengers were allowed to get temporarily off the elevator:
%C 1. If n is odd, then disregard the person on the ((n+1)/2)-th floor (since that person's current floor and destination floor are the same).
%C 2. Move the elevator in a series of 2*k+1 passes in alternating directions; on the p-th pass, move the elevator by (-1)^(p+1)*(n-1-(p-1)*C) floors (i.e., move up by n-1 floors on the 1st pass, down by n-1-C floors on the 2nd pass, up by n-1-2*C floors on the 3rd pass, down by n-1-3*C floors on the 4th pass, etc.). (As a result, the p-th pass will end at the floor numbered (n+1)/2 + C/4 + (-1)^(p+1)*((n-1)/2 + C/4 - p*C/2).) At each of the first C floors of each pass (or until there are no more persons to be moved in that direction), load the person who is waiting to be taken to a floor in the direction in which the elevator will be moving during the current pass. Unload each passenger when his or her destination floor is reached. Before beginning each subsequent upward pass, unload all remaining passengers at the current floor.
%C 3. Make a final downward pass to Floor 1, loading each waiting person when the floor at which he or she is waiting is reached, and unloading each passenger at his or her destination floor.
%C For example, at C = 4 and n = 10, first (going up 9 floors), load persons waiting at Floors 1 through 4 and unload each at his or her destination floor until Floor 10 is reached. Next (going down 5 floors), load persons waiting at Floors 10 through 7 and (temporarily) unload them at Floor 5. Then (going up 1 floor), load the remaining person at Floor 5, and unload him or her at Floor 6. Then, on the final downward pass (going down 5 floors), load the person waiting at Floor 6, unload him or her at Floor 5, reload the four remaining persons waiting there, and unload them at Floors 4 through 1. Total number of floors moved: 9+5+1+5=20. In this example, k = floor((n-2)/(2*C)) = 1, and 2*(k+1)*(n-1-C*k) = 20.
%C That this upper bound 2*(k+1)*(n-1-C*k) is less than a(n) for n > 9 shows that the sequence is defined using the following additional constraint. (End)
%C Additional constraint (tacitly implied by the sequence's author but not stated in the original version): "No passenger can be unloaded from the elevator at any floor other than his or her final destination floor." Are all the existing terms (through a(15) = 44) correct if this constraint is added to the problem? The same question applies to the existing terms of A162761, A162762, and A162763. - _Jon E. Schoenfield_, Dec 28 2013
%C All of the sequences A162761 through A162764 use this additional rule. This is seen easily at 162761(4) = 8. See respective comment and example sections. - _M. F. Hasler_, May 01 2019
%C The simple algorithm of taking the first C (or [n/2] if less) persons up to their destinations, then the last C persons down to their destinations, and if not finished, starting over with floor C+1 as new ground floor with n' = n - 2C, yields an upper bound a(n) <= 2n - 2 + C + a(n - 2C) for n > 2C + 1. In the example section we show that this is not optimal for n = 10 and 11, i.e., 2C + 2 and 2C + 3. I conjecture, however, that this upper bound is sharp (i.e., yields the exact result) for all n > 2C + 3. More precisely, I think the assumption of strict inequality for some larger value of n (the smallest such index) gives a proof by contradiction. - _M. F. Hasler_, May 15 2019
%C It would be nice to have a program explore all possible/relevant solutions to get an independent check and maybe extension of the given data. - _M. F. Hasler_, May 15 2019
%F a(n) = 2n - 2 for n < 2C + 2 = 10, a(n) <= 2n - 2 + C + a(n - 2C) for n > 2C + 1 (cf. comments for proof), with equality for all known values except n = 10 & 11 where a(n) = 4n - 18; conjectured to be exact for all n > 2C + 3 = 11. - _M. F. Hasler_, May 15 2019
%F G.f.: 2*x*(1 + x^8 - x^9 + x^10 - x^11)/((1 - x)^3*(1 + x)*(1 + x^2)*(1 + x^4)) (conjectured). - _M. F. Hasler_, May 15 2019
%e a(2)=2 because at n=2 the elevator needs to move a total of only 2 floors to transport everyone to his or her destination: the elevator loads the person at floor 1, moves to floor 2 (a move of 1 floor), unloads, loads the person at floor 2, moves to floor 1 (another move of 1 floor), and unloads.
%e From _M. F. Hasler_, May 01 2019: (Start)
%e Up to n = 2*C+1 = 9 here, one may simply load all passengers in the lower half, deposit them at their destinations on the way up to floor n, then load the passengers in the upper half and deposit them at their destinations on the way down to floor 1, for a total of a(n) = 2(n-1) moves. From n = 10 on, a(n) > 2(n-1).
%e For n = 10, the smallest solution which does not require a person to get off before their final destination and back in the elevator at a later time is the following: we can transport persons waiting on floors 1 through 4 to their destination floors 7 through 10, then load those waiting on floors 10, 9, 8 and 7, deposit the last one at floor 4 (9 + 6 floors moved so far), transport the person from floor 5 to floor 6 (+ 2 floors moved), then the one at floor 6 and the other three passengers to their destinations at floors 5, 3, 2 and 1 (+ 5 floors), for a total of 9 + 6 + 2 + 5 = 22 moves. It seems impossible to solve the problem in fewer moves unless one allows a passenger to get out and later in again.
%e For n = 11 we can follow the same plan, inserting an additional floor, where the elevator never stops, between the 5th and 6th floor. This adds 4 more floors to the total distance, for a(11) = a(10) + 4 = 26.
%e For n = 12 we transport 4 passengers up to floor 12, then drop passengers 8 and 9 at floors 4 & 3, move passengers 5 & 6 to floors 7 & 8, then take remaining passengers down to their destinations on the way to floor 1. (We always load a passenger whenever we can.) This takes a(12) = 11 + 9 + 5 + 7 = 32 floors.
%e Analogous to n = 11, we have a(13) = a(12) + 4 = 36. (End)
%o (PARI) A162764(n,C=4)=2*n-2+if(n>2*C+3,A162764(n-2*C,C)+C,n>2*C+1,2*n-4*C) \\ Proved to be an upper bound (cf. comments); conjectured to be exact for all n. - _M. F. Hasler_, May 15 2019
%Y For the same problem but with an elevator capacity C of 1, 2, or 3 persons, see A162761, A162762, and A162763, respectively.
%K nonn,more
%O 1,2
%A Do Zerg (daidodo(AT)gmail.com), Jul 13 2009
%E Edited by _Jon E. Schoenfield_, Dec 02 2013
%E Edited by _M. F. Hasler_, May 01 2019
|
