Difference between revisions of "2001 AMC 12 Problems/Problem 16"
m (→Solution 3) |
Sevenoptimus (talk | contribs) (Significantly improved formatting and explanations) |
||
| (15 intermediate revisions by 12 users not shown) | |||
| Line 15: | Line 15: | ||
</math> | </math> | ||
| − | == Solution == | + | == Solution 1 == |
| − | == | + | Suppose the spider tries to put on all <math>2 \cdot 8 = 16</math> items in a random order, so that each of the <math>16!</math> possible permutations is equally probable. This means that for any fixed leg, the probability that it will first put on the sock, and only then the shoe, is clearly <math>\frac{1}{2}</math>. Hence the probability that it will put on the shoe and sock in the correct order for all its legs is <math>\left(\frac{1}{2}\right)^8 = \frac{1}{2^{8}}</math>. Therefore the number of possible permutations is <math>\boxed{\text{(D) }\frac {16!}{2^8}}</math>. |
| − | + | == Solution 2 == | |
| − | + | Each possible order in which the spider puts on its socks and shoes can be uniquely described as a sequence containing two <math>1</math>s, two <math>2</math>s, ..., and two <math>8</math>s, where the first occurrence of number <math>x</math> means that the spider puts the sock onto leg <math>x</math>, and the second occurrence means it puts the shoe onto leg <math>x</math> (as it must put on the sock for each leg before the corresponding shoe). | |
| − | + | Since there are a total of <math>2 \cdot 8 = 16</math> numbers, if they were all unique, the answer would be <math>16!</math>. However, since each of the <math>8</math> numbers actually appear twice, there are <math>2! = 2</math> orders for each number that are actually indistinguishable, and so the overcount is by a total factor of <math>2^8</math>. This means the answer is <math>\boxed{\text{(D) }\frac {16!}{2^8}}</math>. | |
| − | |||
| − | + | == Solution 3 (bash using bounding) == | |
| − | + | The spider could put on all <math>8</math> socks first, in <math>8!</math> possible ways, and then all <math>8</math> shoes on next, giving <math>8!</math> more possible ways. Of course, this is not the only possibility, so <math>8! \cdot 8! = (8!)^2</math> is a lower bound for the correct answer: the spider could instead, for example, put on <math>3</math> socks and then <math>1</math>, <math>2</math>, or <math>3</math> shoes, before proceeding to put on more socks. | |
| − | - | + | |
| + | In principle, it could put on all <math>2 \cdot 8 = 16</math> items in a random order, but some of these orders would violate the rule that on each leg, the sock must be put on before the shoe, so <math>16!</math> is an upper bound. In other words, answer choices <math>\text{(C)}</math> and <math>\text{(E)}</math> are lower and upper bounds, so the correct answer must lie in between them. Recalling that answer choices on the AMC appear in increasing order, we can deduce, without having to actually calculate it, that the correct answer must be <math>\boxed{\text{(D) }\frac {16!}{2^8}}</math>. | ||
| + | |||
| + | == Solution 4 == | ||
| + | Name the sock for e.g. leg <math>1</math> as <math>a1</math> and the corresponding shoe as <math>b1</math>, and similarly for all the other legs. Then, as the sock for each leg must be put on before the shoe, we observe that the pairs <math>(a1,b1)</math> and <math>(b1,a1)</math> must both correspond to the order <math>a1</math>, then <math>b1</math>. | ||
| + | |||
| + | We can now consider constructing an overall order of length <math>2 \cdot 8 = 16</math>, starting with <math>16</math> positions that each need to be filled with <math>ax</math> or <math>bx</math> for some integer <math>x</math> between <math>1</math> and <math>8</math>. For each of the <math>8</math> legs, we effectively need to choose <math>2</math> of the possible remaining positions, without regard to the order in which they are chosen (since only <math>1</math> order is actually possible, as explained above). | ||
| + | |||
| + | In other words, we must choose <math>2</math> unordered positions from <math>16</math>, then from the remaining <math>16-2 = 14</math>, and so on, so the total number of possible orders is | ||
| + | <cmath>\binom{16}{2}\binom{14}{2}\dotsm\binom{2}{2} = \frac{16 \cdot 15 \dotsm 2}{2 \cdot 2 \dotsm 2} = \boxed{\text{(D) }\frac {16!}{2^8}}.</cmath> | ||
| + | |||
| + | == Video Solution == | ||
| + | https://youtu.be/D1n-qEPdm6g | ||
== See Also == | == See Also == | ||
Latest revision as of 06:35, 6 June 2025
Contents
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?
Solution 1
Suppose the spider tries to put on all 
items in a random order, so that each of the 
possible permutations is equally probable. This means that for any fixed leg, the probability that it will first put on the sock, and only then the shoe, is clearly 
. Hence the probability that it will put on the shoe and sock in the correct order for all its legs is 
. Therefore the number of possible permutations is 
.
Solution 2
Each possible order in which the spider puts on its socks and shoes can be uniquely described as a sequence containing two 
s, two 
s, ..., and two 
s, where the first occurrence of number 
means that the spider puts the sock onto leg , and the second occurrence means it puts the shoe onto leg (as it must put on the sock for each leg before the corresponding shoe).
Since there are a total of numbers, if they were all unique, the answer would be . However, since each of the numbers actually appear twice, there are 
orders for each number that are actually indistinguishable, and so the overcount is by a total factor of 
. This means the answer is .
Solution 3 (bash using bounding)
The spider could put on all socks first, in 
possible ways, and then all shoes on next, giving more possible ways. Of course, this is not the only possibility, so 
is a lower bound for the correct answer: the spider could instead, for example, put on 
socks and then , , or shoes, before proceeding to put on more socks.
In principle, it could put on all items in a random order, but some of these orders would violate the rule that on each leg, the sock must be put on before the shoe, so is an upper bound. In other words, answer choices 
and 
are lower and upper bounds, so the correct answer must lie in between them. Recalling that answer choices on the AMC appear in increasing order, we can deduce, without having to actually calculate it, that the correct answer must be .
Solution 4
Name the sock for e.g. leg as 
and the corresponding shoe as 
, and similarly for all the other legs. Then, as the sock for each leg must be put on before the shoe, we observe that the pairs 
and 
must both correspond to the order , then .
We can now consider constructing an overall order of length , starting with 
positions that each need to be filled with 
or 
for some integer between and . For each of the legs, we effectively need to choose of the possible remaining positions, without regard to the order in which they are chosen (since only order is actually possible, as explained above).
In other words, we must choose unordered positions from , then from the remaining 
, and so on, so the total number of possible orders is
![\[\binom{16}{2}\binom{14}{2}\dotsm\binom{2}{2} = \frac{16 \cdot 15 \dotsm 2}{2 \cdot 2 \dotsm 2} = \boxed{\text{(D) }\frac {16!}{2^8}}.\]](http://latex.artofproblemsolving.com/b/c/6/bc61ecd2b3f595dedbd396fd8d6451c6ac46a7d8.png)
Video Solution
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 | |
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. 
