Problem

Source: 2017 Indonesia MO Problem 2

Tags: combinatorics



Five people are gathered in a meeting. Some pairs of people shakes hands. An ordered triple of people $(A,B,C)$ is a trio if one of the following is true: A shakes hands with B, and B shakes hands with C, or A doesn't shake hands with B, and B doesn't shake hands with C. If we consider $(A,B,C)$ and $(C,B,A)$ as the same trio, find the minimum possible number of trios.