Kezdőlap


Feladat:	B.5035	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Füredi Erik Benjámin , Hegedűs Dániel , Várkonyi Zsombor , Weisz Máté
Füzet:	2019/december, 540 - 542. oldal		PDF \| MathML
Témakör(ök):	Feladat, Gráfelmélet, Egyéb szinezési problémák
Hivatkozás(ok):	Feladatok: 2019/május: B.5035

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.

Elnevezés: Az $(\binom{n}{k})$ kifejezésben $n$ -re olykor számlálóként, $k$ -ra pedig nevezőként hivatkozunk. Szükségünk lesz a következő becslésre: Legyenek $a$ , $b$ , $y$ pozitív egész számok, melyekre $a > b$ ; ekkor: $(\binom{a}{y}) + (\binom{b}{y}) \geq (\binom{a - 1}{y}) + (\binom{b + 1}{y})$ .
Bizonyítás: ekvivalens átalakításokat hajtunk végre a bizonyítandó egyenlőtlenségen. Szorozzuk mindkét oldalt $(y!)$ -sal:

\begin{matrix} a (a - 1) (a - 2) ... (a - y + 1) + b (b - 1) (b - 2) ... (b - y + 1) \geq \\ \geq (a - 1) (a - 2) (a - 3) ... (a - y) + (b + 1) b (b - 1) ... (b - y + 2) . \end{matrix}

Vonjuk ki a jobb oldalt és emeljünk ki:

\begin{matrix} (a - (a - y)) (a - 1) (a - 2) ... (a - y + 1) + \\ + ((b - y + 1) - (b + 1)) b (b - 1) ... (b - y + 2) \geq 0. \end{matrix}

Végezzük el a kivonást és adjuk hozzá a negatív tagot:

\begin{matrix} y (a - 1) (a - 2) ... (a - y + 1) \geq y b (b - 1) ... (b - y + 2) . \end{matrix}

Ez pedig egyenesen következik abból, hogy

a > b

, mert mindkét oldalon

y

pozitív szám szorzata áll, és a bal oldalon lévők páronként nagyobbak vagy egyenlők, mint a jobb oldalon lévők. Ezzel a lemmával a későbbiekben olyan összegeket tudunk alulról becsülni, ahol a binomiális tagok ,,számlálójában'' lévő tagok összege adott. Fontos megjegyezni, hogy amit beláttunk

1

-re (amennyivel ,,közelebb vittük egymáshoz'' a két számlálót), az tetszőleges pozitív valós számra igaz, ez látszik a bizonyítás menetéből. Tehát valójában a számlálók átlagával tudunk alulról becsülni, és ez akárhány tagra igaz.

A feladat állításának bizonyítása: Vegyünk egy tetszőleges

n

pontú teljes gráfot. Legyen az élek színe kék és lila, és tegyük fel, hogy kékből van több vagy ugyanannyi, mint lilából. Legyen a kék élek száma

\frac{n k}{2}

(itt

k

nem feltétlenül egész szám, de ez nem baj, és már most tudjuk, hogy

k \leq \frac{n - 1}{2}

), az a lényeg, hogy egy csúcsból átlagosan

k

darab kék él indul ki. Ha egy csúcsból kiindul

x

kék él, akkor az a csúcs

(\binom{x}{2})

kék cseresznyének a gyökere (egy cseresznye egy kettő hosszú út, és gyökere az élek közös végpontja). Legyen a gráf

i

-edik csúcsából kiinduló kék élek száma

A_{i}

. Ekkor a gráfban van

(\binom{A_{1}}{2}) + (\binom{A_{2}}{2}) + ... + (\binom{A_{n}}{2})

kék cseresznye, ahol

A_{1} + A_{2} + ... A_{n} = n k

. Most alkalmazzuk a lemmát az

y = 2

esetre, és megkapjuk, hogy van a gráfban legalább

n (\binom{k}{2})

kék cseresznye, hiszen mind az

n

számlálóba behelyettesítettük

k

-t, a számlálók átlagát. Ezt osszuk el az élek számával, és megkapjuk, hogy egy élen átlagosan

\begin{matrix} \frac{2 (\binom{k}{2})}{n - 1} \end{matrix}

cseresznye fekszik (egy cseresznye azon az élen fekszik, ami hiányzik a három pont által meghatározott háromszögből). Persze lehetséges, hogy néhány élen több, néhányon pedig kevesebb cseresznye fekszik, azonban a következő lépésből és a lemmából látni fogjuk, hogy akkor kapunk alsó becslést, ha az átlaggal számolunk. Szintén a lemmát alkalmazva kapjuk, hogy

\begin{matrix} (\binom{\frac{2 (\binom{k}{2})}{n - 1}}{2}) \end{matrix}

4 hosszú kék kör fekszik átlagosan egy élen mint a 4 hosszú kör ,,átlóján''. Ezt az élek számával beszorozva megkapjuk a 4 hosszú kék körök számát. Azonban így minden 4 hosszú kék kört kétszer számoltunk (mindkét átlójánál), ezért ezt el kell osztani 2-vel. Ebből azt kapjuk, hogy legalább

\begin{matrix} (\binom{\frac{2 (\binom{k}{2})}{n - 1}}{2}) \cdot (\binom{n}{2}) \cdot \frac{1}{2} \end{matrix}

4 hosszú kék kör van a gráfban. Teljesen megegyező gondolatmenettel kaphatjuk, hogy lila körből legalább

\begin{matrix} (\binom{\frac{2 (\binom{n - 1 - k}{2})}{n - 1}}{2}) \cdot (\binom{n}{2}) \cdot \frac{1}{2} \end{matrix}

darab van, hiszen az egy csúcsból kiinduló lila élek átlagos száma

n - 1 - k

. Konstans szorzótól eltekintve ezek is fix összegű számlálók azonos nevezőjű binomiális kifejezéseinek összegei, tehát alulról becsülhetjük az átlaggal:

k

és

n - 1 - k

átlaga éppen

\frac{n - 1}{2}

, ezt behelyettesítve becsülhetjük a 4 hosszú körök számát:

\begin{matrix} 2 \cdot (\binom{\frac{2 (\binom{\frac{n - 1}{2}}{2})}{n - 1}}{2}) \cdot (\binom{n}{2}) \cdot \frac{1}{2} . \end{matrix}

Ezt ekvivalens átalakítások sorozatával szebb alakra hozhatjuk:

\begin{matrix} \frac{n (n - 1) (n - 3) (n - 7)}{64} . \end{matrix}

n \geq 9

esetén nagyobb a bizonyítandónál, hiszen

n (n - 7) > {(n - 5)}^{2}

és

(n - 1) > (n - 5)

, valamint

(n - 3) > (n - 5)

mind teljesül

n \geq 9

-re. Ha

n = 8

, akkor pedig

8 \cdot 7 \cdot 5 \cdot 1 > 64

. Ezzel a bizonyítandót beláttuk.

Várkonyi Zsombor (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 10. évf.)