A random selector can only select one of the nine integers $ 1,2,\ldots,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.
Problem
Source: 1972 USAMO Problem 3
Tags: probability
futuremospper
06.03.2010 06:22
In order for the product to be divisible by $ 10$, there must be at least one $ 5$ and at least one even number among the $ n$ numbers that have come up. Let $ A$ denote the event of obtaining at least one $ 5$ and let $ B$ denote the event of obtaining at least one even number in $ n$ spins. If $ A+B, AB, A', P(E)$ denote the union of $ a,b$; the intersection of $ A,B$; the complement of $ A$; the probability of the event $ E$, respectively, we have $ P(AB) = 1 - P(A') - P(B') + P(A'B')$. Hence
\[ P(AB) = 1 - \left (\frac{8}{9} \right )^n - \left (\frac{5}{9} \right )^n + \left (\frac{4}{9} \right )^n.\]
epsilonist
07.04.2010 08:17
futuremospper wrote:
In order for the product to be divisible by $ 10$, there must be at least one $ 5$ and at least one even number among the $ n$ numbers that have come up. Let $ A$ denote the event of obtaining at least one $ 5$ and let $ B$ denote the event of obtaining at least one even number in $ n$ spins. If $ A + B, AB, A', P(E)$ denote the union of $ a,b$; the intersection of $ A,B$; the complement of $ A$; the probability of the event $ E$, respectively, we have $ P(AB) = 1 - P(A') - P(B') + P(A'B')$. Hence
\[ P(AB) = 1 - \left (\frac {8}{9} \right )^n - \left (\frac {5}{9} \right )^n + \left (\frac {4}{9} \right )^n.\]
That is simply nice. At first, I misread the problem and I thought it was about to choose $ n$ numbers from the set $ \{1,2,...,9\}$. In fact, if the problem is what I'd misread, the answer would be $ \frac{n}{9} - \frac{n(9-n)(8-n)(7-n)(6-n)}{15120}$. I have to be more careful next time.
ahaanomegas
06.12.2012 23:18
futuremospper's solution seems to be the one I was thinking of, even though I'm sure, since it's not a complete solution. I came up with something, but it's not agreeing with futuremospper.
Of the $n$ selections, at least one of them must be $5$. Of the remaining $n-1$ selections, at least $1$ of them must be even. If even one of them is even, we don't care about the other $n-2$ selections. The probability of getting a $5$ on one selection is $\tfrac{1}{9}$. Let the probability of getting at least one even number on the remaining $n-1$ tosses be $Q$. Then, $1-Q$ is the probability of getting all odds. There are $5$ odds in the set $[1,9]$, so \[ \begin {align*} Q &= 1 - \left( \dfrac {5}{9} \right)^{n-1}. \]Thus, the original probability we want is \[ \begin {align*} P &= \dfrac {1}{9} \cdot Q \\&= \dfrac {1 - \cfrac {5^{n-1}}{9^{n-1}}}{9} \\&= \dfrac {9^{n-1} - 5^{n-1}}{9 \cdot 9^{n-1} = 9^n} \\&= \boxed {\dfrac {9^{n-1} - 5^{n-1}}{9^n}}. \]
Incidentally, these contest page problems need to be sourced.
fclvbfm934
21.07.2013 04:28
ahaanomegas wrote: futuremospper's solution seems to be the one I was thinking of, even though I'm sure, since it's not a complete solution. I came up with something, but it's not agreeing with futuremospper.
Of the $n$ selections, at least one of them must be $5$. Of the remaining $n-1$ selections, at least $1$ of them must be even. If even one of them is even, we don't care about the other $n-2$ selections. The probability of getting a $5$ on one selection is $\tfrac{1}{9}$. Let the probability of getting at least one even number on the remaining $n-1$ tosses be $Q$. Then, $1-Q$ is the probability of getting all odds. There are $5$ odds in the set $[1,9]$, so \[ \begin {align*} Q &= 1 - \left( \dfrac {5}{9} \right)^{n-1}. \]Thus, the original probability we want is \[ \begin {align*} P &= \dfrac {1}{9} \cdot Q \\&= \dfrac {1 - \cfrac {5^{n-1}}{9^{n-1}}}{9} \\&= \dfrac {9^{n-1} - 5^{n-1}}{9 \cdot 9^{n-1} = 9^n} \\&= \boxed {\dfrac {9^{n-1} - 5^{n-1}}{9^n}}. \]
Incidentally, these contest page problems need to be sourced. I believe the issue here is when you did the probability as $\frac{1}{9} \cdot Q$. If you notice, the probability of getting at least one 5 is $1-\left(\frac{8}{9}\right)^{n}$ given a certain $n$. This isn't 1/9 since the probability that probability counts the probability that a particular selection is a 5, not the overall selection having at least one 5. When you do $\frac{1}{9} \cdot Q$, you would be finding the probability that a given selection is a 5, and having the rest be a sequence of having at least one even. However, we might have multiple 5's, so I think that's where the issue arises. Hope that helped
maXplanK
22.03.2018 10:00
futuremospper wrote:
In order for the product to be divisible by $ 10$, there must be at least one $ 5$ and at least one even number among the $ n$ numbers that have come up. Let $ A$ denote the event of obtaining at least one $ 5$ and let $ B$ denote the event of obtaining at least one even number in $ n$ spins. If $ A+B, AB, A', P(E)$ denote the union of $ a,b$; the intersection of $ A,B$; the complement of $ A$; the probability of the event $ E$, respectively, we have $ P(AB) = 1 - P(A') - P(B') + P(A'B')$. Hence
\[ P(AB) = 1 - \left (\frac{8}{9} \right )^n - \left (\frac{5}{9} \right )^n + \left (\frac{4}{9} \right )^n.\]
Can anyone explain $ P(AB) = 1 - P(A') - P(B') + P(A'B')$ ??
scrabbler94
22.03.2018 10:11
maXplanK wrote: Can anyone explain $ P(AB) = 1 - P(A') - P(B') + P(A'B')$ ?? This is just complementary events, coupled with inclusion-exclusion. (here $P(AB)$ denotes $P(A \cap B)$ or $P(A \land B)$, the probability events A and B occur). Also, this is a 4 1/2 year bump.
huashiliao2020
13.04.2023 03:58
The key here is to use complementary counting, since AT LEAST one 2 and AT LEAST one 5 just suggests probability 1- p(no even) - p(no 5) + p(no 2&no 5)$=1-(5/9)^n-(8/9)^n+(4/9)^n$.
hanulyeongsam
21.09.2024 08:35
1-(possibility that is not 0 to mod 2)-(possibliity that is not 0 to mod 5)+(possibility that is not 0 to mod 10) =1-(5/9)^n-(8/9)^n+(4/9)^n