11
$\begingroup$

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?

5 Answers 5

11

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$.

  • 0
    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.2012-09-04
2

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).

1

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}$

0

$\,\,\,\,\,\,\,\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.

  • 0
    @Do$n$Antonio thank you very much)2012-09-04
0

$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));  }