Seventeen People, Love, Etc.

Seventeen intelligent people all correspond with one another. Each person writes “letters” to each of the 16 others (emails, texts, facebook messages, carrier pigeons, whatever). In their letters, one of only three topics is discussed: love, death, or dragons. Each pair of correspondents always writes about the same one of these three topics. Prove that there is a group of at least three people who write to each other about the same topic.

Show/Hide Solution

Seventeen people, call them A, B, C, . . . , Q .

A must write at least six people on the same topic—say dragons.
So AB, AC, AD, AE, AF, AG are dragons.

Consider the five pairs BC, BD, BE, BF, BG. If there is no triangle, then none of these write about dragons, and at least three must be about the same thing—death, say. Suppose BE, BF, BG are about death.

Now consider EF, EG, and FG. If any of these is about either dragons or death, we’ll have our group of three. If none is about either dragons or death, then we have a love triad.

Draw the 17 people as dots in a circle, and connect them with three colors. This shows the situation well.

Leave a Reply

Your email address will not be published. Required fields are marked *