8. If backwards moves are allowed too, find the fixed number of stacks that is required to allow you to make all the permutations (of the starting numbers) in the final stack, however many numbers are in the starting column. (Again, if you don't think this can be done, say why not).
You only require 3 stacks, no matter how many starting numbers you have.
A constructive proof is offered. Suppose we have n numbers, and want to finish with a particular permutation: t1, t2, t3, ..., t(n-1), tn.
The strategy is to build the required permutation from the bottom up in stack 3.
We start by getting the bottom number required, tn, onto stack 3. This can be achieved by successively moving numbers from stack 1 to stack 2 until the tn is on the top of stack 1. We then move this across stack 2 and onto stack 3.
Next, we need to put t(n-1) onto stack 3. This is either going to be further down stack 1, in which case we continue as before transferring numbers from stack 1 to stack 2, or it will be in stack 2, in which case we transfer numbers back into stack 1 until the required number is at the top of stack 2.
At this stage, we can transfer t(n-1) onto stack 3. We continue in this fashion until all the numbers are in stack 3 in the required order.