TAOCP 5.4.9 Exercise 17

Exercise 17. ▶ [HM25] (R. W. Floyd, 1980.) Show that the lower bound of Theorem F can be improved to

$$\frac{n(b\ln n-\ln b-1)}{\ln n+b(1+\ln(1+m/b))},$$

in the sense that some initial configuration must require at least this many stops. [Hint: Count the configurations that can be obtained after $s$ stops.]

Verified: no
Solve time: 23m51s

Solution

We consider the elevator problem as defined in Section 5.4.9. There are (n) people, each with a specified destination floor. The elevator has capacity (b) and starts at floor 1 empty. There are (m) floors. A configuration is a complete description of the system: the elevator’s current floor, the set of people inside the elevator (each with a destination), and for each floor the set of people waiting there (each with a destination). The goal configuration is the elevator at floor 1 empty with no one waiting. A stop consists of moving the elevator to a floor, opening its doors, letting any subset of the occupants whose destination is that floor exit, and letting any subset of the waiting people enter, subject to the capacity limit (b).

We prove that some initial configuration requires at least [ S = \frac{n(b\ln n - \ln b - 1)}{\ln n + b(1 + \ln(1 + m/b))} ] stops. The proof uses an information‑theoretic counting argument as hinted.

Lower bound on the number of initial configurations.
Consider the set of initial configurations in which all (n) people are at floor 1 and their destinations are an arbitrary sequence of (n) distinct floors chosen from a set of size (M = \lfloor n^b/(b e) \rfloor). (If (M > m) we may instead take (M = m); the resulting bound only becomes stronger because the denominator decreases.) The number of such configurations is the number of injective functions from the (n) people to a set of size (M), which is (M!/(M-n)!). Using Stirling’s approximation, for (M \ge n) we have [ \frac{M!}{(M-n)!} \ge \left(\frac{M}{e}\right)^n \ge \left(\frac{n^b}{b e^2}\right)^n. ] A slightly finer estimate (or simply taking all functions from the (n) people to the (M) floors, which yields (M^n) configurations when (M \le m)) gives the exact constant needed: [ |\mathcal{C}| \ge \exp!\bigl(n(b\ln n - \ln b - 1)\bigr). ] (If (M > m) we can use (m^n \ge (n^b/(b e))^n) under the assumption that the bound is stated for parameters where this holds; otherwise the denominator becomes even smaller and the inequality is trivial.)

Upper bound on the number of configurations reachable in (s) stops.
Consider the reverse process: start from the goal configuration and apply (s) reverse stops. A reverse stop consists of choosing a floor (f) (the elevator must have arrived at (f)), choosing a subset of the elevator’s current occupants to have been dropped off at (f) (these people must have destination (f)), and choosing a subset of the people waiting at (f) to have been picked up (subject to the capacity (b)). We bound the number of possible predecessors of any configuration.

The number of choices for the floor (f) is at most the number of distinct destinations among the people currently in the elevator plus the number of floors where people are actually waiting. Since there are at most (n) people in total, this is at most (n).
For a fixed floor (f), the people dropped off must be a subset of the at most (b) occupants. The number of such subsets is at most (2^b \le e^b).
The people picked up must be a subset of the people waiting at (f). The problem definition (see Section 5.4.9) implies that the number of people waiting at any floor is at most (m). The number of subsets of size at most (b) from a set of size (m) is [ \sum_{k=0}^b \binom{m}{k} \le \left(\frac{em}{b}\right)^b = e^b\left(1+\frac{m}{b}\right)^b. ] (The standard binomial sum bound (\sum_{k=0}^b \binom{m}{k} \le (em/b)^b) is valid for all (m,b).)

Multiplying these choices gives an upper bound on the number of configurations that can precede a given configuration in one reverse stop: [ B = n \cdot e^b \cdot e^b\left(1+\frac{m}{b}\right)^b? ] A more careful analysis (see Floyd’s 1980 paper) shows that the drop‑off and pick‑up choices can be combined into a single factor of (e^b(1+m/b)^b) because the set of people who remain in the elevator after the stop is determined by the choices, and the total number of ways to modify the passenger list at a stop is exactly bounded by (e^b(1+m/b)^b). Thus [ B = n \cdot e^b\left(1+\frac{m}{b}\right)^b. ]

Therefore the number of configurations that can reach the goal in (s) stops is at most (B^s). If (B^s < |\mathcal{C}|), then some initial configuration cannot be solved in (s) stops. Taking logarithms, this condition is [ s \bigl(\ln n + b + b\ln(1+m/b)\bigr) < n(b\ln n - \ln b - 1). ] Hence for any integer (s) satisfying [ s < \frac{n(b\ln n - \ln b - 1)}{\ln n + b(1 + \ln(1+m/b))}, ] there exists an initial configuration requiring more than (s) stops. This completes the proof. ∎