Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2001 AMC 12 Problems/Problem 16"

(New page: == 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 m...)
 
(→‎Solution 4)
 
(24 intermediate revisions by 16 users not shown)
Line 14: Line 14:
 
\text{(E) }16!
 
\text{(E) }16!
 
</math>
 
</math>
−
 
 
== Solution ==
 
== Solution ==
  
 
=== Solution 1 ===
 
=== Solution 1 ===
  
−
Let the spider try to put on all <math>16</math> things in a random order. Each of the <math>16!</math> permutations is equally probable. For any fixed leg, the probability that he will first put on the sock and only then the shoe is clearly <math>1/2</math>. Then the probability that he will correctly put things on all legs is <math>1/2^8</math>. Therefore the number of correct permutations must be <math>\boxed{\frac {16!}{2^8}}</math>.
+
Let the spider try to put on all <math>16</math> things in a random order. Each of the <math>16!</math> permutations is equally probable. For any fixed leg, the probability that he will first put on the sock and only then the shoe is clearly <math>\frac{1}{2}</math>. Then the probability that he will correctly put things on all legs is <math>\frac{1}{2^{8}}</math>. Therefore the number of correct permutations must be <math>\boxed{\frac {16!}{2^8}}</math>.
  
 
=== Solution 2 ===
 
=== Solution 2 ===
  
 
Each dressing sequence can be uniquely described by a sequence containing two <math>1</math>s, two <math>2</math>s, ..., and two <math>8</math>s -- the first occurrence of number <math>x</math> means that the spider puts the sock onto leg <math>x</math>, the second occurrence of <math>x</math> means he puts the shoe onto leg <math>x</math>.  
 
Each dressing sequence can be uniquely described by a sequence containing two <math>1</math>s, two <math>2</math>s, ..., and two <math>8</math>s -- the first occurrence of number <math>x</math> means that the spider puts the sock onto leg <math>x</math>, the second occurrence of <math>x</math> means he puts the shoe onto leg <math>x</math>.  
−
The number of such sequences is <math>{16\choose 2,2,\dots,2} = \frac{16!}{(2!)^8} = \boxed{\frac {16!}{2^8}}</math>.
+
If the numbers were all unique, the answer would be <math> 16! </math>. However, since 8 terms appear twice, the answer is <math> \frac{16!}{(2!)^8} = \boxed{\dfrac {16!}{2^8}}</math>.
 +
 
 +
=== Solution 3 (Bashy Solution)===
 +
You can put all <math>8</math> socks on first for <math>8!</math> ways and then all <math>8</math> shoes on next for <math>8!</math> more ways. This is not the only possibility, so the lower bound is <math>(8!)^2</math>. Here is the reason why this is not the only possibility: You could for example put on 3 socks and then 1, 2, or 3 shoes before moving on and putting more socks on. Clearly this is not accounted for if you put on 8 socks right away and then 8 shoes. You don't have to put on 8 socks and then 8 shoes. You can choose all <math>16</math> in a random fashion, but some combinations would violate the rules, so the upper bound is <math>16!</math>. <math>\text{(C)}</math> & <math>\text{(E)}</math> are the lower and upper bounds, so the answer is in between them, <math>\boxed{\frac {16!}{2^8}}</math>.
 +
 
 +
=== Solution 4 ===
 +
Pretty clearly, if we choose each sock-shoe pair individually, they will automatically align themselves.
 +
Name the corresponding socks for leg 1 as a1 and each shoe for leg 1 be b1, and follow this flow of logic, extending it to leg 8, with sock named a1 and shoe named b1. Then, we can see that the set {a1,b1} and set {ba,a1} will both correspond to the order {a1,ba}, from the condition. Basically, this just means that we just need to choose a set of 2 elements without the order.
 +
<math>\binom{16}{2}\binom{14}{2}\cdots\binom{2}{2} = \frac{16 \cdot 15 \cdots 2}{2 \cdot 2 \cdots 2} = \frac{16!}{2^8}</math>
 +
 
 +
=== Video Solution ===
 +
https://youtu.be/D1n-qEPdm6g
  
 
== See Also ==
 
== See Also ==
  
 
{{AMC12 box|year=2001|num-b=15|num-a=17}}
 
{{AMC12 box|year=2001|num-b=15|num-a=17}}
 +
{{MAA Notice}}

Latest revision as of 05:07, 30 May 2024

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?

$\text{(A) }8! \qquad \text{(B) }2^8 \cdot 8! \qquad \text{(C) }(8!)^2 \qquad \text{(D) }\frac {16!}{2^8} \qquad \text{(E) }16!$

Solution

Solution 1

Let the spider try to put on all $16$ things in a random order. Each of the $16!$ permutations is equally probable. For any fixed leg, the probability that he will first put on the sock and only then the shoe is clearly $\frac{1}{2}$. Then the probability that he will correctly put things on all legs is $\frac{1}{2^{8}}$. Therefore the number of correct permutations must be $\boxed{\frac {16!}{2^8}}$.

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{\dfrac {16!}{2^8}}$.

Solution 3 (Bashy Solution)

You can put all $8$ socks on first for $8!$ ways and then all $8$ shoes on next for $8!$ more ways. This is not the only possibility, so the lower bound is $(8!)^2$. Here is the reason why this is not the only possibility: You could for example put on 3 socks and then 1, 2, or 3 shoes before moving on and putting more socks on. Clearly this is not accounted for if you put on 8 socks right away and then 8 shoes. You don't have to put on 8 socks and then 8 shoes. You can choose all $16$ in a random fashion, but some combinations would violate the rules, so the upper bound is $16!$. $\text{(C)}$ & $\text{(E)}$ are the lower and upper bounds, so the answer is in between them, $\boxed{\frac {16!}{2^8}}$.

Solution 4

Pretty clearly, if we choose each sock-shoe pair individually, they will automatically align themselves. Name the corresponding socks for leg 1 as a1 and each shoe for leg 1 be b1, and follow this flow of logic, extending it to leg 8, with sock named a1 and shoe named b1. Then, we can see that the set {a1,b1} and set {ba,a1} will both correspond to the order {a1,ba}, from the condition. Basically, this just means that we just need to choose a set of 2 elements without the order. $\binom{16}{2}\binom{14}{2}\cdots\binom{2}{2} = \frac{16 \cdot 15 \cdots 2}{2 \cdot 2 \cdots 2} = \frac{16!}{2^8}$

Video Solution

https://youtu.be/D1n-qEPdm6g

See Also

2001 AMC 12 (Problems • Answer Key • Resources)
Preceded by
Problem 15 		Followed by
Problem 17
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_AMC_12_Problems/Problem_16&oldid=219885"