Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1998 IMO Problems/Problem 2"
(→‎Solution)
Line 8: Line 8:
 
==Solution==
 
==Solution==
 
{{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
 +
 +
\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 improve 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>
 +
 +
Let <math>N</math> stand for the number of instances where two judges agreed on a candidate. Since there are <math>a</math> candidates, it follows that
 +
 +
<cmath> N = \sum_{i = 1}^n {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 {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 13:52, 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

This problem needs a solution. If you have a solution for it, please help us out by adding it.

Let $c_i$ stand for the number of judges who pass the $i$th candidate. The number of pairs of judges who agree on the $i$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 $b$ is odd, $b^2 - 2b$ is not divisible by $4$ and we can improve 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.\]

Let $N$ stand for the number of instances where two judges agreed on a candidate. Since there are $a$ candidates, it follows that

\[N = \sum_{i = 1}^n {c_i \choose 2} + {{b - c_i} \choose 2} \geq a \cdot \left( \frac{b - 1}{2} \right)^2.\]

The given condition on $k$ implies that

\[N \leq k \cdot {b \choose 2} = \frac{kb(b - 1)}{2}.\]

Therefore

\[a \cdot \left( \frac{b - 1}{2} \right)^2 \leq \frac{kb(b - 1)}{2},\]

which simplifies to

\[\frac{k}{a} \geq {b - 1}{2b}.\]

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1998_IMO_Problems/Problem_2&oldid=219898"