Let $A,B, C $ be three random integers. What is the probability $ABC \equiv 0 \bmod(4)$?
Probability of the event of product of three integers to be divisible by 4
-
1@user12290: Yes, there's a checkbox next to an answer that essentially says 'this is the answer I accept'; you can check one answer per question. None of the answers on this question, for instance, have actually been _marked_ as accepted; simply thanking the user in comments isn't enough. (As for why to accept an answer, there are any number of reasons, not least to aid new readers) – 2011-07-26
3 Answers
There is no probability distribution that gives "equal weight" to all integers. So the problem is technically wrong!
However, we are probably being invited to assume that the remainder when any of $A$, $B$, and $C$ is divided by $4$ is equally likely to be $0$, $1$, $2$, or $3$. This implies that any of these probabilities is equal to $1/4$.
Without explicitly saying so, the problem expects us to assume that the remainders of $A$, $B$, and $C$ are independent.
We imagine $A$, $B$, and $C$ to be picked one after the other.
It is a little easier to find the probability that the event we are interested in does not happen.
We have $ABC$ is not divisible by $4$ if (i) $A$, $B$, and $C$ are all odd or (ii) Two of $A$, $B$, $C$ are odd and the remaining one has remainder $2$ on division by $4$.
Case (i): The probability that any particular number is odd is $1/2$, so the probability they are all odd is $(1/2)^3$.
Case (ii): Let's find the probability that $A$ has remainder $2$, and $B$ and $C$ are odd. Easily, this is $(1/4)(1/2)^2$. We get the same probability for $B$ having remainder $2$ and the rest odd, and for $C$ having remainder $2$ with the rest odd. This gives a total of $3/16$.
Add up. The probability the product is not divisible by $4$ is $5/16$.
Thus the probability that the product is divisible by $4$ is $11/16$.
-
0Thank you very much for your help. I can understand the approach. Thank you again. – 2011-07-23
Random integers with what distribution? The natural default assumption would be "uniform", but there is no uniform distribution over the integers.
However, let's assume that the distribution is flat enough that the remainders of $A$, $B$ and $C \pmod 4$ are uniformly distributed over $\mathbb Z / 4 \mathbb Z$. Then $ABC \equiv 0 \pmod 4$ iff either
- any one of $A$, $B$ and $C$ equals $0 \pmod 4$, or
- at least two of $A$, $B$ and $C$ equal $2 \pmod 4$.
Conversely, $ABC \not\equiv 0 \pmod 4$ iff either
- all of $A$, $B$ and $C$ are odd, or
- two of $A$, $B$ and $C$ are odd and the third equals $2 \pmod 4$.
These possibilities are mutually exclusive; the first occurs with probability $(2/4)^3 = 1/8$, while the second occurs with probability $3 \cdot (1/4) \cdot (2/4)^2 = 3/16$. Thus, $P(ABC \not\equiv 0 \mod 4) = 1/8 + 3/16 = 5/16$, and so $P(ABC \equiv 0 \mod 4) = 1-P(ABC \not\equiv 0 \mod 4) = 11/16$.
This is the "brute force" approach, without trying any clever idea, just enumerating possibilities.
I think you will get these possibilities for the remainders modulo 4:
0BC ... 16=4·4 possibilities
A0C ... 12=3·4 possibilities (I do not want to double count anything, so I avoid things that have already been counted. That's why I can choose only A=1,2,3)
AB0 ... 9=3·3 possibilites
22C ... 3 possibilities
2B2 ... 2 possibilities (I have to omit B=0 and B=2, which have already been counted.)
A22 ... 2 possibilities
So I get $\frac{44}{4^3}=\frac{11}{16}$, if I did not miss something.