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
-
5What are random integers? There is no uniform distribution on $\mathbb N$. – 2011-07-23
-
0By randomness, I mean $A, B, C$ are any three integers. – 2011-07-23
-
5Please try to understand what Rasmus has said. There is no uniform distribution on the integers. That means the phrase "random integers" is a nonsense, unless you give it a precise meaning. You haven't done that. Think about it. Please. – 2011-07-23
-
0Lol at user12290's response. I think it's pretty standard to interpret these questions as applying to $\{1,2,3,\dots,n\}$ as $n\to\infty$. – 2011-07-23
-
0Ok. Now I can understand the probelm. Thank you all for identify the problem. By random integer I mean that when $A$ is divided by 4, remanider may be any number from 0 to 3. – 2011-07-23
-
312 questions, not a single accepted answer. If none of the answers satisfy you, why do you keep asking questions here? – 2011-07-24
-
0I have accepted answer. Please see the comments bellow. Is there any other way? – 2011-07-24
-
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$.
-
1+1 for the good write up and for finding a reasonable interpretation of the question. – 2011-07-23
-
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.