Difference between revisions of "1998 IMO Problems/Problem 2"
(→Solution) |
m (latex) |
||
(5 intermediate revisions by one other user not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | In a competition, there are < | + | In a competition, there are <math>a</math> contestants and <math>b</math> judges, where <math>b\ge3</math> is an odd |
− | integer. Each judge rates each contestant as either “pass” or “fail”. Suppose < | + | integer. Each judge rates each contestant as either “pass” or “fail”. Suppose <math>k</math> |
− | is a number such that, for any two judges, their ratings coincide for at most < | + | is a number such that, for any two judges, their ratings coincide for at most <math>k</math> |
− | contestants. Prove that < | + | contestants. Prove that <math>\frac{k}{a}\ge\frac{b-1}{2b}</math>. |
==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 | ||
Line 18: | Line 17: | ||
\end{align*} | \end{align*} | ||
− | where the inequality follows from AM-QM. Since <math>b</math> is odd, <math>b^2 - 2b</math> is not divisible by <math>4</math> and we can | + | where the inequality follows from AM-QM. Since <math>b</math> is odd, <math>b^2 - 2b</math> is not divisible by <math>4</math> and we can strengthen the inequality to |
<cmath>{c_i \choose 2} + {{b - c_i} \choose 2} \geq \frac{b^2 - 2b + 1}{4} = \left(\frac{b - 1}{2}\right)^2.</cmath> | <cmath>{c_i \choose 2} + {{b - c_i} \choose 2} \geq \frac{b^2 - 2b + 1}{4} = \left(\frac{b - 1}{2}\right)^2.</cmath> | ||
− | + | Letting <math>N</math> stand for the number of instances where two judges agreed on a candidate, it follows that | |
− | <cmath> N = \sum_{i = 1}^ | + | <cmath> N = \sum_{i = 1}^a {c_i \choose 2} + {{b - c_i} \choose 2} \geq a \cdot \left( \frac{b - 1}{2} \right)^2. </cmath> |
The given condition on <math>k</math> implies that | The given condition on <math>k</math> implies that | ||
Line 36: | 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}} |
Latest revision as of 22:01, 4 July 2024
Problem
In a competition, there are contestants and
judges, where
is an odd
integer. Each judge rates each contestant as either “pass” or “fail”. Suppose
is a number such that, for any two judges, their ratings coincide for at most
contestants. Prove that
.
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 strengthen 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 |