Difference between revisions of "1998 IMO Problems/Problem 2"
(→Solution) |
(→Solution) |
||
Line 7: | Line 7: | ||
==Solution== | ==Solution== | ||
− | |||
Let <math>c_i</math> stand for the number of judges who pass the <math>i</math>th candidate. The number of pairs of judges who agree on the <math>i</math>th contestant is then given by | Let <math>c_i</math> stand for the number of judges who pass the <math>i</math>th candidate. The number of pairs of judges who agree on the <math>i</math>th contestant is then given by |
Revision as of 14:55, 30 May 2024
Problem
In a competition, there are a contestants and b judges, where b ≥ 3 is an odd integer. Each judge rates each contestant as either “pass” or “fail”. Suppose k is a number such that, for any two judges, their ratings coincide for at most k contestants. Prove that k/a ≥ (b − 1)/(2b).
Solution
Let stand for the number of judges who pass the
th candidate. The number of pairs of judges who agree on the
th contestant is then given by
\begin{align*} {c_i \choose 2} + {{b - c_i} \choose 2} &= \frac{1}{2}\left(c_i(c_i - 1) + (b - c_i)(b - c_i - 1) \right) \\ &= \frac{1}{2}\left( c_i^2 + (b - c_i)^2 - b \right) \\ &\geq \frac{1}{2}\left( \frac{b^2}{2} - b \right) \\ &= \frac{b^2 - 2b}{4} \end{align*}
where the inequality follows from AM-QM. Since is odd,
is not divisible by
and we can improve the inequality to
Letting stand for the number of instances where two judges agreed on a candidate, it follows that
The given condition on implies that
Therefore
which simplifies to
See Also
1998 IMO (Problems) • Resources | ||
Preceded by Problem 1 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 3 |
All IMO Problems and Solutions |