Spider Problem Counting Socks and Shoes

Question

Problem

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?

A) 8! (B) $2^8$ (C) $(8!)^2$ (D) $\frac{16!}{2^8}$ (E) 16!

I am having trouble visualizing how the answer was gotten from this solution.

Solution 2

Each dressing sequence can be uniquely described by a sequence containing two $1$s, two $2$s, ..., and two $8$s -- the first occurrence of number $x$ means that the spider puts the sock onto leg $x$, the second occurrence of $x$ means he puts the shoe onto leg $x$. If the numbers were all unique, the answer would be $16!$. However, since 8 terms appear twice, the answer is $\frac{16!}{(2!)^8} = \boxed{\frac {16!}{2^8}}$

Answer 1

Let's take the simple case of 2 shoes and 2 socks first. There are $4!$ possible orderings (or permutations) of these 4 objects. However, I want to point your attention to the following permutations in particular:

$$P_1 \rightarrow (Shoe\ 1, Sock\ 1, Shoe\ 2, Sock\ 2)$$ $$P_2 \rightarrow (Sock\ 1, Shoe\ 1, Shoe\ 2, Sock\ 2)$$ $$P_3 \rightarrow (Shoe\ 1, Sock\ 1, Sock\ 2, Shoe\ 2)$$ $$P_4 \rightarrow (Sock\ 1, Shoe\ 1, Sock\ 2, Shoe\ 2)$$

Notice how only $P_4$ is a valid permutation since the shoes for leg 1 and leg 2 are worn only after the socks have been worn.

Also see that all of $P_1, P_2, P_3$ and $P_4$ represent the same leg order $(leg\ 1, leg\ 1, leg\ 2, leg\ 2)$. We can deduce at this point that corresponding to any given leg order there is exactly one valid permutation. So the question really boils down to finding how many distinct possible leg orders there are.

There are two ways to think about this. The easier one is to realize the number of distinct leg orders can be given by: $$\frac{4!}{(2!)(2!)} = \frac{4!}{2^2}$$

This is because we are counting the number of permutations where two groups of objects (each of size two) exist such that their contents can not be distinguished from one another.

In our case of 8 shoes and 8 socks, eight groups of size two exist such that their contents can not be distinguished from one another. So the answer we are looking for is: $$\frac{16!}{2^8}$$

---

Alternately,

Start by thinking that for any fixed leg order there are the following possibilities: $$ case\ 1 : You\ get\ no\ sock-shoe\ pair\ wrong\ \rightarrow\ {2 \choose 0} $$ $$ case\ 2 : You\ get\ one\ sock-shoe\ pair\ wrong\ \rightarrow\ {2 \choose 1} $$ $$ case\ 3 : You\ get\ both\ sock-shoe\ pair\ wrong\ \rightarrow\ {2 \choose 2} $$

Hence, any fixed leg order appears exactly ${2 \choose 0} + {2 \choose 1} + {2 \choose 2}$ times when we consider all $4!$ possible orderings. So number of distinct possible leg orders must be: $$\frac{4!}{{2 \choose 0} + {2 \choose 1} + {2 \choose 2}}$$

Extending the same logic to the case of 8 shoes and 8 socks, we get: $$\frac{16!}{{8 \choose 0} + {8 \choose 1} + \cdots +{8 \choose 8}} = \frac{16!}{256} = \frac{16!}{2^8}$$

Answer 2

It might be better to put subscripts on the numbers: $L_1$ means the action of putting the sock, and $L_2$ the shoe, on leg $L$. Then we have 16 distinct symbols $1_1,1_2,2_1,2_2,3_1,3_2,\dots,8_1,8_2$ and there are $16!$ ways to permute them without restrictions.

With the sock-before-shoe restriction, for each pair of $L_1$ and $L_2$, $L_1$ must come before $L_2$. For each sequence where $L_1$ comes before $L_2$ (allowed) there is a corresponding sequence where $L_1$ comes after $L_2$ (disallowed), so we divide by 2 for each leg, yielding the correct answer of $\frac{16!}{2^8}$.