3080.31 – Seventeen Opinionated People

Seventeen opinionated people use a certain social networking app. Using this app, they send each other posts on various topics. Strangely enough, everyone's posts are on only three topics: love, death and dragons. Finally, and this is the kicker, each pair of two people amongst our seventeen, opinionated people, always posts to the other person in the pair on the same one of these three topics.

Prove that there is a group of at least $three$ people who post with each other on the same topic.

Solution

Let the 17 people be named $A, B, \ldots, Q$ . Now $A$ sends posts to 16 people, and so posts with at least 6 people on the same topic. Let's say that $A$ posts with the six people $B, C, D, E, F, G$ on, say, dragons.

Now among the six people $B, C, \dots, G$ , if there are two who post to each other about dragons, then we are done. That pair plus $A$ are the subgroup of three we seek. Otherwise, these six people ( $B, C, \dots, G$ ) only correspond about love and death. I claim that in this group of 6 there is a subgroup of at least three that post only on love OR post only on death. If this is so, then once again we will be done.

We've made progress. We have reduced the problem by one dimension. Now we have 6 people (instead of 17) and two topics (instead of 3).

To complete the proof, take $B$ . In the subgroup ( $B, C, \dots, G$ ), $B$ corresponds with 5 others so there must be three (say: $D$ , $E$ , and $F$ ) with whom $B$ posts on the same topic (say: love). Now if there is a pair among $D$ , $E$ , and $F$ who also correspond on love, then we are done. Otherwise, all three correspond amongst themselves only on death. But then we are done too.

Now we are really really done.