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

Revision as of 07:54, 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 III.

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 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>.
-===Solution III===
+===Appendix===
+This solution is motivated by the suggestive formula <math>\frac{(n-2)^{3}}{n^{3}}</math>.
-Because <math>x</math>, <math>y</math>, and <math>z</math> are chosen independently and at random from the interval <math>[0,n]</math>, which means that  <math>x</math>, <math>y</math>, and <math>z</math> distributes uniformly and independently in the interval <math>[0,n]</math>. So the point <math>(x, y, z)</math> distributes uniformly in the cubic <math>0\leqslant x, y, z \leqslant n</math>, as shown in the figure below. The volume of this cubic is <math>V_0=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>.
-[[File:Cubic.png]]
+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>.
-As we want to find the probablity of the incident
-<math>A=\big\{ |x-y|\geqslant 1, |y-z|\geqslant1, |z-x|\geqslant 1 \big\}</math>,
-we should find the volume of the region of points such that <math>|x-y|\geqslant 1</math>, <math>|y-z|\geqslant 1</math>, <math>|z-x|\geqslant 1</math> and <math>0\leqslant x, y, z \leqslant n</math>.
-Now we will find the region  <math>\big\{ (x,y,z)\ | \ 0\leqslant x, y, z \leqslant n, |x-y|\geqslant 1, |y-z|\geqslant 1, |z-x|\geqslant 1 \big\} </math>.
-The region can be generated by cuting off 3 slices corresponding to <math>|x-y|< 1</math>, <math>|y-z|< 1</math>, and <math>|z-x|< 1</math>, respectively, from the cubic.
-After cutting off a slice corresponding to <math>|x-y|< 1</math>, we get two triangular prisms, as shown in the figure.
-[[File:2.png]]
-In order to observe the object clearly, we rotate the object by the <math>z</math> axis, as shown.
-[[File:3.png]]
-We can draw the slice corresponding to <math>|y-z|< 1</math> on the object.
-[[File:4B.png]]
-After cutting off the slice corresponding to <math>|y-z|< 1</math>, we have 4 pieces left.
-[[File:5.png]]
-After cutting off the slice corresponding to <math>|z-x|< 1</math>, we have 6 congruent triangular prisms.
-[[File:6B.png]]
-Here we draw all the pictures in colors in order to explain the solution clearly. That does not mean that the students should do it in the examination. They can draw a figure with lines only, as shown below.
-[[File:7.png]]
-Every triangular pyramid has an altitude <math>n-2</math> and a base of isoceless right triangle with leg length <math>n-2</math>, so the volume is <math>(n-2)^3/6</math>.
-Then the volume of the region <math>\big\{ (x,y,z)\ | \ 0\leqslant x, y, z \leqslant n, |x-y|\geqslant 1, |y-z|\geqslant 1, |z-x|\geqslant 1 \big\}</math> is <math>V_A=6\times(n-2)^3/6</math>=<math>(n-2)^3</math>.
-So the probability of the incident <math>A</math> is <math>P(A)=\dfrac{V_A}{V_0}</math>=<math>\dfrac{(n-2)^3}{n^3}</math>.
-Then we can get the answer the same way as Solution I.
-The answer is D.
-If there is no choice for selection, we can also find the minimum value of the integer <math>n</math> if we do not substitude <math>n</math> by the possible values one by one.
-Let <math>P(A)>1/2</math>, i.e., <math>\dfrac{(n-2)^3}{n^3}>\dfrac{1}{2}</math>,  so <math>\dfrac{n-2}{n}>\dfrac{1}{\sqrt[^3\!]{2}}</math>, or <math>1-\dfrac{2}{n}>\dfrac{1}{\sqrt[^3\!]{2}}</math>, hence <math>n>\dfrac{2\sqrt[^3\!]{2}}{\sqrt[^3\!]{2}-1}</math>.
-Now we will estimate the value of <math>\dfrac{2\sqrt[^3\!]{2}}{\sqrt[^3\!]{2}-1}</math> without a calculator.
-Since <math>a^3-1</math>=<math>(a-1)(a^2+a+1)</math>, so
-<math>\dfrac{2\sqrt[^3\!]{2}}{\sqrt[^3\!]{2}-1}</math>
-=<math>\dfrac{2\sqrt[^3\!]{2}\times\left( \sqrt[^3\!]{2}^2+\sqrt[^3\!]{2}+1\right)}{\left( \sqrt[^3\!]{2}-1\right)\left( \sqrt[^3\!]{2}^2+\sqrt[^3\!]{2}+1\right)}</math>
-=<math>\dfrac{2\times\left( 2+\sqrt[^3\!]{2}^2+\sqrt[^3\!]{2}\right)}{ \sqrt[^3\!]{2}^3-1}</math>
-=<math>2\times\left( 2+\sqrt[^3\!]{4}+\sqrt[^3\!]{2}\right)</math>.
-Now we would get the approximation of <math>\sqrt[^3\!]{4}</math> and <math>\sqrt[^3\!]{2}</math>.
-In order to avoid compicated computation, we get the approximation with one decimal digit only.
-Estimation of <math>\sqrt[^3\!]{2}</math>.
-Since <math>1.5^3=2.25\times1.5>2</math>, so <math>1<\sqrt[^3\!]{2}<1.5</math>.
-The mean of 1 and 1.5 with one decimal digit is about 1.3 .
-As <math>1.3^3=1.69\times 1.3=2.197>2</math>, so <math>1<\sqrt[^3\!]{2}<1.3</math>.
-The mean of 1 and 1.3 with one decimal digit is about 1.2.
-As <math>1.2^3=1.44\times 1.2=1.728<2</math>, so <math>1.2<\sqrt[^3\!]{2}<1.3</math>.
-Estimation of <math>\sqrt[^3\!]{4}</math>.
-As <math>\sqrt[^3\!]{4}=\sqrt[^3\!]{2}^2</math>, so <math>1.2^2<\sqrt[^3\!]{4}<1.3^2</math>,
-then <math>1.24<\sqrt[^3\!]{4}<1.69</math>.
-As <math>1.5^3=2.25\times 1.5=3.375<4</math>, so <math>1.5<\sqrt[^3\!]{4}<1.69</math>.
-The mean of 1.5 and 1.69 with one decimal digit is about 1.6.
-As <math>1.6^3=(16/10)^3=(2^4/10)^3=2^12/10^3=4\times 2^10/10^3=4\times 1.024>4</math>, so <math>1.5<\sqrt[^3\!]{4}<1.6</math>.
-Then <math>2\times(2+1.5+1.2)<2\times\left(2+\sqrt[^3\!]{4}+\sqrt[^3\!]{2}\right)<2\times(2+1.6+1.3)</math>, i.e.,
-<math>9.4<2\times\left(2+\sqrt[^3\!]{4}+\sqrt[^3\!]{2}\right)<9.8</math>,
-As <math>n>2\times\left(2+\sqrt[^3\!]{4}+\sqrt[^3\!]{2}\right)</math>, So the minimal value of integer <math>n</math> is 10.
 == See Also ==
 {{AMC10 box|year=2012|ab=A|num-b=24|after=Last Problem}}

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