<s>[INST] 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.
 [/INST] 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}.$$
</s>