7. Find the fixed number of stacks that is required to allow you to make all the permutations, however many numbers are in the starting column? (If you don't think it can be done, indicate why not).
Despite the huge successes possible with 4 columns, in general no fixed number of stacks, k, will let you make all possible permutations. In fact, the fraction of possible permutations of n starting numbers that you can make with a fixed number of stacks gets smaller and smaller as n gets bigger and bigger.
Both Simon and James gave the statement "You can't make all arrangements of n numbers using only n stacks" without proof (although Simon indicated his reasoning).
This is not, however, a valid counter-example, because it's not true.
ProofSuppose you can construct all permutations of k numbers using k stacks, for some k. Then you can construct all permutations of k+1 numbers as follows: Take a given target permutation. Remove from this permutation the number k+1. Construct this new permutation in reverse on the k'th stack. Now transfer numbers from stack k to stack k+1 one at a time. At the appropriate point, insert the number k+1 by transferring it over column k and onto column k+1. Then transfer the rest of the numbers. Since we've already seen that we can construct all permutations of 4 numbers using 4 stacks, this proves that the claimed counter-example is in fact not true for all n>3. |
I now give a non-constructive proof that a fixed number of stacks does not suffice to construct all permutations of an arbitrarily-sized starting stack.
Consider the number of possible different strategies you can have, for a fixed number of stacks k and n starting numbers.
It takes a total of nx(k-1) moves to get all the numbers onto the last stack. At each move, you have a choice of at most (k-1) different moves to choose from (move a number from stack 1, move a number from stack 2, etc.). Sometimes you have fewer choices, but you never have more than this.
Consequently, there are at most (k-1)^(nx(k-1)) different strategies that you can use to move all the numbers from the first stack to the last. Since k is fixed, this means that (k-1)^(k-1) is a constant. Let us call this value M.
At this stage the argument I'm using should become clear. The values of M^n go up by a fixed factor of M as n increases; whereas the count of possible permutations of n numbers goes up by an increasing factor as n increases.
Thus, our upper bound of achievable combinations expressed as a fraction of the total possible permutations, (M^n)/n!, tends to zero for large n.
In other words, at some point for a fixed number of stacks there'll be fewer possible strategies than total permutations.