Difference between revisions of "2020 AIME I Problems/Problem 9"
(→Problem) |
|||
(15 intermediate revisions by 11 users not shown) | |||
Line 1: | Line 1: | ||
− | |||
== Problem == | == Problem == | ||
Let <math>S</math> be the set of positive integer divisors of <math>20^9.</math> Three numbers are chosen independently and at random with replacement from the set <math>S</math> and labeled <math>a_1,a_2,</math> and <math>a_3</math> in the order they are chosen. The probability that both <math>a_1</math> divides <math>a_2</math> and <math>a_2</math> divides <math>a_3</math> is <math>\tfrac{m}{n},</math> where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m.</math> | Let <math>S</math> be the set of positive integer divisors of <math>20^9.</math> Three numbers are chosen independently and at random with replacement from the set <math>S</math> and labeled <math>a_1,a_2,</math> and <math>a_3</math> in the order they are chosen. The probability that both <math>a_1</math> divides <math>a_2</math> and <math>a_2</math> divides <math>a_3</math> is <math>\tfrac{m}{n},</math> where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m.</math> | ||
− | == Solution == | + | == Solution 1 == |
+ | |||
+ | <asy> | ||
+ | size(12cm); | ||
+ | for (int x = 1; x < 18; ++x) { | ||
+ | draw((x, 0) -- (x, 9), dotted); | ||
+ | } | ||
+ | for (int y = 1; y < 9; ++y) { | ||
+ | draw((0, y) -- (18, y), dotted); | ||
+ | } | ||
+ | |||
+ | draw((0, 0) -- (18, 0) -- (18, 9) -- (0, 9) -- cycle); | ||
+ | |||
+ | pair b1, b2, b3; | ||
+ | pair c1, c2, c3; | ||
+ | pair a1, a2, a3; | ||
+ | b1 = (3, 0); b2 = (12, 0); b3 = (16, 0); | ||
+ | c1 = (0, 2); c2 = (0, 4); c3 = (0, 8); | ||
+ | a1 = b1 + c1; a2 = b2 + c2; a3 = b3 + c3; | ||
+ | |||
+ | draw(b1 -- a1 -- c1); | ||
+ | draw(b2 -- a2 -- c2); | ||
+ | draw(b3 -- a3 -- c3); | ||
+ | |||
+ | dot(a1); dot(a2); dot(a3); | ||
+ | label("$a_1$", a1, NE); | ||
+ | label("$a_2$", a2, NE); | ||
+ | label("$a_3$", a3, NE); | ||
+ | label("$b_1$", b1, S); | ||
+ | label("$b_2$", b2, S); | ||
+ | label("$b_3$", b3, S); | ||
+ | label("$c_1$", c1, W); | ||
+ | label("$c_2$", c2, W); | ||
+ | label("$c_3$", c3, W); | ||
+ | |||
+ | </asy> | ||
First, prime factorize <math>20^9</math> as <math>2^{18} \cdot 5^9</math>. Denote <math>a_1</math> as <math>2^{b_1} \cdot 5^{c_1}</math>, <math>a_2</math> as <math>2^{b_2} \cdot 5^{c_2}</math>, and <math>a_3</math> as <math>2^{b_3} \cdot 5^{c_3}</math>. | First, prime factorize <math>20^9</math> as <math>2^{18} \cdot 5^9</math>. Denote <math>a_1</math> as <math>2^{b_1} \cdot 5^{c_1}</math>, <math>a_2</math> as <math>2^{b_2} \cdot 5^{c_2}</math>, and <math>a_3</math> as <math>2^{b_3} \cdot 5^{c_3}</math>. | ||
− | In order for <math>a_1</math> to divide <math>a_2</math>, and for <math>a_2</math> to divide <math>a_3</math>, <math>b_1 | + | In order for <math>a_1</math> to divide <math>a_2</math>, and for <math>a_2</math> to divide <math>a_3</math>, <math>b_1\le b_2\le b_3</math>, and <math>c_1\le c_2\le c_3</math>. We will consider each case separately. Note that the total amount of possibilities is <math>190^3</math>, as there are <math>(18+1)(9+1)=190</math> choices for each factor. |
− | We notice that if we add <math>1</math> to <math>b_2</math> and <math>2</math> to <math>b_3</math>, then we can reach the stronger inequality <math>b_1<b_2<b_3</math>. Therefore, if we pick <math>3</math> integers from <math>0</math> to <math>20</math>, they will correspond to a unique solution, forming a 1-1 correspondence. The amount of solutions to this inequality is <math>\dbinom{21}{3}</math>. | + | We notice that if we add <math>1</math> to <math>b_2</math> and <math>2</math> to <math>b_3</math>, then we can reach the stronger inequality <math>0\le b_1<b_2+1<b_3+2\le 20</math>. Therefore, if we pick <math>3</math> integers from <math>0</math> to <math>20</math>, they will correspond to a unique solution, forming a 1-1 correspondence between the numbers <math>b_1</math>, <math>b_2+1</math>, and <math>b_3+2</math>. This is also equivalent to applying stars and bars on distributing the powers of 2 and 5 through differences. The amount of solutions to this inequality is <math>\dbinom{21}{3}</math>. |
− | The case for <math>c_1</math>,<math>c_2</math>, and <math>c_3</math> proceeds similarly for a result of <math>\dbinom{12}{3}</math>. Therefore, the probability of choosing three such factors is <cmath>\frac{\dbinom{21}{3} \cdot \dbinom{12}{3}}{190^3}.</cmath> Simplification gives <math>\frac{77}{1805}</math>, and therefore the answer is <math>\boxed{ | + | The case for <math>c_1</math>,<math>c_2</math>, and <math>c_3</math> proceeds similarly for a result of <math>\dbinom{12}{3}</math>. Therefore, the probability of choosing three such factors is <cmath>\frac{\dbinom{21}{3} \cdot \dbinom{12}{3}}{190^3}.</cmath> Simplification gives <math>\frac{77}{1805}</math>, and therefore the answer is <math>\boxed{077}</math>. |
-molocyxu | -molocyxu | ||
+ | |||
+ | == Solution 2== | ||
+ | |||
+ | Same as before, say the factors have powers of <math>b</math> and <math>c</math>. <math>b_1, b_2, b_3</math> can either be all distinct, all equal, or two of the three are equal. As well, we must have <math>b_1 \leq b_2 \leq b_3</math>. If they are all distinct, the number of cases is simply <math>{19 \choose 3}</math>. If they are all equal, there are only <math>19</math> cases for the general value. If we have a pair equal, then we have <math>2 \cdot {19\choose 2}</math>. We need to multiply by <math>2</math> because if we have two values <math>b_i < b_j</math>, we can have either <math>(b_i, b_i, b_j)</math> or <math>(b_i, b_j, b_j)</math>. | ||
+ | |||
+ | <cmath>{19 \choose 3} + 2 \cdot {19 \choose 2} + 19 = 1330</cmath> | ||
+ | |||
+ | Likewise for <math>c</math>, we get | ||
+ | |||
+ | <cmath>{10 \choose 3} + 2 \cdot {10 \choose 2} + 10 = 220</cmath> | ||
+ | |||
+ | The final probability is simply <math>\frac{1330 \cdot 220}{190^3}</math>. Simplification gives <math>\frac{77}{1805}</math>, and therefore the answer is <math>\boxed{077}</math>. | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | Similar to before, we calculate that there are <math>190^3</math> ways to choose <math>3</math> factors with replacement. Then, we figure out the number of triplets <math>{a,b,c}</math> and <math>{d,f,g}</math>, where <math>a</math>, <math>b</math>, and <math>c</math> represent powers of <math>2</math> and <math>d</math>, <math>f</math>, and <math>g</math> represent powers of <math>5</math>, such that the triplets are in non-descending order. The maximum power of <math>2</math> is <math>18</math>, and the maximum power of <math>5</math> is <math>9</math>. Using the Hockey Stick identity, we figure out that there are <math>\dbinom{12}{3}</math> ways to choose <math>d</math>, <math>f</math> and <math>g</math>, and <math>\dbinom{21}{3}</math> ways to choose <math>a</math>, <math>b</math>, and <math>c</math>. Therefore, the probability of choosing <math>3</math> factors which satisfy the conditions is <cmath>\frac{\dbinom{21}{3} \cdot \dbinom{12}{3}}{190^3}.</cmath> This simplifies to <math>\frac{77}{1805}</math>, therefore <math>m =</math> <math>\boxed{077}</math>. | ||
+ | |||
+ | ==Solution 4 (Official MAA)== | ||
+ | Note that the prime factorization of <math>20^9</math> is <math>2^{18}\cdot5^{9}.</math> The problem reduces to selecting independently the powers of <math>2</math> and the powers of <math>5</math> in the numbers <math>a_1</math>, <math>a_2</math>, and <math>a_3</math>. This is equivalent to selecting <math>3</math> exponents for the powers of <math>2</math> and <math>3</math> exponents for the powers of <math>5</math> and determining in each case the probability that the 3 exponents are chosen in nondecreasing order. Given a positive integer <math>k</math>, the probability that three integers <math>a</math>, <math>b</math>, and <math>c</math> are chosen such that <math>0\le a \le b\le c \le k</math> is the probability that <math>a</math>, <math>b+1</math>, and <math>c+2</math> are chosen such that <math>0 \le a < b+1 < c+2 \le k+2</math>. There are <math>\binom {k+3}3</math> ways to choose <math>a</math>, <math>b+1</math>, and <math>c+2</math>, so the probability that the integers are chosen in order is | ||
+ | <cmath>\frac{\binom{k+3}3}{(k+1)^3}.</cmath>Thus the probability that three chosen divisors of <math>20^9</math> satisfy the divisibility requirement is | ||
+ | <cmath>\frac{\binom{12}3}{10^3}\cdot\frac{\binom{21}3}{19^3}=\frac{12\cdot11\cdot10}{6\cdot10\cdot10\cdot10}\cdot\frac{21\cdot20\cdot19}{6\cdot19\cdot19\cdot19}=\frac{77}{1805}.</cmath>The requested numerator is <math>77.</math> | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2020|n=I|num-b=8|num-a=10}} | {{AIME box|year=2020|n=I|num-b=8|num-a=10}} | ||
+ | |||
+ | [[Category: Intermediate Combinatorics Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 23:59, 24 February 2021
Problem
Let be the set of positive integer divisors of Three numbers are chosen independently and at random with replacement from the set and labeled and in the order they are chosen. The probability that both divides and divides is where and are relatively prime positive integers. Find
Solution 1
First, prime factorize as . Denote as , as , and as .
In order for to divide , and for to divide , , and . We will consider each case separately. Note that the total amount of possibilities is , as there are choices for each factor.
We notice that if we add to and to , then we can reach the stronger inequality . Therefore, if we pick integers from to , they will correspond to a unique solution, forming a 1-1 correspondence between the numbers , , and . This is also equivalent to applying stars and bars on distributing the powers of 2 and 5 through differences. The amount of solutions to this inequality is .
The case for ,, and proceeds similarly for a result of . Therefore, the probability of choosing three such factors is Simplification gives , and therefore the answer is .
-molocyxu
Solution 2
Same as before, say the factors have powers of and . can either be all distinct, all equal, or two of the three are equal. As well, we must have . If they are all distinct, the number of cases is simply . If they are all equal, there are only cases for the general value. If we have a pair equal, then we have . We need to multiply by because if we have two values , we can have either or .
Likewise for , we get
The final probability is simply . Simplification gives , and therefore the answer is .
Solution 3
Similar to before, we calculate that there are ways to choose factors with replacement. Then, we figure out the number of triplets and , where , , and represent powers of and , , and represent powers of , such that the triplets are in non-descending order. The maximum power of is , and the maximum power of is . Using the Hockey Stick identity, we figure out that there are ways to choose , and , and ways to choose , , and . Therefore, the probability of choosing factors which satisfy the conditions is This simplifies to , therefore .
Solution 4 (Official MAA)
Note that the prime factorization of is The problem reduces to selecting independently the powers of and the powers of in the numbers , , and . This is equivalent to selecting exponents for the powers of and exponents for the powers of and determining in each case the probability that the 3 exponents are chosen in nondecreasing order. Given a positive integer , the probability that three integers , , and are chosen such that is the probability that , , and are chosen such that . There are ways to choose , , and , so the probability that the integers are chosen in order is Thus the probability that three chosen divisors of satisfy the divisibility requirement is The requested numerator is
See Also
2020 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 8 |
Followed by Problem 10 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.