3
$\begingroup$

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}}$

$\endgroup$
  • 1
    $\begingroup$ I have difficulty visualizing how the spider can put a sock and a shoe on its eighth leg. Must be difficult when the other seven legs are covered. Perhaps you can make a drawing? $\endgroup$ – M. Wind Nov 3 '18 at 2:14
1
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ Is there any chance this would be A006480? I checked by hand for up to N=3 and it works, but more than that would be tedious to do on paper. It does seem like an (n,n,n) grid would define the problem space, one number being a bare foot, one being a socked foot, and the other being a socked-and-shoed foot. I'd think it make more sense as a (3,3,...,3) grid in N dimensions, which should be the same problem just inverted. I don't know, just spit-balling here. $\endgroup$ – Darrel Hoffman Jan 29 '19 at 21:54
2
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.