5. Zadatak

Prvo rješenje.

Neka je $m$ broj djevojčica, a $n$ broj dječaka na natjecanju. Potrebno je odrediti minimalnu vrijednost za $m+n$. Budući da nije potrebno zadovoljiti nikakve uvjete na međusobne partije djevojčica i međusobne partije dječaka, u rješenju promatramo samo partije između djevojčica i dječaka.

Među njima je odigrano $mn$ partija (svaki dječak sa svakom djevojčicom). Broj partija u kojima su pobijedile djevojčice, iz uvjeta zadatka, veći ili jednak je od $21m$, dok je broj partija u kojima su pobijedili dječaci barem $12n$. Iz toga zaključujemo da je

$$mn\geq21m+12n.$$

Tu nejednakost možemo zapisati kao $(m-12)(n-21)\geq252$.

Primjenom nejednakosti između aritmetičke i geometrijske sredine dobivamo da je

$$(m-12)+(n-21)\geq2\sqrt{(m-12)(n-21)}\geq2\sqrt{252}>\sqrt{961}=31,$$

pa je $m+n>64$. Iz toga zaključujemo da je $m+n\geq65$.

Preostaje pokazati da je moguće da je na turniru bilo $m+n=65$ natjecatelja. Konstruirat ćemo primjer za slučaj $m=30$ i $n=35$.

Podijelimo djevojčice u šest skupina (nazovimo ih $X_1,\ldots,X_6$), a dječake u sedam skupina (nazovimo ih $Y_1,\ldots,Y_7$) po $5$ osoba.

Za svaki par skupina $X_i$ i $Y_j$ neka je djevojčica koja je na mjestu $k$ u grupi $X_i$ pobijedila dječake koji su na mjestima $k$, $k+1$ i $k+2$ u grupi $Y_j$, pri čemu mjesta promatramo ciklički (šesto mjesto je prvo, sedmo je drugo, osmo je treće).

Tada je svaka djevojčica pobijedila $7\cdot3=21$ dječaka, te je svaki dječak pobijedio $6\cdot2=12$ djevojčica.

Napomena: Iz nejednakosti $(m-12)(n-21)\geq252$ ne možemo direktno zaključiti da će $m+n$ biti najmanje kad vrijedi jednakost. Naime, $ab<cd$ ne povlači $a+b<c+d$ za cijele brojeve, kao što pokazuje primjer: $76=4\cdot19<77=7\cdot11$, iako je $4+19>7+11$. Zbog toga moramo koristiti neki oblik nejednakosti između aritmetičke i geometrijske sredine ili razmišljanja kao u drugom rješenju.

Napomena: Primjer iz rješenja možemo opisati i na drugačiji način. Podijelimo djevojčice u pet skupina od po njih $6$ (nazovimo ih $A_1$, $A_2$, $A_3$, $A_4$, $A_5$), a dječake u $5$ skupina od po njih $7$ (nazovimo ih $B_1$, $B_2$, $B_3$, $B_4$, $B_5$). Imamo $5$ skupina djevojčica i $5$ skupina dječaka.

Neka su svi dječaci iz skupine $B_i$ pobijedili djevojčice iz skupine $A_i$ i $A_{i+1}$, za $1\leq i\leq4$, te $B_5$ su pobijedili djevojčice iz $A_5$ i $A_1$. Od svih ostalih djevojčica su izgubili.

To znači da je svaki dječak pobijedio djevojčice iz točno dvije skupine djevojčica, dakle u točno $2\cdot6=12$ partija. Svaka djevojčica je pobijedila sve dječake iz točno tri njihove skupine, dakle u točno $3\cdot7=21$ partija.

Drugo rješenje.

Uz oznake kao u prvom rješenju opet dolazimo do nejednakosti $mn\geq21m+12n$.

Neka je $S=m+n$, tada je

$$(S-n)n\geq21(S-n)+12n, \qquad\text{odnosno}\qquad S\geq\frac{n^2-9n}{n-21}.$$

Neka je $a_k=\frac{k^2-9k}{k-21}$, gdje je $k\geq22$ prirodan broj, računamo

$$a_{k+1}-a_k=\frac{k^2-41k+168}{(k-21)(k-20)},$$

stoga je $a_{k+1}>a_k$ ako i samo ako je $k^2-41k+168>0$, a to vrijedi ako i samo ako je $k\geq37$. Dakle, vrijedi $a_{22}>a_{23}>\cdots>a_{37}<a_{38}<a_{39}<\cdots$.

Budući da je je $a_{37}=\frac{259}{4}=64.75$, zaključujemo da je $S\geq65$.

Kao u prvom rješenju konstruiramo primjer za $S=65$.

Napomena: Konstruirat ćemo primjer za $m=26$ i $n=39$. Podijelimo djevojčice na $13$ skupina po $2$ djevojčice ($A_1,\ldots,A_{13}$) te dječake na $13$ skupina po $3$ dječaka ($B_1,\ldots,B_{13}$).

Neka su svi dječaci iz skupine $B_i$, za $1\leq i\leq13$, pobijedili sve djevojčice iz skupina $A_i,A_{i+1},\ldots,A_{i+5}$ (koristimo notaciju $A_{i+13}=A_i$), a izgubili od ostalih djevojčica.

Svaki dječak pobijedio je točno $6\cdot2=12$ djevojčica, te je svaka djevojčica pobijedila točno $7\cdot3=21$ dječaka.

Napomena: Konstruirat ćemo primjer za $m=28$ i $n=37$.

Podijelimo $28$ djevojčica u $7$ skupina po $4$ djevojčice.

Postoji ukupno $\binom73=35$ različitih odabira $3$ od tih $7$ skupina i pri tome svaka od tih skupina sudjeluje u točno $\binom62=15$ odabira. Svaki od tako dobivenih odabira pridružimo točno jednom dječaku. Neka je svaki od tih dječaka pobijedio sve djevojčice iz odabira koji mu je pridružen, a izgubio od svih ostalih. Time je svaki od tih $35$ dječaka pobijedio točno $12$ djevojčica, dok je svaka od tih djevojčica izgubila najviše $15$ partija.

Za preostala $2$ dječaka odaberimo dva disjunktna odabira po $3$ skupine (što možemo jer postoji $7$ skupina) i na isti način svakom od tih dječaka pridružimo po jedan odabir. Ovime su i preostala dva dječaka pobijedila točno $12$ djevojčica, dok sve djevojčice imaju najviše $16$ izgubljenih partija. Dakle, svaka djevojčica je pobijedila u barem $37-16=21$ partiji.