2017 Indonesia MO Problems/Problem 2

Revision as of 00:18, 10 October 2020 by Duck master (talk | contribs) (created page w/ solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

Solution

Note that the number of trios that $\{A, B, C\}$ 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 $5$ and forcing $x$ to shake hands with $x + 1$ for all $x$, and that only. Then there are $\binom{5}{3} = 10$ 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