Probability and Divisibility

Considered modulo $3$ , each person can draw a number with residue $0$ with probability $\frac{6}{19}$ , a number with residue $1$ with probability $\frac{7}{19}$ , and a number with residue $2$ with probability $\frac{6}{19}$ . It follows that the generating function for the probabilities of these residues is $\frac{1}{19}\left(6+7x+6x^2\right)$

Therefore the sum of their residues has generating function $\left(\frac{1}{19}\left(6+7x+6x^2\right)\right)^3 = \sum_{n=0}^6 a_n x^n,$ which is a degree $6$ polynomial. Therefore we just need to find the sum $a_0 + a_3 + a_6$ .

We can easily find $a_0 = a_6 = \frac{6^3}{19^3}$ and using the fact $3 = 2+1+0 = 1+1+1$ and these are the only two partitions of $3$ using $0,1,2$ , we can find $a_3 = \frac{1}{19^3} \left(7^3 + 3! \cdot (6)(7)(6)\right)$

Adding these, we find the probability is $\frac{1}{19^3}\left(6^3 + 7^3 + 3!(6)(7)(6) + 6^3\right) = \boxed{\frac{2287}{6859}}$

---

An alternate method to calculate $a_0+a_3+a_6$ :

We can also set $x=e^{2\pi i/3}$ to note that $\frac{1}{19^3}\left(6+7e^{2\pi i/3} + 6e^{4\pi i/3}\right)^3 = (a_0+a_3+a_6) + (a_1+a_4)e^{2\pi i/3} + (a_2+a_5)e^{4\pi i/3}$ and then evaluating the left-hand side by using $1+e^{2\pi i/3} + e^{4\pi i/3} = 0$ : $\frac{1}{19^3}\left(6+7e^{2\pi i/3} + 6e^{4\pi i/3}\right)^3 = \frac{1}{19^3}\left(e^{2\pi i/3}\right)^3 = \frac{1}{19^3} = \left(\frac{1}{19^3} + t\right) + te^{2\pi i/3} + te^{4\pi i/3}$

Then since the coefficients are probabilities, it follows that $1 = \left(\frac{1}{19^3} + t\right) + t + t = \frac{1}{19^3} + 3t \implies t = \frac{1}{3}\left(1 - \frac{1}{19^3}\right) = \frac{2286}{6859}$ so that $a_0+a_3+a_6 = \frac{1}{19^3} + \frac{2286}{6859} = \boxed{\frac{2287}{6859}}$

You can count the ways of rolling a total of $n$ with three 19-sided dice by looking at the coefficient of $x^n$ in the polynomial $(x + x^2 + \dots + x^{19})^3$ . Wolfram will happily expand this polynomial for you, allowing you to read off the coefficients of the $x^{3k}$ terms, which are: 1, 10, 28, 55, 91, 136, 190, 235, 262, 271, 262, 235, 190, 136, 91, 55, 28, 10, 1. Summing this up gives a total of 2287 ways of rolling a multiple of three. Divide by the total number of outcomes, $19^3 = 6859$ , for the probability.

This solution is similar to Brian's, but his is more clever because he used some modular arithmetic to simplify the polynomial whereas I just let a computer do all the work.

Let Albert choose number $a$ , Ben choose number $b$ and Charles choose number $c$ .

Then for $a + b+ c$ to be divisible by 3 , there are following three cases :

Case 1 : All the three numbers $a$ , $b$ , $c$ are divisible by 3.

Case 2 : Only one of them is divisible by 3 and sum of other two is divisible by 3.

Case 3 : No number is divisible by 3.

Case 1 : In the interval [0, 19] there are 6 integers that are divisible by 3.

$P(\text{all the three numbers are divisible by 3}) = \bigg(\large\frac{6}{19}\bigg)^3$

Case 2 : Let $3 \mid a$ and $3 \mid (b + c)$ with $3 \nmid b$ and $3 \nmid c$ .

We know any integer that is not divisible by 3 is of the form $3m+1$ or $3m+2$ . Taking $b$ and $c$ from $3m+1$ form or from $3m+2$ form will not get us $3\mid (b+c)$ . So one number should be of each form i.e. either $b$ is of the $3m+1$ form $\&$ $c$ is of $3m+2$ form or $b$ is of $3m+2$ form $\&$ $c$ is of $3m+1$ form. There are 7 numbers of the form $3m + 1)$ and 8 numbers of the form $3m+2)$ in the interval [0, 19].

$P(3 \mid a$ and $3 \mid (b+c)$ with $3 \nmid b$ and $3 \nmid c) = \LARGE\frac{6}{19}\cdot\frac{6}{19}\cdot\frac{7}{19} + \frac{6}{19}\cdot\frac{7}{19}\cdot\frac{6}{19} = \frac{2\cdot6^{2}\cdot7}{19^3}$

But $b$ or $c$ can also take place of $a$

So, $\large P(Case 2) = 3\cdot\frac{2\cdot6^2\cdot7}{19^3}$

Case 3 : Either all 3 numbers are of the form $3m+1$ or all of them is of $3m+2$ form. This condition must be satisfied for $a+b+c$ to be divisible by 3.

$P(Case 3) = \bigg(\large\frac{6}{19}\bigg)^3 + \bigg(\large\frac{7}{19}\bigg)^3$

Adding all the partial probability we get,

$P(3\mid(a+b+c)) = \LARGE\frac{6^3 + 6^3\cdot7 + 6^3 + 7^3}{19^3} = \boxed{\frac{2287}{6859}}$