Olympiad MethodsDifficulty 80-1005 tagged problems

Probabilistic Method

Probabilistic Method is the habit of proving an object exists by showing a random construction works with positive probability. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

If a random object $X$ satisfies $\Pr[X \text{ good}] > 0$ — equivalently $E[N] > 0$ for the count $N$ of good features — then a good object exists.

To prove some object with a desired property exists, build one at random and show the probability it works is positive — or that the expected count of the desired feature is positive — so at least one outcome must achieve it; this is non-constructive but often the only feasible route.

Why It Works

1
Set up a probability space whose sample points are candidate objects (e.g. random colorings, random orientations, random subsets), choosing the distribution so the quantity you care about is easy to analyze.
2
Existence form: if $\Pr[X \text{ has the property}] > 0$, then the event is nonempty, so at least one object in the space has the property — there is nothing to construct explicitly.
3
Expectation form (often via linearity of expectation): if a random object has expected value $E[N] = \mu$ for some count $N$, then some outcome has $N \ge \mu$ and some outcome has $N \le \mu$, because a random variable cannot lie strictly above (or below) its own mean everywhere.
4
A common existence variant is the union bound: $\Pr[\text{some bad event}] \le \sum \Pr[\text{bad event}_i]$; if this sum is $< 1$ then $\Pr[\text{no bad event}] > 0$, so a configuration avoiding all of them exists.

Worked Examples

Example 1

Show that some tournament on $4$ players (every pair plays once, no ties) contains at least $3$ Hamiltonian paths — orderings of all $4$ players in which each beats the next.

1
Take a random tournament: orient each of the matches independently, each direction with probability $\tfrac12$. For a fixed ordering of the $4$ players, it is a Hamiltonian path iff its $3$ consecutive games all point forward.
2
Those $3$ games are independent, so $\Pr[\text{a fixed ordering is a Hamiltonian path}] = \left(\tfrac12\right)^{3} = \tfrac18$.
3
Let $N$ count Hamiltonian paths. By linearity of expectation over the $4! = 24$ orderings, $E[N] = 24 \cdot \tfrac18 = 3$.
4
Since the average number of Hamiltonian paths over all tournaments is $3$, at least one tournament must have $N \ge 3$ — otherwise every tournament would have $N \le 2$ and the average could not reach $3$.

Answer:

Yes — because $E[N] = 4!\cdot 2^{-3} = 3$, some $4$-player tournament has at least $3$ Hamiltonian paths.

Contest level

Prove that every graph $G$ with $m$ edges contains a bipartition of its vertices into sets $A, B$ such that at least $m/2$ edges have one endpoint in each (a large cut).

1
Place each vertex independently into $A$ or $B$, each with probability $\tfrac12$.
2
Fix an edge $uv$. It crosses the cut iff $u, v$ land in different sets, which happens with probability $\tfrac12$ (two of the four equally likely placements).
3
Let $X$ be the number of crossing edges. By linearity of expectation, $E[X] = \sum_{\text{edges}} \tfrac12 = \tfrac{m}{2}$.
4
Since the average over all bipartitions is $\tfrac{m}{2}$, at least one bipartition achieves $X \ge \tfrac{m}{2}$.

Answer:

Some bipartition cuts at least $\tfrac{m}{2}$ edges (Max-Cut lower bound).

Olympiad / Challenge

Prove the Ramsey lower bound: for $k \ge 3$, $R(k,k) > 2^{k/2}$, i.e. the edges of $K_n$ with $n = \lfloor 2^{k/2}\rfloor$ can be $2$-colored with no monochromatic $K_k$.

1
Color each edge of $K_n$ red or blue independently with probability $\tfrac12$. For a fixed set of $k$ vertices, $\Pr[\text{its } \binom{k}{2} \text{ edges are all one color}] = 2\cdot 2^{-\binom{k}{2}} = 2^{1-\binom{k}{2}}$.
2
Let $X$ count monochromatic $K_k$'s. By linearity over the $\binom{n}{k}$ vertex-sets, $E[X] = \binom{n}{k}\,2^{1-\binom{k}{2}}$.
3
Bound it: $\binom{n}{k} \le \tfrac{n^k}{k!}$, and with $n \le 2^{k/2}$ one gets $n^k\,2^{-\binom{k}{2}} \le 2^{k^2/2}\cdot 2^{-(k^2-k)/2} = 2^{k/2}$, so $E[X] \le \tfrac{2^{1+k/2}}{k!}$, which is $< 1$ for every $k \ge 3$ (at $k=3$ it is $2^{2.5}/6 \approx 0.94$, and it shrinks thereafter).
4
Since $E[X] < 1$ and $X$ is a nonnegative integer, $\Pr[X = 0] > 0$. Hence some coloring has no monochromatic $K_k$, proving $R(k,k) > n \ge 2^{k/2}$.

Answer:

$R(k,k) > 2^{k/2}$ for $k \ge 3$ (Erdős's probabilistic lower bound).

Going Deeper

The expectation/union-bound idea sharpens into the Lovász Local Lemma: even when each bad event has positive probability, if the events are mostly independent and individually rare, a configuration avoiding ALL of them still exists — yielding bounds no union bound can reach.
It is the signature method of Erdős and a frequent Putnam/olympiad surprise: lower bounds for Ramsey numbers, existence of tournaments with many Hamiltonian paths, large cuts, and high-girth high-chromatic graphs all fall to it.
Pitfall: the method proves EXISTENCE, not construction — you get no explicit object. And it is only as good as the chosen distribution and bound: a sloppy union bound that sums to $\ge 1$ proves nothing, so the inequality must come out strictly $< 1$ (or $E > 0$) to conclude.

Spot the Signal

Use it when you must show some configuration exists but cannot build it explicitly.
You can describe the hard part as proving an object exists by showing a random construction works with positive probability, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by defining a random construction and bounding the probability (or expectation) of the bad event.
Name the relation that makes Probabilistic Method legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

A union bound that is too weak, or assuming an independence that isn't there.
Applying Probabilistic Method because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

If the average is good enough, some instance must be at least that good.

Try it on:

Prove an existence claim by a probabilistic expectation or counting argument.

Back to techniques

Olympiad MethodsDifficulty 80-1005 tagged problems

Probabilistic Method

Practice this technique Match my level

The Key Result

If a random object $X$ satisfies $\Pr[X \text{ good}] > 0$ — equivalently $E[N] > 0$ for the count $N$ of good features — then a good object exists.

Why It Works

1
Set up a probability space whose sample points are candidate objects (e.g. random colorings, random orientations, random subsets), choosing the distribution so the quantity you care about is easy to analyze.
2
Existence form: if $\Pr[X \text{ has the property}] > 0$, then the event is nonempty, so at least one object in the space has the property — there is nothing to construct explicitly.
3
Expectation form (often via linearity of expectation): if a random object has expected value $E[N] = \mu$ for some count $N$, then some outcome has $N \ge \mu$ and some outcome has $N \le \mu$, because a random variable cannot lie strictly above (or below) its own mean everywhere.
4
A common existence variant is the union bound: $\Pr[\text{some bad event}] \le \sum \Pr[\text{bad event}_i]$; if this sum is $< 1$ then $\Pr[\text{no bad event}] > 0$, so a configuration avoiding all of them exists.

Worked Examples

Example 1

Show that some tournament on $4$ players (every pair plays once, no ties) contains at least $3$ Hamiltonian paths — orderings of all $4$ players in which each beats the next.

1
Take a random tournament: orient each of the matches independently, each direction with probability $\tfrac12$. For a fixed ordering of the $4$ players, it is a Hamiltonian path iff its $3$ consecutive games all point forward.
2
Those $3$ games are independent, so $\Pr[\text{a fixed ordering is a Hamiltonian path}] = \left(\tfrac12\right)^{3} = \tfrac18$.
3
Let $N$ count Hamiltonian paths. By linearity of expectation over the $4! = 24$ orderings, $E[N] = 24 \cdot \tfrac18 = 3$.
4
Since the average number of Hamiltonian paths over all tournaments is $3$, at least one tournament must have $N \ge 3$ — otherwise every tournament would have $N \le 2$ and the average could not reach $3$.

Answer:

Yes — because $E[N] = 4!\cdot 2^{-3} = 3$, some $4$-player tournament has at least $3$ Hamiltonian paths.

Contest level

Prove that every graph $G$ with $m$ edges contains a bipartition of its vertices into sets $A, B$ such that at least $m/2$ edges have one endpoint in each (a large cut).

1
Place each vertex independently into $A$ or $B$, each with probability $\tfrac12$.
2
Fix an edge $uv$. It crosses the cut iff $u, v$ land in different sets, which happens with probability $\tfrac12$ (two of the four equally likely placements).
3
Let $X$ be the number of crossing edges. By linearity of expectation, $E[X] = \sum_{\text{edges}} \tfrac12 = \tfrac{m}{2}$.
4
Since the average over all bipartitions is $\tfrac{m}{2}$, at least one bipartition achieves $X \ge \tfrac{m}{2}$.

Answer:

Some bipartition cuts at least $\tfrac{m}{2}$ edges (Max-Cut lower bound).

Olympiad / Challenge

Prove the Ramsey lower bound: for $k \ge 3$, $R(k,k) > 2^{k/2}$, i.e. the edges of $K_n$ with $n = \lfloor 2^{k/2}\rfloor$ can be $2$-colored with no monochromatic $K_k$.

1
Color each edge of $K_n$ red or blue independently with probability $\tfrac12$. For a fixed set of $k$ vertices, $\Pr[\text{its } \binom{k}{2} \text{ edges are all one color}] = 2\cdot 2^{-\binom{k}{2}} = 2^{1-\binom{k}{2}}$.
2
Let $X$ count monochromatic $K_k$'s. By linearity over the $\binom{n}{k}$ vertex-sets, $E[X] = \binom{n}{k}\,2^{1-\binom{k}{2}}$.
3
Bound it: $\binom{n}{k} \le \tfrac{n^k}{k!}$, and with $n \le 2^{k/2}$ one gets $n^k\,2^{-\binom{k}{2}} \le 2^{k^2/2}\cdot 2^{-(k^2-k)/2} = 2^{k/2}$, so $E[X] \le \tfrac{2^{1+k/2}}{k!}$, which is $< 1$ for every $k \ge 3$ (at $k=3$ it is $2^{2.5}/6 \approx 0.94$, and it shrinks thereafter).
4
Since $E[X] < 1$ and $X$ is a nonnegative integer, $\Pr[X = 0] > 0$. Hence some coloring has no monochromatic $K_k$, proving $R(k,k) > n \ge 2^{k/2}$.

Answer:

$R(k,k) > 2^{k/2}$ for $k \ge 3$ (Erdős's probabilistic lower bound).

Going Deeper

The expectation/union-bound idea sharpens into the Lovász Local Lemma: even when each bad event has positive probability, if the events are mostly independent and individually rare, a configuration avoiding ALL of them still exists — yielding bounds no union bound can reach.
It is the signature method of Erdős and a frequent Putnam/olympiad surprise: lower bounds for Ramsey numbers, existence of tournaments with many Hamiltonian paths, large cuts, and high-girth high-chromatic graphs all fall to it.
Pitfall: the method proves EXISTENCE, not construction — you get no explicit object. And it is only as good as the chosen distribution and bound: a sloppy union bound that sums to $\ge 1$ proves nothing, so the inequality must come out strictly $< 1$ (or $E > 0$) to conclude.

Spot the Signal

Use it when you must show some configuration exists but cannot build it explicitly.
You can describe the hard part as proving an object exists by showing a random construction works with positive probability, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by defining a random construction and bounding the probability (or expectation) of the bad event.
Name the relation that makes Probabilistic Method legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

A union bound that is too weak, or assuming an independence that isn't there.
Applying Probabilistic Method because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

If the average is good enough, some instance must be at least that good.

Try it on:

Prove an existence claim by a probabilistic expectation or counting argument.