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 $1\ 2\ 3\ 4\ 5$, which of the following could not be the order in which the secretary types them?
$\textbf{(A)}\ 1\ 2\ 3\ 4\ 5 \qquad \textbf{(B)}\ 2\ 4\ 3\ 5\ 1 \qquad \textbf{(C)}\ 3\ 2\ 4\ 1\ 5 \qquad \textbf{(D)}\ 4\ 5\ 2\ 3\ 1 \qquad \textbf{(E)}\ 5\ 4\ 3\ 2\ 1 \qquad$
We can show that $A$, $B$, $C$, and $E$ are possible.
$A$: the boss delivers $1$, then the secretary does $1$, then the boss delivers $2$, then the secretary does $2$, etc. up to $5$.
$B$: the boss delivers $1$, then delivers $2$, then the secretary does $2$, then the boss delivers $3$, then delivers $4$, then the secretary does $4$, then the secretary does $3$, then the boss delivers $5$, then the secretary does $5$, then the secretary does $1$.
$C$: the boss delivers $1$, then delivers $2$, then delivers $3$, then the secretary does $3$, then does $2$, then the boss delivers $4$, then the secretary does $4$, then does $1$, then the boss delivers $5$, then the secretary does $5$.
$E$: the boss delivers $1$, then $2$, then $3$, then $4$, then $5$, then the secretary does $5$, does $4$, etc. down to $1$.
Hence the answer must be $\boxed{\text{D}}$. To give a complete proof, we need to show $D$ is impossible. In order for the secretary to start with $4$, the boss must deliver $1$, $2$, $3$, and $4$, then the secretary does $4$. To get $5$ next, the boss next delivers $5$, then the secretary does $5$, but now we can't get $2$, $3$, $1$: the remaining letters must start with $3$, which is on the top of the pile. Hence $D$ is impossible, as required.