2017 Indonesia MO Problems/Problem 2
Five people are gathered in a meeting. Some pairs of people shakes hands. An ordered triple of people 
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 and 
as the same trio, find the minimum possible number of trios.
Solution
Note that the number of trios that 
constitute (including permutations) is one, plus two if all three shake hands with each other or all three do not shake hands with each other. However, we can arrange for no triple of people to all shake hands or all not shake hands (the minimum possible "extras"), by numbering the people by integers modulo 
and forcing 
to shake hands with 
for all , and that only. Then there are 
triples overall, the minimum possible, and we are done.
See also
| 2017 Indonesia MO (Problems) | ||
| Preceded by First Problem |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 | Followed by Problem 2 |
| All Indonesia MO Problems and Solutions | ||
