| If each pizza can be built N ways, and there's no way to tell them
apart except for the toppings, then there are N*(N+1) combinations.
There's no integer N for which N*(N+1)=1048576=2^20. Thus, there
must be some difference between the pizzas (perhaps one's large and
one's small), and there are N^2 combinations. Each pizza can be built
1024=2^10 ways.
I puzzled for a while about how to find sums of quotients of
factorials that would add up to 2^10. Finally I came at it this way:
If there are only 5 toppings to choose from, you can build 32=2^5
different pizzas (each topping is independently included or not),
and never worry about having too many toppings on a pizza. But
we need many more different pizzas than this. If there are 11 toppings
to choose among, you get 2048=2^11 different pizzas -- but some of
them have more than 5 toppings. But every pizza with 6 or more
toppings has a "complement" pizza that has the other 5 or fewer
toppings, and vice versa, so exactly half the pizzas have too many
toppings. Thus the number of legal pizzas is 1024=2^10, and two
such pizzas can be built in 1048576 ways.
|