A162763 -id:A162763 - cp's OEIS frontend

A162761 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.

0, 2, 4, 9, 13, 20, 26, 35, 43, 54, 64, 77, 89, 104, 118, 135, 151, 170, 188, 209, 229, 252, 274, 299, 323, 350, 376, 405, 433, 464, 494, 527, 559, 594, 628, 665, 701, 740, 778, 819, 859, 902, 944, 989, 1033, 1080, 1126, 1175, 1223, 1274, 1324, 1377, 1429

Offset: 1

Do Zerg (daidodo(AT)gmail.com), Jul 13 2009

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

			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.
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.

Cf. A162762, A162763 and A162764 for the analog with elevator capacity of C = 2, 3 and 4 persons.

A162761(n)=(n^2+n)\2-1-bitand(n,n>1) \\ M. F. Hasler, Apr 29 2019

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

Edited and extended by M. F. Hasler, Apr 29 2019

A162764 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.

Original entry on oeis.org

0, 2, 4, 6, 8, 10, 12, 14, 16, 22, 26, 32, 36, 40, 44

Offset: 1

Do Zerg (daidodo(AT)gmail.com), Jul 13 2009

From Jon E. Schoenfield, Dec 21 2013, edited by M. F. Hasler, May 01 2019: (Start)
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:
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).
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.
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.
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.
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)
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
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
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
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

			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.
From _M. F. Hasler_, May 01 2019: (Start)
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).
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.
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.
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.
Analogous to n = 11, we have a(13) = a(12) + 4 = 36. (End)

For the same problem but with an elevator capacity C of 1, 2, or 3 persons, see A162761, A162762, and A162763, respectively.

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

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

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

Edited by Jon E. Schoenfield, Dec 02 2013

Edited by M. F. Hasler, May 01 2019

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.

Original entry on oeis.org

0, 2, 4, 6, 8, 14, 18, 22, 26, 34, 40, 46, 52, 62, 70, 78, 86

Offset: 1

Do Zerg (daidodo(AT)gmail.com), Jul 13 2009

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

			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)

Cf. A162761, A162763 and A162764 for analogs with capacity C = 1, 3 and 4.

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

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

Edited by M. F. Hasler, May 01 2019

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions