People Triangle: Like, Dislike

Six people who all know each other are in a room. Every two people either like each other or dislike each other. Show that there is a group of three people who either all like each other or all dislike each other.

Show/Hide Solution

We put our six people on a circle. We connect people who like each other with chords. In the figure, A likes everybody. Now it’s clear that if any two among B, C, D, E, and F like each other, then we’ll have a triangle, indicating the set of three who like each other. We added dotted lines to show, then, that a dotted-line triangle is inevitable.

Suppose A is friends with everybody except B. You can work out what happens. Here in the second figure, A is friends with only D, E, and F. If any of D, E, and F are friends we have a triangle. So then they must describe each other — and we still have a (dotted) triangle.

All possibilities lead to some triangle, solid or dotted.

Leave a Reply

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