pr.probability - probability in number theory

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.

• Next complex multiplication - A problem of Shimura and its relation to class field theory
• Previous sg.symplectic geometry - What is the meaning of symplectic structure?