2005 Indonesia MO Problems/Problem 8

Revision as of 22:32, 10 October 2019 by Rockmanex3 (talk | contribs) (Solution to Problem 8 (credit to Diarmuid) -- meeting contestants)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)


There are $90$ contestants in a mathematics competition. Each contestant gets acquainted with at least $60$ other contestants. One of the contestants, Amin, state that at least four contestants have the same number of new friends. Prove or disprove his statement.

Solution (credit to Diarmuid)

In order to disprove Amin's statement, we just need to find one counterexample to Amin's claim.

Note that each person can meet up to $89$ other contestants. Thus, there are $89 - 60 + 1 = 30$ numbers that can be the number of contestants one meets.

For each number of contestants one meets, there can be at most 3 contestants (for Amin's claim to be disproven), so there can be a total of at most $90$ contestants (which is the same as the number at the competition). So we only need to check whether it's possible for that one case to happen.

The total number of meets in this scenario is $\frac12 \cdot 3 \cdot \frac{(60+89) \cdot 30}{2} = \frac{6705}{2}$, which can not happen. Therefore, there are no valid cases where at most three contestants have the same number of new friends, so Amin is correct.

See Also

2005 Indonesia MO (Problems)
Preceded by
Problem 7
1 2 3 4 5 6 7 8 Followed by
Last Problem
All Indonesia MO Problems and Solutions
Invalid username
Login to AoPS