Have you read [The Probabilistic Method][1] 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][2]): 

$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.


  [1]: https://www.amazon.com/Probabilistic-Wiley-Interscience-Discrete-Mathematics-Optimization/dp/0471370460
  [2]: https://www.math.cmu.edu/~ploh/docs/math/mop2009/prob-comb.pdf