Have you read The Probabilistic Method by Joel Spencer and Noga Alon?

Although originally developed by Erdos, here's an example of the probabilistic method taken from combinatoricist Po-Shen Loh:

$A_1, \dots, A_s \subseteq \{ 1, 2, \dots, M \}$ such that $A_i \not \subset A_j$ and let $a_i = |A_i|$. Show that $$ \sum_{i=1}^s \frac{1}{\binom{M}{a_i}} \leq 1$$
The hint is to consider a random permutation $\sigma = (\sigma_1, \dots, \sigma_M)$. Loh defines the event $E_i$ when $\{ \sigma_1, \dots, \sigma_{a_i}\} = A_i$. Then he observes the events $E_i$ are mutually exclusive and that $\mathbb{P}(E_i)$ is relevant to our problem...

There are probably a lot of olympiad combinatorics problems that can be solved this way. Err... you were asking for number theory, but you will find both in Spencer and Alon's book.