Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1972 USAMO Problems/Problem 3"

m
m
 
(8 intermediate revisions by 6 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 not a factor of 2 or 5 in there is <math>\left( \frac{4}{9}\right)^n</math>. The probability that there is no 5 is <math>\left( \frac{8}{9}\right)^n</math>, so the probability that there is a 2 but no 5 is <math>\left( \frac{8}{9}\right)^n-\left( \frac{4}{9}\right)^n</math>. The probability that there is no 2 is <math>\left( \frac{5}{9}\right)^n</math>, so the probability that there is a 5 but no 2 is <math>\left( \frac{5}{9}\right)^n-\left( \frac{4}{9}\right)^n</math>. Thus the only possibility left is getting a 2 and a 5, and thus making the product divisible by 10. The probability of that is <math>1-\left( \frac{4}{9}\right)^n-\left( \frac{8}{9}\right)^n+\left( \frac{4}{9}\right)^n-\left( \frac{5}{9}\right)^n+\left( \frac{4}{9}\right)^n=\boxed{1-(8/9)^n-(5/9)^n+(4/9)^n}</math>.
+
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}}
  
 
==See Also==
 
==See Also==
 
{{USAMO box|year=1972|num-b=2|num-a=4}}
 
{{USAMO box|year=1972|num-b=2|num-a=4}}
 +
{{MAA Notice}}
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

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 $n$ selections ($n>1$), the product of the $n$ 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 $\left( \frac{8}{9}\right)^n$.

The probability that there is no 2 is $\left( \frac{5}{9}\right)^n$.

The probability that there is neither a 2 nor 5 is $\left( \frac{4}{9}\right)^n$, 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 $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}$.

Solution 2 (Recursion)

Define $a_n$ as the probability that the product is divisible by $10$ after selection $n$. Likewise, define $b_n$ and $c_n$ with divisibility by $2$ and $5$, respectively. Define $d_n$ to be the chance of dividing neither $2$ nor $5$ (and thus not $10$ either) similarly.

It is clear that $d_n=\left(\frac{4}{9}\right)^n$. Now we can define other recursive formulas:

We are able to reach a $b$ state via selecting a non-$5$ from a $b$ state and selecting an even number from a $d$ state. Thus its formula is $b_n=\frac{8}{9}b_{n-1}+\frac{4}{9}d_{n-1}$.

We are able to reach a $c$ state via selecting a non-even number from a $c$ state and selecting a $5$ from a $d$ state. Thus its formula is $c_n=\frac{5}{9}c_{n-1}+\frac{1}{9}d_{n-1}$.

Finally, to reach an $a$ state, we can select a $5$ from a $b$ state and select an even number from a $c$ state. We can also reach $a_n$ from $a_{n-1}$ because of the fact that once the product is divisible by $10$, it will always be divisible by $10$ regardless of the following selections. Thus its formula is $a_n=a_{n-1}+\frac{1}{9}b_{n-1}+\frac{4}{9}c_{n-1}$.

For our formula for $b_n$, we can substitute to find that $b_n=\frac{8}{9}b_{n-1}+\left(\frac{4}{9}\right)^n$. Solving this recursion yields $b_n=\left(\frac{8}{9}\right)^n-\left(\frac{4}{9}\right)^n$.

For our formula for $c_n$, we can substitute to find that $c_n=\frac{5}{9}c_{n-1}+\frac{1}{9}\cdot\left(\frac{4}{9}\right)^{n-1}$. Solving this recursion yields $c_n=\left(\frac{5}{9}\right)^n-\left(\frac{4}{9}\right)^n$.

Finally, substituting the values into the $a_n$ formula yields $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)$. Solving this recursion yields the final answer, $\boxed{1-\left(\frac{8}{9}\right)^n-\left(\frac{5}{9}\right)^n+\left(\frac{4}{9}\right)^n}$.

~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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1972_USAMO_Problems/Problem_3&oldid=223901"