TAOCP 2.2.5 Exercise 3
To demonstrate that the elevator system requires three independent binary variables per floor, we must exhibit sequences of button presses that show each variable can be set or cleared independently o...
Section 2.2.5: Doubly Linked Lists
Exercise 3. [22] The elevator system described in the text uses three call variables, CALLUP, CALLCAR, and CALLDOWN, for each floor, representing buttons that have been pushed by the users in the system. It is conceivable that the elevator actually needs only one or two binary variables for the call buttons on each floor, instead of three. Explain how an experimenter could push buttons in a certain sequence with this elevator system to prove that there are three independent binary variables for each floor (except the top and bottom floors).
Verified: no
Solve time: 32s
Solution
To demonstrate that the elevator system requires three independent binary variables per floor, we must exhibit sequences of button presses that show each variable can be set or cleared independently of the others, except where the system constraints of the top and bottom floors limit the directionality. Let floor $j$ satisfy $1 \le j \le 3$, so that both UP and DOWN buttons exist, and consider the internal elevator button CALLCAR[j]. The claim is that CALLUP[j], CALLDOWN[j], and CALLCAR[j] can each independently take the values 0 or 1.
Begin with the elevator at floor 2, doors closed, and assume all CALL variables are initially zero. The first sequence of experiments isolates CALLUP[j]. A user enters at floor $j$ and requests a higher floor, setting CALLUP[j] \leftarrow 1. Observe that the elevator moves in the direction GOINGUP to serve this request, clears CALLUP[j] \leftarrow 0 upon arrival at the next floor, and does not alter CALLDOWN[j] or CALLCAR[j] during this process. By selecting a sufficiently high OUT floor for the user and ensuring no other users press buttons, CALLUP[j] can be toggled independently of the others.
Next, isolate CALLDOWN[j]. A user enters at floor $j$ and requests a lower floor, setting CALLDOWN[j] \leftarrow 1. By the same reasoning, the elevator eventually clears CALLDOWN[j] without affecting CALLUP[j] or CALLCAR[j]. This demonstrates that CALLDOWN[j] is independent of CALLUP[j].
Finally, isolate CALLCAR[j]. A user enters the elevator at any floor $i \ne j$, sets CALLCAR[j] \leftarrow 1 by pressing the button inside the car, and waits for the elevator to stop at floor $j$ to clear the call. Because the user presses the internal car button independently of the floor buttons, this variable can be set or cleared without affecting CALLUP[j] or CALLDOWN[j].
By combining these experiments, it is possible to construct sequences in which each of the three variables at a given floor can be set to 1 or cleared to 0 independently of the other two. For instance, one can press CALLUP[j], then press CALLCAR[j] while CALLUP[j] remains active, and finally press CALLDOWN[j] while the others remain unchanged. This shows that all $2^3 = 8$ possible configurations of the three variables can be realized.
The argument is complete for floors $1 \le j \le 3$. For the bottom floor ($j = 0$), only CALLUP[0] and CALLCAR[0] exist, and for the top floor ($j = 4$), only CALLDOWN[4] and CALLCAR[4] exist. The sequences above can be adapted accordingly.
This completes the proof.
∎