If you sample $n$ integers from the range $1$ to $n$ inclusive it seems intuitive that you are likely to get a lot of numbers exactly once. Call $X_n$ the number of integers you get that occur exactly once in your sample. Is there a nice simple way of showing the following for all $n\geq 2$.
$$\exists a,b >0\text{ such that } P(X_n \leq an) \leq 2^{-bn} $$
$X_n$ is a random variable on the product space $\Omega = \{1,\ldots,n\}^n$ such that changing the value of any one coordinate of $\omega \in \Omega$ changes $X_n(\omega)$ by at most 2. This is a classic case in which martingale concentration inequalities can be applied to show that $$\mathbb{P}(|X_n - \mathbb{E}(X_n)| \geq t) \leq 2e^{-t^2/8n}.$$ So in fact $X_n$ almost always takes a value in some interval of length about $\sqrt n$. $\mathbb{E}(X_n) = n(1-1/n)^{n-1} \sim n/e$, so you can find a $b$ for any $a < 1/e$.
