OFFSET
1,2
COMMENTS
Equivalently, the distance (or number of edges) a taxicab must drive to transport n people initially standing at km (or vertex) i (= 1, ..., n) to their destinations at km n-i+1, when the taxi can hold at most 3 passengers, and starts at km 1.
In case of odd n, the person at the middle floor (n+1)/2 is already at her destination and does not need to be transported.
The simple algorithm of taking the first C (or [n/2] if less) persons up to their destination, then the last C persons down to their destination, 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 = 8 and 9, 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
FORMULA
a(n) = 2n - 2 for n < 2C + 2 = 8, a(n) <= 2n - 2 + C + a(n - 2C) else, see comment for proof. Conjectured to hold with equality for all n except n = 2C + {2, 3} = {8, 9} where a(n) = 4(n - C) - 2 = 4n - 14. - M. F. Hasler, May 15 2019
G.f.: x*(2 + 2*x^6 - 2*x^7 + x^8 - x^9)/((1 - x)^3*(1 + x)*(1 - x + x^2)*(1 + x + x^2)) (conjectured). - M. F. Hasler, May 15 2019
EXAMPLE
For n = 2, the term a(2) = 2 means the elevator needs to move only 2 floors to transport everyone to his or her destination: the elevator loads one person at floor 1, and moves to floor 2 (up 1 floor), unloads one person and loads another person, then moves back to floor 1 (down 1 floor) and unloads.
From M. F. Hasler, May 01 2019: (Start)
Similarly, for n = 3, the person at floor 2 is already at his or her destination, so the elevator can move the person at floor 1 to floor 3 (up 2 floors), then move the person at floor 3 to floor 1 (down 2 floors), whence a(3) = 4.
For n = 4, the elevator must move once up to floor 4 then back down to floor 1 (a total of 3 + 3 floors), with intermediate stops allowing the persons at floors 2 and 3 to enter and get off at their destinations, too: a(4) = 3 + 3 = 6.
The pattern prevails up to n = 7 with a(7) = 6 + 6, where the elevator can hold the persons from floors 1, 2, and 3 simultaneously, and later those from floors 7, 6, and 5 simultaneously.
Beyond this, the limited capacity of the elevator comes into play and requires it to move back and forth between intermediate floors to accomplish the task.
One solution for n = 8 is to take persons 1, 2 and 3, drop off person 3 at floor 6 (moving 5 floors so far), take person 5 down to floor 4 (+ 2 floors), then person 4 to floor 5 and passengers 2 and 1 to their destinations at floor 7 and 8 (+ 4 floors), and finally the persons there down to floor 2 and 1 (+ 7 floors), for a total of a(8) = 5 + 2 + 4 + 7 = 18 floors. A similar solution (inserting an additional floor, where the elevator never has to stop, between 4 and 5) yields a(9) = a(8) + 4 = 22. (End)
PROG
(PARI) A162763(n, C=3)=2*n-2+if(n>2*C+3, A162763(n-2*C, C)+C, n>2*C+1, 2*n-4*C) \\ Proved to be an upper bound, conjectured to be exact (also for other values of C). - M. F. Hasler, May 15 2019
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Do Zerg (daidodo(AT)gmail.com), Jul 13 2009
EXTENSIONS
Edited by M. F. Hasler, Apr 29 2019
STATUS
approved