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...") |
(→Solution) |
||
| (7 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| − | In a competition, there are a contestants and b judges, where b ≥ 3 is an odd | + | ==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 <i>a</i> contestants and <i>b</i> judges, where <i>b</i> ≥ 3 is an odd |
| − | contestants. Prove that k/a ≥ (b − 1)/(2b) | + | integer. Each judge rates each contestant as either “pass” or “fail”. Suppose <i>k</i> |
| + | is a number such that, for any two judges, their ratings coincide for at most <i>k</i> | ||
| + | contestants. Prove that <i>k</i>/<i>a</i> ≥ (<i>b</i> − 1)/(2<i>b</i>). | ||
| + | |||
| + | ==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 15:28, 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 strengthen the inequality to
![\[{c_i \choose 2} + {{b - c_i} \choose 2} \geq \frac{b^2 - 2b + 1}{4} = \left(\frac{b - 1}{2}\right)^2.\]](http://latex.artofproblemsolving.com/b/1/7/b171b18ac10a2c0f0a7bbd1eabf1410edeba864b.png)
Letting 
stand for the number of instances where two judges agreed on a candidate, it follows that
![\[N = \sum_{i = 1}^a {c_i \choose 2} + {{b - c_i} \choose 2} \geq a \cdot \left( \frac{b - 1}{2} \right)^2.\]](http://latex.artofproblemsolving.com/d/d/2/dd2364f4214f7010c2137216e277e6e54722e63e.png)
The given condition on 
implies that
![\[N \leq k \cdot {b \choose 2} = \frac{kb(b - 1)}{2}.\]](http://latex.artofproblemsolving.com/d/8/2/d822e4cde94139c63856f9ca61185a3157b3afb3.png)
Therefore
![\[a \cdot \left( \frac{b - 1}{2} \right)^2 \leq \frac{kb(b - 1)}{2},\]](http://latex.artofproblemsolving.com/c/6/6/c66c6465bc61dc52b9e264ec903870f9bd984f66.png)
which simplifies to
![\[\frac{k}{a} \geq \frac{b - 1}{2b}.\]](http://latex.artofproblemsolving.com/b/3/1/b3122f2a058fc60b564edde0125e319f117b2450.png)
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 | ||
