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 |