Ex. 3 A spider has one sock and one shoe for each of its eight legs. On each leg the sock
must be put on before the shoe. In how many different orders can the spider put on its
socks and shoes?
(1) 8! (2) 2⁸ · 8! (3) (8!)² (4) 16!/2⁸
Sol. (4)
Without the condition that on each of the legs the sock must go on before the shoe, the
solution to the problem would be easy. The shoes and socks total 16 objects, so there
would be 16! orders. Since the requirement of putting the respective socks on before the
shoes reduces this number, the problem is to determine the reduction.
Suppose that we let S₁ be the shoe that is placed on the 1st leg, and s₁ be the sock that
is placed on the 1st leg, where 1 ≤ i ≤ 8. If we write the order that the spider placed
objects on its legs, it must start with one of the socks, say s₁. Then it can place any
of its remaining socks but only the shoe S₁. After the second object is placed, what
immediately can follow depends on whether the second object chosen was the shoe S₁ or
one of the remaining socks.
It seems clear that this problem is too difficult to solve by trying to find a pattern
that will enumerate all the possibilities. Even if the spider had only 2 legs, there
would be 6 possibilities:
s₁ S₁ s₂ S₂, s₁ s₂ S₁ S₂, s₂ S₂ s₁ S₁,
s₂ s₁ S₁ S₂, s₁ s₂ S₂ S₁, or s₂ s₁ S₂ S₁.
However, this simplified enumeration gives the clue to the pattern. For the two-legged
spider, the total number of orders, 4! = 24, has been reduced by multiplying by 1/4 =
(1/2)² because, for each leg, half of the time the sock will be first, which is a
success, and half of the time the shoe will be first, which is a failure.
Since there must be a success on each of the 8 legs of our original spider, the total
number of ways that the spider can be successful is the total number of ways the 16
objects can be chosen, 16!, multiplied by the likelihood the spider will be successful
on each leg, (1/2)⁸. So the total number of successful orders is 16!/2⁸.
Comments
Post a Comment