4
$\begingroup$

A centipede wants to put on its 100 legs 100 socks and 100 shoes. In how many different sequences can it put on all shoes and socks if it has to put on each sock on a leg before the shoe, but it can put on a sock on another leg before putting on a shoe on the former leg? I tried it by recursion, but it seems complicated.

$\endgroup$
6
$\begingroup$

There are $200\choose 2$ possible times when thins are done to the first leg. After that, there are $198\choose 2$ for the second leg, and so on. In total, we cont $$ {200\choose 2}{198\choose 2}{196\choose 2}\cdot {2\choose 2}=\frac{200!}{2^{100}}$$

$\endgroup$
  • 1
    $\begingroup$ Elegant solution.+1 $\endgroup$ – saulspatz May 9 '18 at 18:28
7
$\begingroup$

There are $200$ events that need to occur, in some order -- each leg's shoeing and each leg's socking. So, that's $200!$ possible events. But now we can add the constraint that the socks come before the shoe, for each leg. In half of the $200!$ sequences, we put the first leg's shoe before the first leg's sock, so we have to throw away half of them. Then the same is true for the second leg: remove half. And so on. So we trim stuff down by a factor of $2^{100}$. So

$$\frac{200!}{2^{100}}$$

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