Imagine a teacher who tells the class that the average score on the last test was 12 but does not hand back the papers. What can the students infer? Not much, really: it is well known that an average is a very imperfect statistical indicator and reveals little about the distribution of the data. One fact is certain, however: at least one student has a score of at least 12 (and likewise, someone has a score of at most 12); after all, if everyone had scored strictly below 12, the average of all their scores — the average reported by the teacher — would also be below 12.
This is a fairly elementary phenomenon to understand: in any set of data, there is always at least one value greater than or equal to the average. We would probably tend to overlook this fact had Paul Erdős not made it the heart of a formidably powerful tool: the probabilistic method.
Too many handshakes
To understand the principle behind this method, let's work through an example based on a classic result. The handshake theorem (also called the "friends and strangers theorem") states that, among any 6 people, there are always either 3 who have all shaken hands with one another or 3 among whom no handshakes have taken place at all\*. This result is now part of mathematical folklore, and we encourage you to prove it yourself if you have never encountered it before. You can also verify that the number 6 in this statement is optimal by exhibiting a configuration of 5 people for which the property fails — that is, one in which every group of 3 people contains 2 who have shaken hands and 2 who have not. It is therefore impossible to find either 3 people who have all shaken hands with one another or 3 among whom no handshakes have taken place. Such a configuration can be constructed explicitly.
(* This can also be stated as follows: in a group of 6 people, you can always find 3 who know each other or 3 who do not know each other.)
