Difference between revisions of "1972 USAMO Problems/Problem 3"
(→Solution) |
m |
||
(5 intermediate revisions by 3 users not shown) | |||
Line 2: | Line 2: | ||
A random number selector can only select one of the nine integers 1, 2, ..., 9, and it makes these selections with equal probability. Determine the probability that after <math>n</math> selections (<math>n>1</math>), the product of the <math>n</math> numbers selected will be divisible by 10. | A random number selector can only select one of the nine integers 1, 2, ..., 9, and it makes these selections with equal probability. Determine the probability that after <math>n</math> selections (<math>n>1</math>), the product of the <math>n</math> numbers selected will be divisible by 10. | ||
− | ==Solution== | + | ==Solution 1== |
For the product to be divisible by 10, there must be a factor of 2 and a factor of 5 in there. | For the product to be divisible by 10, there must be a factor of 2 and a factor of 5 in there. | ||
− | The probability that there is | + | The probability that there is no 5 is <math>\left( \frac{8}{9}\right)^n</math>. |
+ | The probability that there is no 2 is <math>\left( \frac{5}{9}\right)^n</math>. | ||
+ | The probability that there is neither a 2 nor 5 is <math>\left( \frac{4}{9}\right)^n</math>, which is included in both previous cases. | ||
+ | |||
+ | The only possibility left is getting a 2 and a 5, making the product divisible by 10. | ||
+ | By complementarity and principle of inclusion-exclusion, the probability of that is <math>1- \left( \left( \frac{8}{9}\right)^n + \left( \frac{5}{9}\right)^n - \left( \frac{4}{9}\right)^n\right)=\boxed{1-(8/9)^n-(5/9)^n+(4/9)^n}</math>. | ||
+ | |||
+ | ==Solution 2 (Recursion)== | ||
+ | Define <math>a_n</math> as the probability that the product is divisible by <math>10</math> after selection <math>n</math>. Likewise, define <math>b_n</math> and <math>c_n</math> with divisibility by <math>2</math> and <math>5</math>, respectively. Define <math>d_n</math> to be the chance of dividing neither <math>2</math> nor <math>5</math> (and thus not <math>10</math> either) similarly. | ||
+ | |||
+ | It is clear that <math>d_n=\left(\frac{4}{9}\right)^n</math>. Now we can define other recursive formulas: | ||
+ | |||
+ | We are able to reach a <math>b</math> state via selecting a non-<math>5</math> from a <math>b</math> state and selecting an even number from a <math>d</math> state. Thus its formula is <math>b_n=\frac{8}{9}b_{n-1}+\frac{4}{9}d_{n-1}</math>. | ||
+ | |||
+ | We are able to reach a <math>c</math> state via selecting a non-even number from a <math>c</math> state and selecting a <math>5</math> from a <math>d</math> state. Thus its formula is <math>c_n=\frac{5}{9}c_{n-1}+\frac{1}{9}d_{n-1}</math>. | ||
+ | |||
+ | Finally, to reach an <math>a</math> state, we can select a <math>5</math> from a <math>b</math> state and select an even number from a <math>c</math> state. We can also reach <math>a_n</math> from <math>a_{n-1}</math> because of the fact that once the product is divisible by <math>10</math>, it will always be divisible by <math>10</math> regardless of the following selections. Thus its formula is <math>a_n=a_{n-1}+\frac{1}{9}b_{n-1}+\frac{4}{9}c_{n-1}</math>. | ||
+ | |||
+ | For our formula for <math>b_n</math>, we can substitute to find that <math>b_n=\frac{8}{9}b_{n-1}+\left(\frac{4}{9}\right)^n</math>. Solving this recursion yields <math>b_n=\left(\frac{8}{9}\right)^n-\left(\frac{4}{9}\right)^n</math>. | ||
+ | |||
+ | For our formula for <math>c_n</math>, we can substitute to find that <math>c_n=\frac{5}{9}c_{n-1}+\frac{1}{9}\cdot\left(\frac{4}{9}\right)^{n-1}</math>. Solving this recursion yields <math>c_n=\left(\frac{5}{9}\right)^n-\left(\frac{4}{9}\right)^n</math>. | ||
+ | |||
+ | Finally, substituting the values into the <math>a_n</math> formula yields <math>a_n=a_{n-1}+\frac{1}{9}\left(\left(\frac{8}{9}\right)^{n-1}+4\cdot\left(\frac{5}{9}\right)^{n-1}-5\cdot\left(\frac{4}{9}\right)^{n-1}\right)</math>. Solving this recursion yields the final answer, <math>\boxed{1-\left(\frac{8}{9}\right)^n-\left(\frac{5}{9}\right)^n+\left(\frac{4}{9}\right)^n}</math>. | ||
+ | |||
+ | ~eevee9406 | ||
{{alternate solutions}} | {{alternate solutions}} |
Latest revision as of 11:26, 29 July 2024
Problem
A random number selector can only select one of the nine integers 1, 2, ..., 9, and it makes these selections with equal probability. Determine the probability that after selections (), the product of the numbers selected will be divisible by 10.
Solution 1
For the product to be divisible by 10, there must be a factor of 2 and a factor of 5 in there.
The probability that there is no 5 is .
The probability that there is no 2 is .
The probability that there is neither a 2 nor 5 is , which is included in both previous cases.
The only possibility left is getting a 2 and a 5, making the product divisible by 10. By complementarity and principle of inclusion-exclusion, the probability of that is .
Solution 2 (Recursion)
Define as the probability that the product is divisible by after selection . Likewise, define and with divisibility by and , respectively. Define to be the chance of dividing neither nor (and thus not either) similarly.
It is clear that . Now we can define other recursive formulas:
We are able to reach a state via selecting a non- from a state and selecting an even number from a state. Thus its formula is .
We are able to reach a state via selecting a non-even number from a state and selecting a from a state. Thus its formula is .
Finally, to reach an state, we can select a from a state and select an even number from a state. We can also reach from because of the fact that once the product is divisible by , it will always be divisible by regardless of the following selections. Thus its formula is .
For our formula for , we can substitute to find that . Solving this recursion yields .
For our formula for , we can substitute to find that . Solving this recursion yields .
Finally, substituting the values into the formula yields . Solving this recursion yields the final answer, .
~eevee9406
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See Also
1972 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.