Advanced book on Mathematics Olympiad

6

6 Combinatorics and Probability....................................

We conclude the book with combinatorics. First, we train combinatorial skills in set

theory and geometry, with a glimpse at permutations. Then we turn to some specific

techniques: generating functions, counting arguments, the inclusion–exclusion principle.

A strong accent is placed on binomial coefficients.

This is followed by probability, which, in fact, should be treated separately. But the

level of this book restricts us to problems that use counting, classical schemes such as the

Bernoulli and Poisson schemes and Bayes’ theorem, recurrences, and some minor geo-

metric considerations. It is only later in the development of mathematics that probability

loses its combinatorial flavor and borrows the analytical tools of Lebesgue integration.

6.1 Combinatorial Arguments in Set Theory and Geometry...............

6.1.1 Set Theory and Combinatorics of Sets.......................

A first example comes from the 1971 German Mathematical Olympiad.

Example.Given 2n−^1 subsets of a set withnelements with the property that any three

have nonempty intersection, prove that the intersection of all the sets is nonempty.

Solution.LetS ={A 1 ,A 2 ,...,A 2 n− 1 }be the family of subsets of the setAwithn

elements. BecauseShas 2n−^1 elements, for any subsetBofA, eitherBor its complement

Bcis inS. (They cannot both be inSby the other hypothesis.)

So ifAiandAjare inS, then eitherAi∩Ajis inS, or its complement is inS. If the

complement is inSthenAi∩Aj∩(Ai∩Aj)cis empty, contradicting the fact that the

intersection of any three elements ofSis nonempty. HenceAi∩Aj∈S.

We will now show by induction onkthat the intersection of anyksets inSis

nontrivial. We just proved the base casek=2. Assume that the property is true for

anyk−1 elements ofS, and let us prove it forAi 1 ,Ai 2 ,...,Aik∈S. By the induction