1972 USAMO Problems/Problem 3

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.

1972 USAMO (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1972 USAMO Problems/Problem 3

Contents

Problem

Solution 1

Solution 2 (Recursion)

See Also