The question was:
A spider has 8 legs. It wants to put on 8 different socks and 8 different shoes on each leg, but it must put a sock on before a shoe. What is the total amount of ways?
I thought it would be $8! \times 8!$, since we fix socks, then arrange socks. Then fix shoes, then arrange shoes.

However, my lecturer said it was this:
Form a 16 digit string with only digits $1$ to $8$.
An example is:
THe total amount of ways of having a string of this form will be $16!/(2!)^8$.

I don't see why my answer is incorrect and why their one is. Their explanation was that
"each digit represents that leg. For example, the first digit $1$ is corresponding to putting a sock on the 1st leg. The second $1$ that appears will be the shoe."


His result $$\frac{16!}{(2!)^8}$$ comes from the fact that you can arrange the socks and shoes in any order, but only half of the orders will put sock A on before shoe A, half of those will put on sock B before shoe B, and so on. This can be extended to the spider having to put on a sock, then a shoe, then a snowshoe. In that case, there are six possible orders to put on the sock, then the sock protector, then the shoe, but only the order sock, shoe, and snowshoe works, meaning that only $\frac1{3!}=\frac16$ out of the possible orders will be correct. You do this for each of the eight legs. Your result of $8!\cdot8!$ only counts the ordering of putting on all the socks, then all the shoes after the spider has put on all eight socks. For instance, your result would not count putting on the sock and the corresponding shoe immediately afterwards.

  • $\begingroup$ I see. If we could put on shoes before socks, we wouldn't divide right? And each digit will be distinct? So we have something like $1_1,1_2$? $\endgroup$ – similarityinvariance1 Sep 20 '17 at 2:16
  • $\begingroup$ @similarityinvariance1 Yes, if we could put on socks and shoes in any order, we would have $16!$ ways to do it. I am having trouble understanding your other questions. $\endgroup$ – AlgorithmsX Sep 20 '17 at 2:19
  • $\begingroup$ A better extension might be: sock, shoe, snowshoe. Or you can do: sock, shoe, ski boot, ski. $\endgroup$ – Wildcard Sep 20 '17 at 2:21
  • 1
    $\begingroup$ Thank you. Which part of my reasoning for $8!\times 8!$ is incorrect? $\endgroup$ – similarityinvariance1 Sep 20 '17 at 2:25

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.