Party Puzzel


Party Puzzle is a special case of Ramsey theory. This particular problem is also known under the name of the problem of the surprise-party, and can be explained as follows:

Six people in a party are chosen at random (say, A, B, C, D, E and F). Is it true that either three of them mutually know one another or three of them mutually do not know one another?

The answer can be found by only considering two simple cases:

In the first case, suppose A knows three (or more) of the others, say, B, C and D. If either B and C or C and D are mutual acquaintances, then A and the acquainted pair make three people who know one another. Otherwise B, C and D are mutual strangers.

In the second case, suppose A knows only two (or fewer) of the others, say, B and C. If either D and F or E and F are strangers, then A and the unacquainted pair make three people who do not know one another. Otherwise D, E and F are mutual acquaintances.

In just six sentences, it is clear that any party of six peoples must include at least three mutual acquaintances or three mutual strangers.

The Party Puzzle typifies the problems that Ramsey theory addresses. It can be illustrated by our game HEXI. The six people in the party are represented by six vertices on a game board. The relationship between two people - strangers or acquaintances - is represented by colored edges between the corresponding vertices. According to the result of the Party Puzzle, we know that there must be a monochrome triangle if all of the edges are colored either red or green, since either there are three people who mutually know each other or three people who mutually don't know each other. That means, our game HEXI will never end in a draw.