Problem:
In an office, at various times during the day the boss gives the secretary a letter to type, each time putting the letter on top of the pile in the secretary's in-box. When there is time, the secretary takes the top letter off the pile and types it. If there are five letters in all, and the boss delivers them in the order , which of the following could not be the order in which the secretary types them?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
At any given time, the letters in the box are in increasing order from the bottom, because that's the way they were put in the box and the relative order of those still there is never changed. Thus, for any and all , all letters taken off the pile later than letter must still have been in the pile when was added, and thus are in descending order from the top. Thus they must be taken off in descending order. For , this is not true in -- the lower numbered letters supposedly typed after are , in that order. So is not a possible typing order. All the other permutations listed meet the condition just described. For instance, for , the letters with which come after are and , in that order, which is descending order. All these other permutations are possible typing orders; the reader should show when each letter was added to the pile and when each was typed.
Note. This is a problem in computer science in disguise. The in-box is a "stack", an important "data structure" in computer science. The general question underlying this problem is: if items are put on a stack in order , then what permutations are possible orders for taking them off? We have found a necessary condition: all which follow in the permutation must be in descending order. Is this condition sufficient?