Ivars Peterson's MathTrek

December 6, 1999

Party Games

The reason for this certainty lies in a mathematical proof that any gathering of six people will always automatically include one or the other of these two groupings. No such guarantee is possible when five or fewer people are present.

To prove that any party of six must contain at least three acquaintances or at least three strangers, you could write down all the possible combinations, starting with a group in which everyone knows one another. However, there are 32,768 such possibilities.

This number reflects the fact that any pair in a group of six must be either acquainted or strangers. Moreover, there are six choices of people for the first member of a pair, which leaves five choices for the second member of the pair, for a total of 30 possibilities. Because the order of the choices in a particular case doesn't matter (picking Alice first and then Barry is the same as picking Barry, then Alice), the number of possibilities that count is down to 30/2, or 15. Overall, for two possible relations (stranger or acquaintance), the number of possibilities is 2¹⁵, or 32,768.

Luckily, there's a shorter path to a proof. You need consider only two particular cases.

Suppose a party is attended by the conveniently named guests Alice, Barry, Charles, Diana, Edith, and Frank. Of the five partygoers Barry, Charles, Diana, Edith, and Frank, either at least three are friends of Alice or at least three are strangers to Alice. If Alice knows Barry, Charles, and Diana. If either Barry and Charles, Barry and Diana, or Charles and Diana are friends, then Alice and the acquainted pair make three people who know one another. Otherwise Barry, Charles, and Diana are mutual strangers.

In the second case, suppose Alice knows only two (or fewer) of the others, say, Barry and Charles. If either Diana and Edith, Diana and Frank, or Edith and Frank are strangers, then Alice and the unacquainted pair make three people who do not know one another. Otherwise, Diana, Edith, and Frank are mutual acquaintances.

This argument covers all possible cases for each of the six dinner-party guests.

The result represents a special case stemming from a branch of mathematics known as Ramsey theory, named for the mathematician Frank Plumpton Ramsey (1903-1930). Instead of talking about six people, you could consider groups consisting of any number of people. Instead of specifying just two relationships (acquaintances and strangers), you could have any number of mutually exclusive relations. For example, you could consider people (or nations) who are allies, foes, and neutral parties--representing three mutually exclusive relationships--embroiled in a widespread conflict.

In general, Ramsey theory concerns the existence of highly regular patterns in sufficiently large sets of randomly selected objects, whether they are gatherings of people, sequences of randomly generated numbers, randomly placed points in the plane, or even stars in the night sky.

It's straightforward to convert a party puzzle into a graph problem. In general, a graph consists of an array of points, or vertices, connected by straight lines, which are often called edges.

In the dinner-party case, you can draw a point for each of the six people present in the group. You can then draw lines to join the points, with each line colored red to signify two people who know each other or blue to mean the two people are strangers. When all pairs of points are joined, the resulting network of points and lines is known as a complete graph.

Depending on the relationships specified in a given case, such a graph may contain only red lines (all acquaintances), only blue lines (all strangers), or a mixture of red and blue lines joining the points. The problem comes down to proving that no matter how the lines are colored, you can't avoid producing a red triangle (representing three mutual acquaintances) or a blue triangle (three strangers).

A graph depicting relationships among six people at a party, where red lines link acquaintances and blue lines connect strangers.

Such a coloring is guaranteed for a complete graph of six points, but not necessarily for a graph of five or fewer points, as the following figure demonstrates.

This graph representing the relationships of five people shows that it is possible to obtain a gathering in which there is no group of three strangers or three acquaintances. In other words, there is no triangle in the diagram that is made up entirely of red or blue lines.

Wolfgang Slany of the Technical University of Vienna in Austria has turned the party problem into a two-person game he calls HEXI (see http://www.dbai.tuwien.ac.at/proj/ramsey/). You and your opponent take turns coloring in the uncolored edges of a complete graph laid out as a hexagon, with each player using a different color. The first person to build a triangle with all three edges of the same color loses.

Slany also has a variant of the game in which a player may choose to color in more than one edge with each turn.

Ramsey theory ensures that HEXI never ends in a draw.

Copyright 1999 by Ivars Peterson