Uluslararası Matematik Olimpiyatı 1998 Soru 2

[geo]

Bir yarışmada, $b \geq 3$ bir tek sayı olmak üzere, $a$ yarışmacı ve $b$ hakem bulunmaktadır. Her hakem her yarışmacıyı ya "başarılı" ya da "başarısız" olarak değerlendiriyor. $k$ aşağıdaki özelliğe sahip bir sayı olsun: Herhangi iki hakemin en çok $k$ yarışmacı hakkındaki değerlendirmeleri çakışmaktadır. $$\dfrac ka \geq \dfrac {b-1}{2b}$$ olduğunu gösteriniz.

[geo]

Tüm çakışan karar ikililerinin sayısı $N$ olsun.
$N \leq \dbinom b2 \cdot k$.

$a\times b$ bir matriste satırlar yarışmacıları, sütunlar da hakemleri ifade etsin.

$i.$ yarışmacıyı başarılı bulan hakemlerin sayısı $c_i$ olsun. $b-c_i$ tanesi de başarısız bulmuştur.
$i$. yarışmacı için çakışan kararların sayısı:
$\begin{array}{lcl}
\dbinom {c_i}2 + \dbinom {b-c_i}2 &=& \dfrac {c_i^2 - c_i}2 + \dfrac {(b-c_i)^2 - (b-c_i)}{2} \\
&=& \dfrac {b^2 - b + 2c_i^2 - 2bc_i}{2} \\
&=& \dfrac {b^2 - b + 2c_i^2 - 2bc_i}{2} \\
&=& \dfrac {b^2 - b}{2} - c_i(b-c_i) \\
&\geq & \dfrac {b^2 - b}{2} - \dfrac {b-1}{2} \cdot \dfrac {b+1}2 \\
&=& \dfrac {b-1}2\left ( b - \dfrac {b+1}2 \right ) \\
&=& \dfrac {(b-1)^2}4
\end{array}$

Toplam $a$ tane yarışması olduğu için tüm yarışmacılar için çakışan tüm kararların sayısına $N \geq a\cdot \dfrac {(b-1)^2}4$.

$\dbinom b2 \cdot k \geq N \geq a\cdot \dfrac {(b-1)^2}4$

$\dfrac ka \geq \dfrac {\dfrac {(b-1)^2}{4}}{\dfrac {b(b-1)}{2}} = \dfrac {b-1}{2b}$.