Have you read The Probabilistic Method by Joel Spencer and Noga Alon?
Although originally developed by Erdős, here's an example of the probabilistic method taken from combinatoricist Po-Shen Loh (Probabilistic methods in combinatorics):
$A_1, \dotsc, A_s \subseteq \{ 1, 2, \dotsc, M \}$ such that $A_i \not \subset A_j$ and let $a_i = \lvert A_i\rvert$. 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, \dotsc, \sigma_M)$. Loh defines the event $E_i$ when $\{ \sigma_1, \dotsc, \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.
