the basic probabilistic method
The probabilistic method is a non-constructive proof technique pioneered by Paul Erdos for proving the existence of combinatorial objects with prescribed properties. The paradox it resolves is this: sometimes we want to show that an object with a certain property exists, but we have no idea how to build one explicitly. The method sidesteps construction entirely. Instead of building the object, we set up a probability space of candidate objects, and we show that a randomly chosen candidate has the desired property with positive probability. If the probability of a property is strictly greater than zero, then at least one object in the sample space must have that property — because an event of probability zero is exactly the union of outcomes none of which occur.
The basic form is almost trivially simple once stated, which is why it is so powerful. Let Omega be a finite (or general) probability space whose points are the objects of interest. Suppose we want an object satisfying property A. We choose the object at random according to some distribution and compute P(A). If P(A) > 0, an object satisfying A exists. Equivalently, in the complementary form, if we can show P(no object has the property) = P(union of bad events) < 1, then with positive probability all bad events are avoided, so a good object exists. The whole craft lies in choosing the right random model and bounding the probability — typically with a union bound P(union of B_i) <= sum P(B_i) in the simplest arguments.
What makes this revolutionary is that it converts existence questions in discrete mathematics into probability calculations, often yielding bounds far better than any known explicit construction. Erdos's 1947 lower bound for Ramsey numbers is the founding example: a random two-colouring of the edges of the complete graph on n vertices avoids a monochromatic clique of size k with positive probability when n is below a threshold roughly 2^(k/2), proving R(k,k) > 2^(k/2) in two lines, a bound that explicit constructions could not match for over half a century. The honest caveat is that the method proves existence without exhibiting a witness; turning a probabilistic existence proof into an efficient algorithm (derandomisation) is a separate and often hard problem.
Tournaments and the property S_k: a tournament is an orientation of the complete graph (every pair plays, one beats the other). We claim that for every k there is a tournament where, for any set of k players, some player beats all of them. Take a random tournament on n players (each edge oriented by a fair coin). For a fixed k-set, the chance no single other player beats all of them is (1 - 2^(-k))^(n-k); union over all k-sets gives expected number of bad k-sets at most C(n,k)(1 - 2^(-k))^(n-k), which is below 1 for n large enough. Hence a tournament with property S_k exists, with no explicit construction needed.
Positive probability (or expected count below 1) forces existence — the argument never names the object.
The method proves existence, not uniqueness or abundance, and gives no explicit witness; a 'derandomised' construction matching the probabilistic bound can be far harder to find than the existence proof itself.