This math puzzle will help you plan your next party

August 4, 2017 by Gary Chartrand, Arthur Benjamin And Ping Zhang, The Conversation
Mapping connections at your next shindig. Credit: unclibraries_commons

Let's say you're planning your next party and agonizing over the guest list. To whom should you send invitations? What combination of friends and strangers is the right mix?

It turns out mathematicians have been working on a version of this problem for nearly a century. Depending on what you want, the answer can be complicated.

Our book, "The Fascinating World of Graph Theory," explores puzzles like these and shows how they can be solved through graphs. A question like this one might seem small, but it's a beautiful demonstration of how graphs can be used to solve mathematical problems in such diverse fields as the sciences, communication and society.

A puzzle is born

While it's well-known that Harvard is one of the top academic universities in the country, you might be surprised to learn that there was a time when Harvard had one of the nation's best football teams. But in 1931, led by All–American quarterback Barry Wood, such was the case.

That season Harvard played Army. At halftime, unexpectedly, Army led Harvard 13–0. Clearly upset, Harvard's president told Army's commandant of cadets that while Army may be better than Harvard in football, Harvard was superior in a more scholarly competition.

Though Harvard came back to defeat Army 14-13, the commandant accepted the challenge to compete against Harvard in something more scholarly. It was agreed that the two would compete – in mathematics. This led to Army and Harvard selecting mathematics teams; the showdown occurred in West Point in 1933. To Harvard's surprise, Army won.

The Harvard–Army competition eventually led to an annual mathematics competition for undergraduates in 1938, called the Putnam exam, named for William Lowell Putnam, a relative of Harvard's president. This exam was designed to stimulate a healthy rivalry in mathematics in the United States and Canada. Over the years and continuing to this day, this exam has contained many interesting and often challenging problems – including the one we describe above.

Red and blue lines

The 1953 exam contained the following problem (reworded a bit): There are six points in the plane. Every point is connected to every other point by a line that's either blue or red. Show that there are three of these points between which only lines of the same color are drawn.

In math, if there is a collection of points with lines drawn between some pairs of points, that structure is called a . The study of these graphs is called graph theory. In graph theory, however, the points are called vertices and the lines are called edges.

Graphs can be used to represent a wide variety of situations. For example, in this Putnam problem, a point can represent a person, a red line can mean the people are friends and a blue line means that they are strangers.

Show that there are three points connected by lines of the same color. Credit: Gary Chartrand

For example, let's call the points A, B, C, D, E, F and select one of them, say A. Of the five lines drawn from A to the other five points, there must be three lines of the same color.

Say the lines from A to B, C, D are all red. If a line between any two of B, C, D is red, then there are three points with only red lines between them. If no line between any two of B, C, D is red, then they are all blue.

What if there were only five points? There may not be three points where all lines between them are colored the same. For example, the lines A–B, B–C, C–D, D–E, E–A may be red, with the others blue.

From what we saw, then, the smallest number of people who can be invited to a party (where every two people are either friends or strangers) such that there are three or three mutual strangers is six.

What if we would like four people to be mutual friends or mutual strangers? What is the smallest number of people we must invite to a party to be certain of this? This question has been answered. It's 18.

What if we would like five people to be mutual friends or mutual strangers? In this situation, the smallest number of people to invite to a party to be guaranteed of this is – unknown. Nobody knows. While this problem is easy to describe and perhaps sounds rather simple, it is notoriously difficult.

Ramsey numbers

What we have been discussing is a type of number in called a Ramsey number. These numbers are named for the British philosopher, economist and mathematician Frank Plumpton Ramsey.

Ramsey died at the age of 26 but obtained at his very early age a very curious theorem in mathematics, which gave rise to our question here. Say we have another plane full of points connected by red and blue lines. We pick two positive integers, named r and s. We want to have exactly r points where all lines between them are red or s points where all lines between them are blue. What's the smallest number of points we can do this with? That's called a Ramsey number.

For example, say we want our plane to have at least three points connected by all red lines and three points connected by all blue lines. The Ramsey number – the smallest number of we need to make this happen – is six.

When mathematicians look at a problem, they often ask themselves: Does this suggest another question? This is what has happened with Ramsey numbers – and party problems.

For example, here's one: Five girls are planning a party. They have decided to invite some boys to the party, whether they know the boys or not. How many boys do they need to invite to be certain that there will always be three boys among them such that three of the five girls are either friends with all three boys or are not acquainted with all three boys? It's probably not easy to make a good guess at the answer. It's 41!

Very few Ramsey numbers are known. However, this doesn't stop mathematicians from trying to solve such problems. Often, failing to solve one problem can lead to an even more interesting problem. Such is the life of a mathematician.

Explore further: Sorting complicated knots

Related Stories

Sorting complicated knots

July 6, 2017

From bow ties and shoelaces to sailing boats and climbing ropes, knots are not only very useful for our daily lives, but for mathematics too. IBS researchers from the Center for Geometry and Physics, within the Institute ...

Nobel Prize-winning physicist Norman Ramsey dies

November 7, 2011

(AP) -- Norman Ramsey, who shared the 1989 Nobel Prize in physics for his research into molecules and atoms that led to the creation of the atomic clock, has died in Massachusetts. He was 96.

Explained: Graphs

December 17, 2012

When most people hear the word "graph," an image springs to mind: a pair of perpendicular lines overlaid with a line, a curve, or bars of different heights.

Recommended for you

Fat from 558 million years ago reveals earliest known animal

September 20, 2018

Scientists from The Australian National University (ANU) and overseas have discovered molecules of fat in an ancient fossil to reveal the earliest confirmed animal in the geological record that lived on Earth 558 million ...

1 comment

Adjust slider to filter visible comments by rank

Display comments: newest first

1 / 5 (1) Aug 04, 2017
Whichever algorithm you choose, remember the room with the most light gets the most people. The kitchen usually wins.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.