One of my favorite mathematical theorems (not to be confused with theory; a theorem is a statement that is true by a series of logical deductions) is the so-called “Theorem on friends and strangers”. The simplicity of the argument and the startling result is what makes it so fascinating. Below I’ll try to talk about it without using any mathematical jargon or symbols (more as an exercise for myself in exposition).
Here’s the setup: consider any party of six people. If two people have met before, call them friends; if they’ve never met before, call them strangers (there is no in-between, the semantics of what constitutes a friend versus any number of other personal relationship descriptors is besides the point). Then, the following statement is true: either three are mutual friends, or three are mutual strangers. By three people being mutual friends, I mean that each person is friends with everyone else – it’s a friendship triangle. Similarly, for three friends being mutual strangers, you can imagine it as a stranger triangle.
When I say any party of six people, I mean any. Try it at home yourself. Think of a group of six people, perhaps including yourself, perhaps by picking names at random from the front page of the New York Times. Then, designate each pair as mutual strangers or mutual friends, and you will always find a friendship triangle or a stranger triangle – no matter which six people you choose.
Eventually if you try this long enough you may start to wonder why? Let’s think about some arbitrary collection of six people standing in a room, and imagine that a piece of string connects every person to every other person. If you make them stand in a circle, it’ll look like this:
Now, paint the strings either red or blue: red if the two people the string touches are friends and blue if they’re strangers. Stated in this way, we can say that there will always be a red triangle (i.e. friendship triangle) or a blue triangle (i.e. stranger triangle). No matter how many ways you color the strings, you’ll always have either a red triangle or a blue triangle. There’s two ways we can go about convincing ourselves of this fact. Either we can try out all possible combinations of coloring the strings and count it for ourselves (long and tedious), or we can think a bit more abstractly. Let’s try the latter.
Let’s pick an arbitrary person from our group. I’ll call him A. A is attached to five strings (the five other people in the group). These five strings can be any combination of reds and blues, but there must be at least three strings with the same color (the possibilities are: 0 red and 5 blues, 1 red and 4 blues, 2 red and 3 blues, 3 reds and 2 blues, 4 reds and 1 blue, and 5 reds and 0 blues). So there’s always either at least three red strings or at least three blue strings connected to A.
Let’s take the case that there’s at least three red strings attached to A. I’ll call people on the other side of three of those red strings X, Y, and Z. If any one of X, Y, and Z are also friends with each other (i.e. have a red string) then we have a red triangle forming between those two friends and A! For example, if X and Y are friends, we have a red triangle AXY. On the other hand, if none of X, Y, and Z are mutual friends, then they are all strangers with each other, and so we have a blue triangle XYZ. So, in either case, you can find either a red triangle or a blue triangle.
On the other hand, if there are at least three blue strings attached to A, you can make the analogous argument (just changing the colors) as above, and sure enough, you can always find a red triangle or a blue triangle.
Therefore, any way that you color the strings between a group of six people, you will always find a friendship (red) triangle or a stranger (blue) triangle.
I think the theorem on friends and strangers is such a wonderful demonstration of the power of abstraction in mathematics. To paraphrase Gale and Shapley from one of my favorite papers “On college admissions and the stability of marriage”, mathematics isn’t really about numbers and figures, it’s about constructing logical arguments and being able to abstract from the particular to the general. The theorem is true for any group of six people (or really, it could be animals or anything else capable of being friends and strangers), and yet you don’t need to know anything about those six people to know that.
I should mention that the theorem on friends and strangers isn’t really a “serious” theorem by itself; it’s actually a special case of a famous theorem called Ramsey’s theorem, which deals in the general sense of exactly what we talked about in this article: coloring “connecting strings” (really called edges). Ramsey’s theorem began a whole sub-field of math in itself, now referred to as Ramsey theory, which, loosely, studies the conditions under which you can always find order in disorder. For example, in the friends and strangers theorem, we took an arbitrary group of six people (disorder) and showed, surprisingly, we can always find a pattern between them (order).
By the way, I said the other way we could convince ourselves that the theorem on friends and strangers is true is by trying out all the combinations and counting. You might be wondering how many possible combinations there are: there are in fact 78 possible ways of coloring the strings red and blue. Below is a picture of all the possibilities:
If you go through each of the drawings, you’ll find there is a red triangle or a blue triangle in each one. Or, you could rely on the tools of mathematical abstraction and save yourself the time.
Maaz's Notes 