Probability Problem on Divisibility of Sum by 3
From the 3-element subsets of $\{1, 2, 3, \ldots , 100\}$ (the set of the first 100 positive integers), a subset $(x, y, z)$ is picked randomly. What is the probability that $x + y + z$ is divisible by 3?
This is a math Olympiad problem. I would welcome a good solution.
$$p=2*\frac{33}{100}\frac{32}{99}\frac{31}{98}+\frac{34}{100}\frac{33}{99}\frac{32}{98}+6*\frac{34}{100}\frac{33}{99}\frac{33}{98}$$
The above probability shows three clear parts which are the ways to add 3 numbers and yield a number divisible by 3:
- All 3 numbers divisble by 3 or of the form 3k-1. $$2*\frac{33!*97!}{30!*100!}$$
- All 3 numbers of the form 3k+1. $$\frac{34!*97!}{31!*100!}$$
- One number of each form aka: $(3j)+(3k+1)+(3l-1)=3m$ in any order. $$3!*\frac{34*33*33*97!}{100!}$$
Note that the $\frac{97!}{100!}$ that appears frequently is the number of ways to pick the 3 numbers from 100. I get:$$p=\frac{817}{2450}$$.
Note that our set has $34$ members equivalent to $1$ modulo $3$ (that is, with remainder $1$ upon division by $3$), $33$ equivalent to $2$, and $33$ equivalent to $0$.
Suppose we draw three numbers at random to create our subset. In order to get a sum divisible by $3$, we could draw any of the following sets of remainders: $$ 2,2,2\\ 1,1,1\\ 0,0,0\\ 0,1,2 \text{ (In each of }3! \text{ arrangements)} $$ So, the number of possible drawings that will yield a multiple of $3$ (order matters here) is $$ (34\times 33\times 32)+ (33\times 32\times 31)\times 2+(33\times 34 \times 33)\times (3\times 2 \times 1) $$ There are $100\times 99\times 98$ possible ways of drawing three numbers, our probability is $$ \frac{(34\times 33\times 32)+ (33\times 32\times 31)\times 2+(33\times 34 \times 33)\times (3\times 2 \times 1)}{100\times 99 \times 98} $$ Which, upon simplification, yields an answer of $\frac{817}{2450}$.
It is also possible to approach this with combinations instead of permutations. That is, noting we must have either all in one category or one from each category, our total number of possibilities is $$ \binom{33}{3} + \binom{33}{3} + \binom{34}{3} + 33\times 34 \times 33 $$ producing a probability of $$ \frac{\binom{33}{3} + \binom{33}{3} + \binom{34}{3} + 33\times 34 \times 33}{\binom{100}{3}} $$
Using the Polya Enumeration Theorem and supposing we are choosing the three-element subset from $\{1,n\}$ we see that we have the following combinatorial class (not labelled): $$\mathcal{Q} = \mathfrak{P}_3(\mathcal{Z}+\mathcal{Z}^2+\cdots+\mathcal{Z}^n).$$ Now the cycle index for the set construction is given by $$Z(A_n)-Z(S_n) = Z(S_n)_{a_k=(-1)^{k-1} a_k}.$$ For $n=3$ we get the cycle index $$ Z = \frac{1}{6} a_1^3 - \frac{1}{2} a_1 a_2 + \frac{1}{3} a_3.$$ The generating function that we substitute into $Z$ is $$z+z^2+\cdots+z^n = z(1+z+\cdots+z^{n-1}) = z \frac{1-z^n}{1-z}.$$ Therefore the generating function of all subsets by total size (not only those whose sum is divisible by three) is $$f(z) = \frac{1}{6} \left(z \frac{1-z^n}{1-z}\right)^3 - \frac{1}{2} z \frac{1-z^n}{1-z} z^2 \frac{1-z^{2n}}{1-z^2} + \frac{1}{3} z^3 \frac{1-z^{3n}}{1-z^3}.$$ We need the value at $z=1$ of this generating function (excluding powers not divisible by three). Setting $w=e^{2\pi i/3}$ we see that the total count of the subsets with sum divisible by three is $$\left.\frac{1}{3}(f(wz)+f(w^2z)+f(w^3z))\right|_{z=1}.$$ Now suppose that $$n\equiv r\bmod 3$$ where $r\in(1,2,3).$ Then we have that $$f(wz)_{z=1} = \frac{1}{6} \left(\sum_{q=1}^r w^q\right)^3 -\frac{1}{2} \left(\sum_{q=1}^r w^q\right) \left(\sum_{q=1}^r w^{2q}\right) +\frac{1}{3}n$$ and that $$f(w^2z)_{z=1} = \frac{1}{6} \left(\sum_{q=1}^r w^{2q}\right)^3 -\frac{1}{2} \left(\sum_{q=1}^r w^{2q}\right) \left(\sum_{q=1}^r w^{4q}\right) +\frac{1}{3}n$$ and $$f(w^3z)_{z=1} = \frac{1}{6}n^3-\frac{1}{2}n^2+\frac{1}{3}n = {n\choose 3}.$$ Doing the arithmetic we find that $$f(wz)_{z=1} + f(w^2z)_{z=1} = \frac{1}{3} \frac{w^{2r}-w^r}{w^2-w} - \left( \frac{w^{2r}-w^r}{w^2-w}\right)^2 +\frac{2}{3} n.$$ This gives for the total count the value $$\frac{1}{9} \frac{w^{2r}-w^r}{w^2-w} - \frac{1}{3} \left( \frac{w^{2r}-w^r}{w^2-w}\right)^2 + \frac{2}{9} n +\frac{1}{3} {n\choose 3}$$ which can be simplified further to $$\frac{1}{9} (r-3)(3r-2) + \frac{2}{9} n +\frac{1}{3} {n\choose 3}$$ which produces the sequence $$0, 0, 1, 2, 4, 8, 13, 20, 30, 42, 57, 76, 98, 124, 155, 190, 230, 276, 327, 384,\ldots$$ which is A061866 from the OEIS. We thus obtain the following formula for the probability $$\frac{1}{3} +{n\choose 3}^{-1} \left(\frac{1}{9} (r-3)(3r-2) + \frac{2}{9} n\right).$$ Substituting $n=100$ in the above we get the final result, $$\frac{817}{2450}.$$
Well, since there are two competing theoretical answers (now resolved), I thought it might be fun to offer a a quick computational check, here using Mathematica:
Count[Map[Total, Subsets[Range[100],{3}]]/3, _Integer] / Binomial[100,3]
817/2450
This takes about 0.2 seconds to evaluate.