Difference between revisions of "2012 AMC 10A Problems/Problem 25"

Revision as of 06:55, 16 March 2012

Problem

Real numbers $x$ , $y$ , and $z$ are chosen independently and at random from the interval $[0,n]$ for some positive integer $n$ . The probability that no two of $x$ , $y$ , and $z$ are within 1 unit of each other is greater than $\frac {1}{2}$ . What is the smallest possible value of $n$ ?

$\textbf{(A)}\ 7\qquad\textbf{(B)}\ 8\qquad\textbf{(C)}\ 9\qquad\textbf{(D)}\ 10\qquad\textbf{(E)}\ 11$

Solutions

Solution 1

Since $x,y,z$ are all reals located in $[0, n]$ , the number of choices for each one is infinite.

Without loss of generality, assume that $n\geqslant x \geqslant y \geqslant z \geqslant 0$ . Then the set of points $(x,y,z)$ is a tetrahedron, or a triangular pyramid. The point $(x,y,z)$ distributes uniformly in this region. If this is not easy to understand, read Solution II.

The altitude of the tetrahedron is $n$ and the base is an isosceles right triangle with a leg length $n$ . The volume is $V_1=\dfrac{n^3}{6}$ . As shown in the first figure in red.

$[asy] import three; unitsize(10cm); size(150); currentprojection=orthographic(1/2,-1,2/3); // three - currentprojection, orthographic draw((1,1,0)--(0,1,0)--(0,0,0),dashed+green); draw((0,0,0)--(0,0,1),green); draw((0,1,0)--(0,1,1),dashed+green); draw((1,1,0)--(1,1,1),green); draw((1,0,0)--(1,0,1),green); draw((0,0,1)--(1,0,1)--(1,1,1)--(0,1,1)--cycle,green); draw((0,0,0)--(1,0,0)--(1,1,0)--(1,1,1), red); draw((1,1,0)--(0,0,0)--(1,1,1), dashed+red); draw((1,1,1)--(1,0,0), red); [/asy]$

Now we will find the region with points satisfying $|x-y|\geqslant1$ , $|y-z|\geqslant1$ , $|z-x|\geqslant1$ .

Since $n\geqslant x \geqslant y \geqslant z \geqslant 0$ , we have $x-y\geqslant1$ , $y-z\geqslant1$ .

The region of points $(x,y,z)$ satisfying the condition is show in the second Figure in black. It is a tetrahedron, too.

$[asy] import three; unitsize(10cm); size(150); currentprojection=orthographic(1/2, -1, 2/3); // three - currentprojection, orthographic draw((1, 1, 0)--(0, 1, 0)--(0, 0, 0), dashed+green); draw((0, 0, 0)--(0, 0, 1), green); draw((0, 1, 0)--(0, 1, 1), dashed+green); draw((1, 0, 0)--(1, 0, 1), green); draw((0, 0, 1)--(1, 0, 1)--(1, 1, 1)--(0, 1, 1)--cycle, green); draw((1,0,0)--(1,1,0)--(0,0,0)--(1,1,1), dashed+red); draw((0,0,0)--(1,0,0)--(1,1,1), red); draw((1,1,1)--(1,1,0)--(1,0.9,0), red); draw((1, 0.1, 0)--(1, 0.9, 0)--(1, 0.9, 0.8)--cycle); draw((0.2, 0.1, 0)--(1, 0.9, 0.8),dashed); draw((1, 0.1, 0)--(0.2, 0.1, 0)--(1, 0.9, 0),dashed); [/asy]$

The volume of this region is $V_2=\dfrac{(n-2)^3}{6}$ .

So the probability is $p=\dfrac{V_2}{V_1}=\dfrac{(n-2)^3}{n^3}$ .

Substitude $n$ by the values in the choices, we will find that when $n=10$ , $p=\frac{512}{1000}>\frac{1}{2}$ , when $n=9$ , $p=\frac{343}{729}<\frac{1}{2}$ . So $n\geqslant 10$ .

So the answer is D.

Solution II

This solution is motivated by the suggestive formula $\frac{(n-2)^{3}}{n^{3}}$ .

We generalize to $k$ -dimensional real space $\mathbb{R}^{k}$ . Suppose we are asked to find the probability that a randomly chosen $k$ -tuple $(x_{1},\dotsc,x_{k}) \in [0,n]^{k}$ satisfies $|x_{i} - x_{j}| > 1$ for all $i \ne j$ . The total set of $k$ -tuples in $[0,n]^{k}$ has volume $n^{k}$ . Let $S$ be the set of $k$ -tuple $(x_{1},\dotsc,x_{k})$ which satisfy $|x_{i}-x_{j}|>1$ for all $i \ne j$ . The desired probability is Vol $(S)/n^{k}$ . The set of $k$ -tuple $(x_{1},\dotsc,x_{k})$ such that there exist distinct indices $i, j$ such that $x_{i} = x_{j}$ has volume $0$ , so we may restrict our attention to the $k$ -tuple such that $x_{i} \ne x_{j}$ for all $i \ne j$ .

Further, the condition that $|x_{i} - x_{j}| > 1$ for all $i \ne j$ is invariant upon permuting the indices. Therefore we may consider the set of $k$ -tuples $(x_{1},\dotsc,x_{k})$ which satisfy $|x_{i} - x_{j}| > 1$ for all $i \ne j$ and $x_{1} < \dotsb < x_{k}$ ; let us denote this set by $T$ . This condition is equivalent to $0 \le x_{1} < x_{2} - 1 < \dotsb < x_{i}-(i-1) < \dotsb < x_{k}-(k-1) \le n-(k-1) \;.$ Let us choose new variables $y_{i} = x_{i} - (i-1)$ for $i = 1,\dotsc,k$ ; then the set of $k$ -tuples $(y_{1},\dotsc,y_{k}) \in [0,n-(k-1)]^{k}$ which satisfy $y_{1} < \dotsb < y_{k}$ has volume $\frac{1}{k!}(n-(k-1))^{k}$ . Hence $T$ has volume $\frac{1}{k!}(n-(k-1))^{k}$ as well and $S$ has volume $(n-(k-1))^{k}$ . Hence the desired probability is $\frac{(n-(k-1))^{k}}{n^{k}}$ .

Appendix

This solution is motivated by the suggestive formula $\frac{(n-2)^{3}}{n^{3}}$ .

We generalize it to $k$ -dimensional real space $\mathbb{R}^{k}$ . Suppose we are asked to find the probability that a randomly chosen $k$ -tuple $(x_{1},\dotsc,x_{k}) \in [0,n]^{k}$ satisfies $|x_{i} - x_{j}| > 1$ for all $i \ne j$ . The total set of $k$ -tuples in $[0,n]^{k}$ has volume $n^{k}$ . Let $S$ be the set of $k$ -tuple $(x_{1},\dotsc,x_{k})$ which satisfies $|x_{i}-x_{j}|>1$ for all $i \ne j$ . The desired probability is Vol $(S)/n^{k}$ . The set of $k$ -tuple $(x_{1},\dotsc,x_{k})$ such that there exist distinct indices $i, j$ such that $x_{i} = x_{j}$ has volume $0$ , so we may restrict our attention to the $k$ -tuple such that $x_{i} \ne x_{j}$ for all $i \ne j$ .

Further, the condition that $|x_{i} - x_{j}| > 1$ for all $i \ne j$ is invariant upon permuting the indices. Therefore we may consider the set of $k$ -tuples $(x_{1},\dotsc,x_{k})$ which satisfy $|x_{i} - x_{j}| > 1$ for all $i \ne j$ and $x_{1} < \dotsb < x_{k}$ ; let us denote this set by $T$ . This condition is equivalent to $0 \le x_{1} < x_{2} - 1 < \dotsb < x_{i}-(i-1) < \dotsb < x_{k}-(k-1) \le n-(k-1) \;.$ Let us choose new variables $y_{i} = x_{i} - (i-1)$ for $i = 1,\dotsc,k$ ; then the set of $k$ -tuples $(y_{1},\dotsc,y_{k}) \in [0,n-(k-1)]^{k}$ which satisfy $y_{1} < \dotsb < y_{k}$ has volume $\frac{1}{k!}(n-(k-1))^{k}$ . Hence $T$ has volume $\frac{1}{k!}(n-(k-1))^{k}$ as well and $S$ has volume $(n-(k-1))^{k}$ . Hence the desired probability is $\frac{(n-(k-1))^{k}}{n^{k}}$ .

@@ Line 10: / Line 10: @@
 Since <math>x,y,z</math> are all reals located in <math>[0, n]</math>, the number of choices for each one is infinite.
-Without loss of generality, assume that <math>n\geqslant x \geqslant y \geqslant z \geqslant 0</math>. Then the set of points <math>(x,y,z)</math> is a tetrahedron, or a triangular pyramid. The point <math>(x,y,z)</math> distributes uniformly in this region. If this is not easy to understand, read Solution III.
+Without loss of generality, assume that <math>n\geqslant x \geqslant y \geqslant z \geqslant 0</math>. Then the set of points <math>(x,y,z)</math> is a tetrahedron, or a triangular pyramid. The point <math>(x,y,z)</math> distributes uniformly in this region. If this is not easy to understand, read Solution II.
 The altitude of the tetrahedron is <math>n</math> and the base is an isosceles right triangle with a leg length <math>n</math>. The volume is <math>V_1=\dfrac{n^3}{6}</math>. As shown in the first figure in red.

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

Page

Toolbox

Search