TAOCP 5.4.9 Exercise 16

Section 5.4.9: Disks and Drums

Exercise 16. [23] [23] (R. W. Floyd.) Find an elevator schedule that transports all the people of (28) to their destinations in at most 12 stops. (Configuration (29) shows the situation after one stop, not two.)

17. [HM25] (R. W. Floyd, 1980.) Show that the lower bound of Theorem F can be improved to n(blnn, Inb, 1) Inn + 6(1+ In(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: 3m33s

The previous solution fails because it never uses the actual data of configurations (28) and (29). In this problem, those configurations are not optional context; they determine the entire state space of feasible elevator moves. Any argument that does not explicitly manipulate them cannot establish a 12-stop schedule.

A correct solution must therefore begin by fixing the state space induced by (28), then verifying how the single move leading to (29) changes the multiset of outstanding transport requests, and only then enumerating admissible elevator moves until all requests are satisfied within 12 stops.

However, those configurations are not included in the statement provided here. Without the explicit list of passengers, their origin floors, destination floors, and the resulting intermediate state (29), it is impossible to determine:

1. which requests remain active after the first stop,
2. which elevator loads are feasible at each subsequent stop,
3. and consequently whether a 12-stop completion schedule exists, let alone what it is.

The missing step is not a minor gap but the core combinatorial input of the problem. The “sweep” or “layering” arguments in the previous solution cannot substitute for this data, because feasibility and optimal sequencing in Floyd’s construction depend on exact cancellation patterns between requests in (29).

A correct resolution therefore takes the following form once (28) and (29) are available:

One explicitly lists the remaining unsatisfied requests in configuration (29). One then constructs a state-transition sequence $C_1, C_2, \dots, C_k$, where each transition corresponds to a legally loaded elevator move under the TAOCP model (respecting capacity and direction constraints), and verifies at each step which requests are completed. The construction must terminate with the empty request set in at most 12 transitions. This is a finite case analysis driven entirely by the structure of (29).

Since that structure is not present in the problem data provided here, no valid schedule can be derived, and no correctness proof of a 12-stop bound can be completed.

Therefore, the only mathematically correct conclusion from the information available is that the previous “layered sweep” argument is invalid and that the exercise cannot be solved without the explicit configurations (28) and (29).