Kezdőlap


Feladat:	F.3234	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Harangi Viktor , Horváth Gábor , Juhász András , Lippner Gábor , Pogány Ádám , Poronyi Gábor , Székelyhidi Gábor , Terpai Tamás , Végh A. László , Zombori Tamás
Füzet:	1999/április, 227 - 229. oldal		PDF \| MathML
Témakör(ök):	Kombinatorika, Számtani közép, Kvadratikus közép, Feladat
Hivatkozás(ok):	Feladatok: 1998/május: F.3234

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.

Oldjuk meg általánosabban a feladatot, 23 helyett $n$ csapatra, ahol $n$ páratlan szám. Jelöljünk minden csapatot egy-egy ponttal. Két csapat mérkőzése után mutasson nyíl a vesztes csapattól a győztesig. (Ekkor egy $n$ szögpontú irányított teljes gráfot kapunk, mivel a feladat szempontjából feltehető, hogy sohasem született döntetlen eredmény.)
Ha az $A$ , $B$ és $C$ csapatok körbeverték egymást, ‐ ez kétféleképpen lehetséges ‐, akkor az $A B C$ háromszöget irányítottnak nevezzük. Egyébként a háromszög nem irányított.
Adjunk becslést a nem irányított háromszögek számára.
Minden nem irányított háromszögben van pontosan egy csúcs úgy, hogy az ezzel ábrázolt csapat a másik kettőt megverte. A nem irányított háromszögeket eszerint a ,,győztes'' csúcs szerint számoljuk össze.
Jelöljük a csapatokat az $A_{1}$ , $A_{2}$ , $...$ , $A_{n}$ pontokkal, és jelölje az $A_{i}$ győzelmeinek számát $d_{i}$ . Mivel a körmérkőzés során összesen $(\binom{n}{2})$ találkozó volt, $\sum_{i = 1}^{n} d_{i} = \frac{n (n - 1)}{2}$ . Ekkor az $A_{i}$ csúcshoz $(\binom{d_{i}}{2})$ nem irányított háromszög tartozik, hiszen az általa legyőzött csapatokból kell kiválasztani kettőt.
Így az összes nem irányított háromszögek száma: $\sum_{i = 1}^{n} (\binom{d_{i}}{2})$ .
A számtani és a négyzetes közép közötti egyenlőtlenség szerint:

\begin{matrix} \begin{matrix} \sum_{i = 1}^{n} (\binom{d_{i}}{2}) = \frac{1}{2} \sum_{i = 1}^{n} d_{i}^{2} - \frac{1}{2} \sum_{i = 1}^{n} d_{i} = \frac{1}{2} n \frac{\sum_{i = 1}^{n} d_{i}^{2}}{n} - \frac{1}{2} \sum_{i = 1}^{n} d_{i} \geq \frac{1}{2} n {(\frac{\sum_{i = 1}^{n} d_{i}}{n})}^{2} - \frac{1}{2} \sum_{i = 1}^{n} d_{i} = \\ = \frac{1}{2} n {(\frac{n - 1}{2})}^{2} - \frac{1}{2} \frac{n (n - 1)}{2} = \frac{n^{3} - 4 n^{2} + 3 n}{8} . \end{matrix} \end{matrix}

Állhat-e itt egyenlőség? Igen, ha meg tudunk adni olyan irányított teljes gráfot, amelyre

\begin{matrix} d_{1} = d_{2} = ... = d_{n} = \frac{n - 1}{2} . \end{matrix}

Legyen

n = 2 k + 1

. Ekkor egy lehetséges konstrukció a következő:
ha

1 \leq i < j \leq 2 k + 1

és

j - i

nagyobb, mint

k

, akkor

A_{j}

győzte le

A_{i}

-t, különben pedig

A_{i}

győzte le

A_{j}

-t. Könnyen ellenőrizhető, hogy ekkor valóban

\begin{matrix} d_{1} = d_{2} = ... = d_{n} = \frac{n - 1}{2} . \end{matrix}

Mivel összesen

(\binom{n}{3})

háromszög van, azért az irányított háromszögek száma esetünkben

\begin{matrix} (\binom{n}{3}) - \frac{n^{3} - 4 n^{2} + 3 n}{8} = \frac{n (n - 1) (n - 2)}{6} - \frac{n^{3} - 4 n^{2} + 3 n}{8} = \frac{n^{3} - n}{24} . \end{matrix}

n = 23

esetén ez 506, tehát legfeljebb 506 körbeverés történhetett a bajnokság során.

Juhász András (Fazekas M. Főv. Gyak. Gimn., 10. o.t.) dolgozata alapján