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.
Problem
Source: 2017 Indonesia MO Problem 2
Tags: combinatorics
SJOKER
07.07.2017 11:02
if any mistake please tell me : treat the five people as five point A,B,C,D,E and consider a triangle ABC for example : color blue segment for handshake , red segment for no handshake , since a triangle has three sides , there must be two segment has the same color and thus a trio formed. (if a triangle has all three sides the same color , three trios formed and this case should be avoided) for a five points graph , there exist C(5,3) = 10 different triangles , so the minimum posibble number of trios is 10. attached graph is an example pattern for 10 trios.
Attachments:
Brudder
01.05.2022 21:14
@above I don't believe your example is right, since although the problem said $(A,B,C)$ is equivalent to $(C,B,A), $ that doesn't necessarily mean that it is also equivalent to $(B,C,A).$ Take the top three vertices for example. Your solution states that it counts as one trio, when in reality taking the permutations results in three trios.
It is easy to analyze every pair of three vertices and realize that there must be at least one trio. That means that we can lower bound the answer to $10.$ A valid construction for $10$ is simply a cycle of length 5.