Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A solution of $X + Y + Z = 20$ in non-negative integers is chosen at random. What is the probability that $XYZ$ is divisible by $5$?

Edit: This happens to be an exam question. So I can't use calculators or computers and have to get the answer in less than 20 minutes while showing systematic workings. I appreciate the answers below, but can someone instruct me on solving the question given the mentioned constraints?

share|improve this question
add comment

5 Answers

up vote 10 down vote accepted

There are two questions here:

  1. How many triples of numbers $(X,Y,Z)$ add to 20? We can call this $A$.

  2. How many of these are divisible by 5? We can call this $B$.

The answer will then be $B/A$.

First we calculate $A$. Let us write $C(x)$ for the total number of ways of choosing $(X,Y,Z)$ so that $X=x$ and $X+Y+Z=20$.

There are 21 possible choices for $X$. For each such $X$, there are $21-X$ possible choices for $Y$ that make $X+Y\le 20$, namely $\{0, 1, \ldots 20-X\}$. The other choices have $X+Y>20$ and therefore $X+Y+Z>20$. Once we have chosen $X$ and $Y$ at random, there is exactly one possible choice for $Z$ that makes $X+Y+Z=20$. So we have $C(x) = 21-x$.

We want the total of $C(x)$ for each $x$ between 0 and 20: $$\begin{eqnarray} &&\sum_{x=0}^{20} C(x) \\ &=& \sum_{x=0}^{20} (21-x)\\ &=& \sum_{x=0}^{20} 21 - \sum_{x=0}^{20} x \\ &=& 441 - 210 \\ &=& 231. \end{eqnarray}$$

Now we calculate $B$. 5 is prime, so $XYZ$ is divisible by 5 if and only if one of $X$, $Y$, or $Z$ is divisible by 5. We can use inclusion-exclusion: $B$ is the sum of the cases where (at least) $X$, $Y$, or $Z$ is divisible by 5, minus the cases where (at least) two are divisible by 5, plus the cases where all three are divisible by 5. That is, $$\begin{eqnarray}B&=&D_x + D_{y} + D_z \\ &&- D_{xy} - D_{xz} - D_{yz} \\ &&+ D_{xyz}\end{eqnarray}$$

Where $D_{xy}$ denotes the number of choices of $(X,Y,Z)$ where $5\mid X$ and $5\mid Y$, and similarly for the others.

By symmetry, $D_x = D_y = D_z$, and $D_{xy} = D_{xz} = D_{yz}$. Also, it is impossible to have two of $(X,Y,Z)$ divisible by 5 without the third also being divisible by 5, so $D_{xy} = D_{xyz}$. So the previous equation reduces to:

$$B = 3D_x - 2D_{xyz}$$

We calculate $D_x$: $X$ will be a multiple of 5 whenever $X\in\{0,5,10,15,20\}$, so we want $$\begin{eqnarray} &&\sum_{5\mid X} C(X) \\ &=& \sum_{X\in\{0,5,10,15,20\}} (21-X) \\ &=& 21\cdot5 - (0+5+10+15+20) \\ &=& 105 - 50 \\ &=& 55 \end{eqnarray}$$

To calculate $D_{xyz}$ is quick because there are very few such triples, and we can enumerate them by brute force: $(0,0,20)\ldots (0,20,0), (5,0,15)\ldots (5,15,0),\ldots (20,0,0)$. This is 5+4+3+2+1 = 15.

So we have $B = 3\cdot 55 - 2\cdot 15 = 135$.

Thus the answer is $B/A = 135/231 = 45/77$.

share|improve this answer
1  
Very nice answer. +1 –  DonAntonio Sep 4 '12 at 11:00
4  
It is probably quicker to calculate $A$ by stars and bars, to get $A=\binom{22}{2}=231$. –  Henning Makholm Sep 4 '12 at 12:52
    
This is probably obvious, but for completeness I would point out that "Also, it is impossible to have two of (X, Y, Z) divisible by 5 without the third also being divisible by 5" because they're required to sum to a multiple of 5. –  hobbs Sep 4 '12 at 16:11
add comment

Here's some GAP source code that finds the probability by exhaustively enumerating the triples $(x,y,z) \in \{0,1,\ldots,20\}^3$ for which $xyz$ is divisible by $5$. (Note: there are no solutions for $x+y+z=20$ if e.g. $x>20$, so we can assume $x \leq 20$, $y \leq 20$ and $z \leq 20$.)

n:=20;;
d:=5;;

div_by_d_count:=0;;
count:=0;;

for x in [0..n] do
  for y in [0..n-x] do
    z:=n-x-y;
    count:=count+1;
    if(x*y*z mod d=0) then
      div_by_d_count:=div_by_d_count+1;
    fi;
  od;
od;
Print([n,d]," ",div_by_d_count," ",count," ",div_by_d_count/count,"\n");

The output was:

[ 20, 5 ] 135 231 45/77

So the probability is $45/77$ (which concurs with Seyhmus Güngören's earlier result).

share|improve this answer
add comment

Lets calculate the probability for $5|X$ and $Y\nmid5$ and as follows $Z\nmid5$.

Case 0: $X=0 \quad$16 possible solutions for $Y$, $Z$ follows.

Case 1: $X=5 \quad$there are 12 possible solutions

Case 2: $X=10 \quad$8 possible solutions

Case 3: $X=15 \quad$4 possible solutions

So we get $16+12+8+4=40$ solutions.

Now we can apply the same thing to Y and Z. $40*3=120$ solutions.

Now we have the only the case $5|X$ and $5|Y$ and as follows $5|Z$ left. The case can look like this: $(0,0,20), (0,5,15), (0,10,10)$ or $(5,5,10)$. Calculating all those permutations: $3+6+3+3=15$. So we get $15+120=135$ solutions.

Now we have to calculate, how many different values $X,Y,Z$ can take. $X$ can be any value between $0$ and $20$, so $21$ different values. $Y$ can have $21-X$ different values and $Z$ follows. Therefore we get: $\sum_{i=0}^{20}{21-i}=21*21-\frac{20*21}{2}=441-210=231$

So the probability is: $$\frac{135}{231}$$

share|improve this answer
add comment

$$\,\,\,\,\,\,\,\frac{45}{77}\,\,\,\,\,\,\,\,\,$$

EDIT!!!: There are altogether $231$ occurances where you have $X+Y+Z=20$ from the set $\{0,\ldots,20\}$. From this set $135$ of them gives zero reminder to $XYZ/5$. Therefore $135/231$ is the correct answer.

share|improve this answer
3  
And this mysterious result was computed how? –  Asaf Karagila Sep 4 '12 at 10:00
    
Before downvote it, read the question! it is asking the probability!! –  Seyhmus Güngören Sep 4 '12 at 10:01
3  
Poor questions are not an excuse for poor answers. (I didn't downvote, by the way) –  Asaf Karagila Sep 4 '12 at 10:01
1  
@binn how do you intend to get $X+Y+Z=20$ if you have $X>20$ or $Y>20$ or $Z>20$? does it make sense to deal with zero probabilities? –  Seyhmus Güngören Sep 4 '12 at 10:23
1  
To only write a number would hardly get you points in almost any decent exam in almost any decent high school or even university. The understood agreement is that one must also show the way to reach that solution. Here we can also give only some hints and ideas. I didn't downvote (I hardly do ever). –  DonAntonio Sep 4 '12 at 10:30
show 10 more comments

$5\mid XYZ\implies 5 \mid XY(20-X-Y) \implies 5\mid XY(X+Y)$

(1)If $5\mid X$ let $X=5a$ where $a$ is any integer, so $Y$ can have $1+20-5a$ values.

So, here the number possible values of $X,Y$ are $21+16+11+6+1=55$

(2)If $5\mid Y$ let $Y=5b$ where $b$ is any integer, leads to another $55$ values.

(3)If $5\mid Y$ and $5\mid X\implies 5(a+b)≤20\implies 0≤a+b≤4$ which has $(5+4+3+2+1)$ values= $15$ values, for example for $Y=0, X$ can be one of $0,5,10,15,20$.

So, (1)+(2)-(3) leads to $2\cdot 55 -15 =95$ values.

(4)If $5\mid (X+Y),$ but $5∤XY$

If $X=5a+r,Y=5b-r$ where $1≤r≤4$ so,$0≤a+b≤4$ and $1≤b≤4$ and $0≤a≤3$.

For each $r$, these $a,b$ can be chosen in $4+3+2+1=10$ ways,for example for $a=0, b$ can be one of $0,1,2,3$.

There can be $4$ values of $r$ ,leading to $4\cdot 10=40$ possible values of $X,Y$

So, number of the possible values of $X,Y$ such that $ 5\mid XY(X+Y)$ is $55+55-15+40=135$

As, $0 ≤ X+Y ≤ 20$, the number possible values of $X,Y$ are $(0+ 1+2+...+21)=231$, for example for $X=a, a ≤ Y ≤ 20\implies 20-a+1$ values of $Y$ .

So, the required probability $=\frac{135}{231}=\frac{45}{77}$

The answer can be validated using the following Java code:

  void process() {
    int all = 0;
    int count = 0;
    for (int x = 0; x <= 20; x++) {
        boolean xMod5 = (x % 5 == 0);
        for (int y = 0; y <= 20 - x; y++) {
            if (xMod5 || y % 5 == 0 || (x + y) % 5 == 0) {
                count++;
            }
            all++;
        }
    }
    System.out.println(String.format("%d/%d", count, all));
 }
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.