Suppose you want to throw a party, but there’s a catch; you want to invite the minimum number of people to ensure there will be a group of three mutual friends or three mutual enemies, given any two people are either friends or enemies. Since you want there to be a group of three friends or three enemies, there must be at least three people invited to the party. But if you invite three people, there could easily be a situation where two people are friends while the other is an enemy. So you must invite more than three people. The same happens when looking at four or five people at the party, though; there can be a situation where there is not a group of three friends or three enemies. Now let’s consider inviting six people. If there are six people at the party, then each person will have a relationship (whether it be friends or enemies) to five other people. Let’s look at one person’s, say Lisa’s, relationships with the others at the party. If Lisa has no friends at the party, then she will be enemies with five other people. If Lisa only has one friend at the party, then she will be enemies with four other people. If she has two friends at the party, she will be enemies with three other people. Otherwise, Lisa will have three or more friends at the party. Therefore, Lisa will always either have at least three friends or at least three enemies at the party. Now let’s consider the case when Lisa has at least three friends and look at her friends’ relationships. If any two of Lisa’s friends are friends with one another, then there is a group of three friends at the party (the same goes for when she has two enemies that are enemies with one another). If none of Lisa’s three friends are friends with one another, then those friends create a group of three enemies (the same goes for when Lisa has three enemies that are all friends with one another). No matter what, there will always be a group of three mutual friends or three mutual enemies, and so we must invite at least six people to the party to ensure this occurrence.
Modified Ramsey Numbers.
Undergraduate Review, 15, 194-210.
Available at: https://vc.bridgew.edu/undergrad_rev/vol15/iss1/18
Articles published in The Undergraduate Review are the property of the individual contributors and may not be reprinted, reformatted, repurposed or duplicated, without the contributor’s consent.