1
$\begingroup$

a spider has one sock and one shoe for each of its 8 legs.in how many different orders can the spider put on its shocks and shoes; assuming that on each leg ;the shock must be put on before the shoe? i have tried the problem in following processes-

  • we consider in k th step it has completed covering exactly its k legs with socks.now we find the total possibilities in (k+1) th step.
  • in (k+1) th step either one of the remaining (8-k) legs will be covered by shocks or one of the (k-r) legs will be covered by shoe. where r denote the number of legs among the k legs which were already covered by shoes. so 0$\leq$r$\leq$k and 1$\leq$k$\leq$8
  • so in the 1st case there are (8-k) possibilities and in the 2nd case ..........if 1 leg is covered with shoe then (k-1) possibilities; if 2 legs are covered with shoes then (k-2) possibilities; if no leg then k possibilities. so total possibilities is k.(k-1).(k-2)(k-3).........1=k!
  • in (k+1)th step the total possibilities is (8-k).k!.[in each step it puts on either a shock or a shoe]
  • so the solution is $\Sigma$(8-k).k! ;k=1 to 16
  • if i am wrong in any step then show me please. if i am not then give an alternate solution of this.
$\endgroup$
1
$\begingroup$

Let the act of putting on a sock be $1,2,3,4,5,6,7,8$, each corresponding to a leg. Let the act of putting on a shoe be $A,B,C,D,E,F,G,H$, each corresponding to a leg as well.

This problem is now bijective to counting the number of strings such that $A,B,C,D,E,F,G,H$ comes after $1,2,3,4,5,6,7, 8$ respectively.

We start with $1$ leg. Then there is only $1$ way: $1A$. Now we want to add the next leg. There are $3 \times 4$ ways to add $2$ and $B$ into the string, without any order. Why? Because there are $3$ ways to insert $2$ into $1A$, and $4$ ways to insert $B$ into each of the the resultant string.

But there are as many ways to insert $2$ and $B$ such that $2$ comes after $B$ as there are ways of insertion such that $B$ comes after $2$. So there are $\frac{1}{2} \times 3 \times 4$ ways such that $B$ comes after $2$, i.e. second shoe comes after second sock.

Generalize this to get a recursion: Let $a_n$ be the number of ways for $n$ legs. Then,

$$a_{n + 1} = \frac{1}{2}\times a_n \times (2n + 1)\times(2n + 2)$$

$\endgroup$
  • $\begingroup$ nice Yiyuan. nice solution. but is my process right? $\endgroup$ – krishan acton Apr 5 '14 at 14:27
  • $\begingroup$ @krishan I am unable to follow through your solution, it seems a bit too complicated to me... $\endgroup$ – Yiyuan Lee Apr 5 '14 at 14:42
  • $\begingroup$ Also see: artofproblemsolving.com/Wiki/index.php/2001_AMC_12_Problems/… $\endgroup$ – gar Apr 6 '14 at 14:45
  • $\begingroup$ am i right or not? answer me please.yes or no . $\endgroup$ – krishan acton Apr 9 '14 at 6:50

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.