UNCATEGORIZED
The Friends/Strangers Problem
I recently came across a pretty interesting puzzle that used a different kind of mathematics – called Ramsey theory – in order to tackle the problem.
Here’s the problem:
Suppose you have a group of six people. Show that you will necessarily have at least three mutual friends or three mutual strangers.
This is a sort of pigeonhole problem, which sort of means that we have to make a binary choice for each person. But what I love about this proof so much is that it’s entirely visual and fairly easy to grasp.
First, let’s imagine we have six people, who we can each represent as dots.
From there, we want to show the relationships between people. To do this, we will use lines to mark the type of relationship two people have. We will use orange to represent friends, and blue to represent strangers.
To begin, we need to start drawing lines. The first thing that you need to know is that there will always be at least three lines of any one colour that goes out from one person. The reason that this is true is because if we look at one person, the five others have no choice but to be friends or strangers. As such, every person will have at least three orange or blue lines connecting to other people, so we can simply choose one scenario of having three friends, which means three orange lines. We’ll connect them to other people at random, and so we get the following scenario.
Now that we’ve got three lines down, we know that each line represents a friendship between the people. But notice that, to show what we’ve set out to do, we only need to have one of those three friends also be friends. Put differently, if we can find a friendship such that we get a triangle of a single colour, we will prove our statement. However, it’s trivial to simply draw a triangle of one colour and say that we’re done. Instead, we need to show that we’ll be forced to make a triangle of one colour, no matter how much we don’t want to.
Suppose we consider one of those friends who were touched by our original rays. If we look at Person 4, they are friends with Person 1. Additionally, we see that Person 1 is friends with Person 3 and Person 5. Therefore, if we draw a friendship line between either Person 4 and Person 3, or Person 4 and Person 5, we will create a triangle of one colour, which means three people are friends. Since we’re trying to avoid that at all costs, we will draw two blue lines between these people, making sure that no orange triangles are created. This give us the following:
But what, we now have a problem. Look at the line we will need to eventually draw between Person 3 and Person 5. If we draw an orange line between them, then we will create an orange triangle between Person 1, Person 3, and Person 5. But on the other hand, if we draw a blue line between Person 3 and Person 5, we’ll be creating a blue triangle between Person 3, Person 4, and Person 5. Therefore, we’re stuck!
This means that no matter what, a group of six people will have at least three mutual friends or three mutual strangers. Using this technique, we’ve pigeonholed, or forced, ourselves into this situation.
What I like the most about this proof is that it’s visual and easy to understand. It’s what happens when you apply logic at each step, until you arrive at an undeniable conclusion. Furthermore, it’s a glimpse into a type of mathematics that wasn’t shown to me in school, so I thought it would be interesting to share. As I mentioned, I first saw this from a video by Raj Hansen who explains this problem in the introductory video to his Ramsey theory series. You should definitely check it out if you find this proof interesting. Personally, I’m excited to see what other kinds of applications we can find for Ramsey theory.