Difference between revisions of "1998 IMO Problems/Problem 2"
(Created page with "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 nu...") |
m (latex) |
||
(8 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | In a competition, there are a contestants and b judges, where b | + | ==Problem== |
− | 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 | + | In a competition, there are <math>a</math> contestants and <math>b</math> judges, where <math>b\ge3</math> is an odd |
− | contestants. Prove that k/a | + | 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 <math>k</math> | ||
+ | contestants. Prove that <math>\frac{k}{a}\ge\frac{b-1}{2b}</math>. | ||
+ | |||
+ | ==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 | ||
+ | |||
+ | \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 <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> | ||
+ | |||
+ | 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}^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 | ||
+ | |||
+ | <cmath> N \leq k \cdot {b \choose 2} = \frac{kb(b - 1)}{2}. </cmath> | ||
+ | |||
+ | Therefore | ||
+ | |||
+ | <cmath> a \cdot \left( \frac{b - 1}{2} \right)^2 \leq \frac{kb(b - 1)}{2}, </cmath> | ||
+ | |||
+ | which simplifies to | ||
+ | |||
+ | <cmath> \frac{k}{a} \geq \frac{b - 1}{2b}. </cmath> | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=1998|num-b=1|num-a=3}} |
Latest revision as of 21: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
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 |