Difference between revisions of "2012 AMC 10A Problems/Problem 25"
(→Solution II) |
(→Solution III) |
||
Line 80: | Line 80: | ||
Let us choose new variables <math>y_{i} = x_{i} - (i-1)</math> for <math>i = 1,\dotsc,k</math>; then the set of <math>k</math>-tuples <math>(y_{1},\dotsc,y_{k}) \in [0,n-(k-1)]^{k}</math> which satisfy <math>y_{1} < \dotsb < y_{k}</math> has volume <math>\frac{1}{k!}(n-(k-1))^{k}</math>. Hence <math>T</math> has volume <math>\frac{1}{k!}(n-(k-1))^{k}</math> as well and <math>S</math> has volume <math>(n-(k-1))^{k}</math>. Hence the desired probability is <math>\frac{(n-(k-1))^{k}}{n^{k}}</math>. | Let us choose new variables <math>y_{i} = x_{i} - (i-1)</math> for <math>i = 1,\dotsc,k</math>; then the set of <math>k</math>-tuples <math>(y_{1},\dotsc,y_{k}) \in [0,n-(k-1)]^{k}</math> which satisfy <math>y_{1} < \dotsb < y_{k}</math> has volume <math>\frac{1}{k!}(n-(k-1))^{k}</math>. Hence <math>T</math> has volume <math>\frac{1}{k!}(n-(k-1))^{k}</math> as well and <math>S</math> has volume <math>(n-(k-1))^{k}</math>. Hence the desired probability is <math>\frac{(n-(k-1))^{k}}{n^{k}}</math>. | ||
− | === | + | ===Appendix=== |
+ | This solution is motivated by the suggestive formula <math>\frac{(n-2)^{3}}{n^{3}}</math>. | ||
− | + | We generalize it to <math>k</math>-dimensional real space <math>\mathbb{R}^{k}</math>. Suppose we are asked to find the probability that a randomly chosen <math>k</math>-tuple <math>(x_{1},\dotsc,x_{k}) \in [0,n]^{k}</math> satisfies <math>|x_{i} - x_{j}| > 1</math> for all <math>i \ne j</math>. The total set of <math>k</math>-tuples in <math>[0,n]^{k}</math> has volume <math>n^{k}</math>. Let <math>S</math> be the set of <math>k</math>-tuple <math>(x_{1},\dotsc,x_{k})</math> which satisfies <math>|x_{i}-x_{j}|>1</math> for all <math>i \ne j</math>. The desired probability is Vol<math>(S)/n^{k}</math>. The set of <math>k</math>-tuple <math>(x_{1},\dotsc,x_{k})</math> such that there exist distinct indices <math>i, j</math> such that <math>x_{i} = x_{j}</math> has volume <math>0</math>, so we may restrict our attention to the <math>k</math>-tuple such that <math>x_{i} \ne x_{j}</math> for all <math>i \ne j</math>. | |
− | + | Further, the condition that <math>|x_{i} - x_{j}| > 1</math> for all <math>i \ne j</math> is invariant upon permuting the indices. Therefore we may consider the set of <math>k</math>-tuples <math>(x_{1},\dotsc,x_{k})</math> which satisfy <math>|x_{i} - x_{j}| > 1</math> for all <math>i \ne j</math> and <math>x_{1} < \dotsb < x_{k}</math>; let us denote this set by <math>T</math>. This condition is equivalent to <cmath>0 \le x_{1} < x_{2} - 1 < \dotsb < x_{i}-(i-1) < \dotsb < x_{k}-(k-1) \le n-(k-1) \;.</cmath> | |
− | + | Let us choose new variables <math>y_{i} = x_{i} - (i-1)</math> for <math>i = 1,\dotsc,k</math>; then the set of <math>k</math>-tuples <math>(y_{1},\dotsc,y_{k}) \in [0,n-(k-1)]^{k}</math> which satisfy <math>y_{1} < \dotsb < y_{k}</math> has volume <math>\frac{1}{k!}(n-(k-1))^{k}</math>. Hence <math>T</math> has volume <math>\frac{1}{k!}(n-(k-1))^{k}</math> as well and <math>S</math> has volume <math>(n-(k-1))^{k}</math>. Hence the desired probability is <math>\frac{(n-(k-1))^{k}}{n^{k}}</math>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== See Also == | == See Also == | ||
{{AMC10 box|year=2012|ab=A|num-b=24|after=Last Problem}} | {{AMC10 box|year=2012|ab=A|num-b=24|after=Last Problem}} |
Revision as of 06:54, 16 March 2012
Problem
Real numbers ,
, and
are chosen independently and at random from the interval
for some positive integer
. The probability that no two of
,
, and
are within 1 unit of each other is greater than
. What is the smallest possible value of
?
Solutions
Solution 1
Since are all reals located in
, the number of choices for each one is infinite.
Without loss of generality, assume that . Then the set of points
is a tetrahedron, or a triangular pyramid. The point
distributes uniformly in this region. If this is not easy to understand, read Solution III.
The altitude of the tetrahedron is and the base is an isosceles right triangle with a leg length
. The volume is
. As shown in the first figure in red.
Now we will find the region with points satisfying ,
,
.
Since , we have
,
.
The region of points satisfying the condition is show in the second Figure in black. It is a tetrahedron, too.
The volume of this region is .
So the probability is .
Substitude by the values in the choices, we will find that when
,
, when
,
. So
.
So the answer is D.
Solution II
This solution is motivated by the suggestive formula .
We generalize to -dimensional real space
. Suppose we are asked to find the probability that a randomly chosen
-tuple
satisfies
for all
. The total set of
-tuples in
has volume
. Let
be the set of
-tuple
which satisfy
for all
. The desired probability is Vol
. The set of
-tuple
such that there exist distinct indices
such that
has volume
, so we may restrict our attention to the
-tuple such that
for all
.
Further, the condition that for all
is invariant upon permuting the indices. Therefore we may consider the set of
-tuples
which satisfy
for all
and
; let us denote this set by
. This condition is equivalent to
Let us choose new variables
for
; then the set of
-tuples
which satisfy
has volume
. Hence
has volume
as well and
has volume
. Hence the desired probability is
.
Appendix
This solution is motivated by the suggestive formula .
We generalize it to -dimensional real space
. Suppose we are asked to find the probability that a randomly chosen
-tuple
satisfies
for all
. The total set of
-tuples in
has volume
. Let
be the set of
-tuple
which satisfies
for all
. The desired probability is Vol
. The set of
-tuple
such that there exist distinct indices
such that
has volume
, so we may restrict our attention to the
-tuple such that
for all
.
Further, the condition that for all
is invariant upon permuting the indices. Therefore we may consider the set of
-tuples
which satisfy
for all
and
; let us denote this set by
. This condition is equivalent to
Let us choose new variables
for
; then the set of
-tuples
which satisfy
has volume
. Hence
has volume
as well and
has volume
. Hence the desired probability is
.
See Also
2012 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last Problem | |
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 10 Problems and Solutions |