Unexpected yet accessible examples of the probabilistic method What are some examples of applications of the probabilistic method to areas where it might not be expected? I was just wondering how feasible it would be to present different ideas about the probabilistic method to those who don't necessarily have a lot of math background.
One really interesting example I found was hat games, and the applications of Hamming codes and probabilities to find really slick ways to think about different hat puzzles. I was just wondering if you had any other specific examples that don't take a lot of build up to get to some interesting results.
I plan to introduce the basics of probability and expected value, but I don't think I can get to topics like the Local Lemma and Martingales. Also, I don't think I'd like to go very deep into graphs or analysis either, given that a lot of people aren't very familiar with those concepts.

Honestly, I find almost every example of the probabilistic method unexpected. I think that my favourite cute example comes in the following easy-to-state puzzle:
"Prove that any 10 points in the plane can be covered with disjoint open unit discs."
(At first glance, this might seem super obvious, but to see that it isn't true for arbitrarily many points consider like a million points distributed in the unit square, which can't be covered)
The solution by the probabilistic method comes from taking an arbitrary collection of 10 points $x_1, \dotsc, x_{10}$ and dropping a hexagonal lattice of unit discs uniformly at random on the plane (this can be made precise with a little thought).
Letting $A_i$ be the event that $x_i$ is not covered by any of the discs in the lattice, we have that $\mathbf{P}(A_i)$ is the density of "holes" between the discs in the lattice. It is a straightforward geometric exercise to see that the area of each "hole" is $\sqrt{3} - \pi/2$ and so that their density is
$$
\frac{\sqrt{3} - \pi/2}{\sqrt{3}} \approx 0.0931.
$$
In particular, we have that
\begin{align*}
\mathbf{P}(\text{All points are covered})
&= \mathbf{P}\Big(\bigcap_{i=1}^{10} A_i^c\Big) \\
&= 1 - \mathbf{P}\Big(\bigcup_{i=1}^{10} A_i\Big) \\
&\geq 1 - 10 \cdot 0.0931 \\
&> 0.
\end{align*}
Since this probability is positive, the probabilstic method yields that there must be some orientation of the lattice, and so some collection of disjoint open unit discs that cover all 10 points.
