FMM1

Friday Morning Math Problem

Spider Socks and Shoes

A spider has one sock and one shoe for each of its eight legs. In how many different orders can the spider put on its socks and shoes, assuming that, on each leg, the sock must be put on before the shoe?

Solution

Label each of the spider's legs 1 through 8. Label the "put on a sock" operation as a, "put on a shoe" operation as b. Now, a possible arrangement of ways of putting on socks and shoes is a permutation of the 16 symbols, a1 b1 a2 b2 ... a8 b8 subject to the condition that ak precedes bk for k = 1..8. Our goal is to count the number of these permutations. The total number of permutations of the 16 symbols (no conditions) is 16! Among those 16! possibilities, exactly half of them have a1 before b1, and the other half have b1 before a1. So, only half of the total permutations fit our criteria for leg number 1. We are down to 16!/2 possibilities. But we can apply the same logic for leg 2 - of those 16!/2 possibilities, exactly half of them have a2 before b2, and the other half have b2 before a2. So, only half of those permutations fit our criteria. We are down to 16!/2^2 possibilities. We apply the same logic to all 8 legs, to obtain our final answer of ${\dfrac {16!}{2^{8}}}=81,729,648,000$