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

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


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