Difference between revisions of "1998 IMO Problems/Problem 2"
(→Solution) |
(→Solution) |
||
Line 35: | Line 35: | ||
which simplifies to | which simplifies to | ||
− | <cmath> \frac{k}{a} \geq {b - 1}{2b}. </cmath> | + | <cmath> \frac{k}{a} \geq \frac{b - 1}{2b}. </cmath> |
==See Also== | ==See Also== | ||
{{IMO box|year=1998|num-b=1|num-a=3}} | {{IMO box|year=1998|num-b=1|num-a=3}} |
Revision as of 14:58, 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 |