Kezdőlap


Feladat:	Gy.2385	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	1987/november, 389 - 390. oldal		PDF \| MathML
Témakör(ök):	Indirekt bizonyítási mód, Kombinatorika, Gyakorlat
Hivatkozás(ok):	Feladatok: 1987/január: Gy.2385

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Legyen $A$ és $B$ a két ország, és tegyük fel, hogy az $A$ -beli versenyzők együttesen kevesebb (nem több) pontot szereztek, mint a $B$ -beliek. Jelölje az $A$ ország $n$ darab versenyzőjének a saját honfitársaitól és a $B$ -beli versenyzőktől szerzett pontszámait rendre $a_{1}$ , $a_{2}$ , $...$ , $a_{n}$ , illetve $b_{1}$ , $b_{2}$ , $...$ , $b_{n}$ . Az $A$ kiválasztása szerint az $A$ -beli versenyzők az összesen $n^{2}$ "nemzetközi'' mérkőzésen a megszerezhető pontoknak legfeljebb a felét érték el, azaz

\begin{matrix} b_{1} + b_{2} + ... + b_{n} ≦ \frac{n^{2}}{2} . \end{matrix}

(1)

Másfelől az

n

darab

A

-beli versenyző között

(\binom{n}{2})

mérkőzés zajlott le, így

\begin{matrix} a_{1} + a_{2} + ... + a_{n} = \frac{n (n - 1)}{2} . \end{matrix}

Nyilván készen vagyunk, ha valamelyik

A

-beli versenyzőre teljesül a feladat állítása, azaz van olyan

i

, amelyre

a_{i} ≧ b_{i}

. Tegyük fel, hogy ez nem igaz, vagyis minden

i

-re

a_{i} < b_{i}

. Ekkor

a_{i} + 0, 5 ≦ b_{i}

is fennáll, és ezt összegezve

\begin{matrix} \sum_{i = 1}^{n} b_{i} ≧ \sum_{i = 1}^{n} (a_{i} + 0, 5) = \frac{n (n - 1)}{2} + \frac{n}{2} = \frac{n^{2}}{2} \end{matrix}

(2)

adódik.

Ezt (1)-gyel összevetve látható, hogy

\sum_{i = 1}^{n} b_{i} = \frac{n^{2}}{2}

, a két ország versenyzőinek együttes pontszáma tehát egyenlő, továbbá ekkor természetesen (2)-ben is egyenlőség van, azaz

b_{i} = a_{i} + 0, 5

minden

i

-re. Az

A

ország versenyzői tehát rendre

a_{i} + b_{i} = 2 a_{i} + 0, 5

pontot szereztek a versenyen. Ez nem egész szám, hisz maga

a_{i}

egész, vagy egész szám fele.
Azt kaptuk, hogy ha az

A

ország egyetlen versenyzőjére sem teljesül a feladat állítása, akkor egyetlen

A

-beli versenyző pontszáma sem lehet egész, másfelől ekkor a két ország sakkozói együttesen ugyanannyi pontot szereztek a tornán. Ez utóbbi azt jelenti, hogy a

B

-beli versenyzőkre megismételhető a fenti gondolatmenet, tehát ha köztük sincs megfelelő, akkor egyikük sem szerezhetett egész számú pontot.
Ez viszont csak úgy lehetséges, ha az összesen

2 n

darab versenyző rendre

\frac{1}{2}

\frac{3}{2}

...

(2 n - 1) + \frac{1}{2}

pontot szerzett, hiszen a feltétel szerint a verseny végén nem volt két azonos pontszámú sakkozó. Ezek összege

\begin{matrix} \frac{1}{2} \cdot 2 n + 1 + 2 + ... + (2 n - 1) = n + \frac{(2 n - 1) \cdot 2 n}{2} = 2 n^{2} . \end{matrix}

Másfelől a bajnokságon összesen

\frac{2 n (2 n - 1)}{2} = 2 n^{2} - n

játszmára került sor, így a megszerzett pontok összege is ennyi kell legyen.
Valamelyik feltevésünk tehát ellentmondásra vezetett, azaz nem lehetséges, hogy egyik ország versenyzői közt se legyen olyan, akire a feladat állítása nem teljesül. Ezzel a bizonyítást befejeztük.

Megjegyzés. Nyilván létezik olyan bajnokság, melynek kimenetele a feltétel szerint alakul, hiszen ha a

2 n

versenyzőt sorba állítva, mindenki legyőzi azokat, akik mögötte állnak a sorban, akkor semelyik két versenyző pontszáma nem egyenlő.