combinatoriek 5

Opgave - IMO 1998 dag 1 vraag 2

In een wedstrijd zijn er $m$ deelnemers en $n$ juryleden, met $n\geq3$ een oneven natuurlijk getal. Iedere kandidaat wordt door ieder jurylid beoordeeld als geslaagd of gebuisd. Veronderstel dat ieder koppel juryleden akkoord gaat met elkaar over maximum $k$ kandidaten. Bewijs dat
$$\frac km\geq\frac{n-1}{2n}.$$

Oplossing

Zij $M=\{d_1,\dots, d_m\}$ de verzameling deelnemers, $N=\{j_1,j_2,\dots j_n\}$ de verzameling juryleden. $g(d)$ is het aantal juryleden die een deelnemer $d\in M$ slagen.

We tellen op twee manieren het aantal elementen van de verzameling
$$T=\{(d,j_x,j_y)\in M\times N^2, x < y | j_x \text{ en }j_y \text{ gaan akkoord met deelnemer } d\}$$

Enerzijds is $|T|\leq k{n \choose 2}$, want voor elk koppel juryleden (hiervoor zijn ${n \choose 2}$ mogelijkheden), zijn er maximum $k$ deelnemers waarvoor beide juryleden overeen komen.

Aan de andere kant is $|T|=\sum_{d\in N}{g(d) \choose 2}+{n-g(d) \choose 2}$, want als we een willekeurige deelnemer kiezen dan kunnen we uit de $g(d)$ juryleden die hem slaagde en de $n-g(d)$ juryleden die hem buisde er telkens 2 kiezen. Sommeer dus over $d$ en je bekomt alle elementen van $T$.

Dus $$|T|=\frac12\sum_{d\in M}g(d)^2-g(d)+(n-g(d))^2-(n-g(d))$$
$$=m\frac{n(n-1)}{2}-\sum_{d\in M}g(d)(n-g(d))$$
$$\geq m\frac{n(n-1)}{2}-\sum_{d\in M}\frac{n-1}{2}\cdot\frac{n+1}{2}=m\frac{n(n-1)}{2}-m\frac{n^2-1}{4}=m\frac{(n-1)^2}{4}$$
(waarbij we gebruik maakten dat voor $x+y=z$ met $z$ oneven, allen natuurlijk, het product $xy$ gemaximaliseerd wordt als $\{x,y\}=\{\frac{z-1}{2},\frac{z+1}{2}\}$)

Er volgt dat $k\frac{n(n-1)}{2}\ge|T|\ge m\frac{(n-1)^2}{4}$ waaruit het gevraagde volgt.
QED.