Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 5035. feladat (2019. május)

B. 5035. Bizonyítsuk be, hogy ha az \(\displaystyle n\ge 8\) csúcsú teljes gráf éleit kiszínezzük két színnel, akkor több, mint \(\displaystyle \frac{{(n-5)}^4}{64}\) egyszínű, négy hosszú kör keletkezik.

Pálfy Máté (Budapest) javaslata nyomán

(6 pont)

A beküldési határidő 2019. június 11-én LEJÁRT.


Megoldás. Vegyük az \(\displaystyle n\) csúcsú teljes gráf éleinek egy tetszőleges színezését a piros és kék színekkel. Ha \(\displaystyle abcd\) egy piros (kék) kör, akkor erre úgy is gondolhatunk, hogy \(\displaystyle a\) és \(\displaystyle c\) csúcsokhoz tartozik két csúcs, \(\displaystyle b\) és \(\displaystyle d\), melyek mindegyike \(\displaystyle a\)-val és \(\displaystyle c\)-vel is piros (kék) színnel van összekötve. (Persze a szerepek szimmetrikusak: \(\displaystyle a\) és \(\displaystyle c\) szerepét \(\displaystyle b\) és \(\displaystyle d\) is játszhatja, ekkor \(\displaystyle b\) és \(\displaystyle d\) szerepét \(\displaystyle a\) és \(\displaystyle c\) veszi át.) Mindezek alapján érdemes a piros és kék cseresznyék számára alsó becslést adni. Egy cseresznye egy olyan három pontú gráf, ahol a három pont (mondjuk \(\displaystyle a,b,c\)) egyike (\(\displaystyle b\)) össze van kötve a másik kettővel (\(\displaystyle a,c\)), ekkor \(\displaystyle b\)-t nevezzük a cseresznye középső csúcsának, \(\displaystyle a\) és \(\displaystyle c\) pedig a szélső csúcsok. (Ha \(\displaystyle a,b,c\) egy háromszöget alkot, akkor ez a három csúcs összesen három cseresznyét határoz meg: bármelyik csúcs lehet középső.) A cseresznyét pirosnak (kéknek) mondjuk, ha \(\displaystyle ab,cb\) élek mindegyike piros (kék), ha a középső csúcs \(\displaystyle b\).

Megjegyezzük, hogy 4 hosszú körrel kapcsolatos problémáknál gyakran érdemes a cseresznyéket vizsgálni, ilyen gráfelméleti eredményekről és azok számelméleti alkalmazásairól a KöMaL 2004. decemberi számában megjelent Körök és multiplikatív Sidon-sorozatok (http://db.komal.hu/KomalHU/cikk.phtml?id=201729) c. cikkben írtunk.

Legyen \(\displaystyle b\) egy tetszőleges csúcs. Ha \(\displaystyle b\)-ből \(\displaystyle k\) piros és \(\displaystyle n-k-1\) kék indul ki, akkor összesen \(\displaystyle \binom{k}{2}+\binom{n-k-1}{2}\) olyan piros és kék cseresznye van, aminek \(\displaystyle b\) a középső csúcsa. Az \(\displaystyle \binom{x}{2}=\frac{x(x-1)}{2}\) a függvényt az egész valós számegyenesre kiterjesztve használjuk majd. Az előbbi képlet \(\displaystyle k\in \{0,1\}\) (illetve \(\displaystyle k\in \{n-2,n-1\}\)) mellett is helyes eredményt ad: ekkor a piros (illetve kék) cseresznyék száma 0.

Az \(\displaystyle \binom{x}{2}=\frac{x(x-1)}{2}\) függvény konvex (hiszen egy felfelé álló parabola), így a Jensen-egyenlőtlenség alapján kapjuk a következő alsó becslést az olyan egyszínű cseresznyék számára, melyek középső csúcsa \(\displaystyle b\):

\(\displaystyle \binom{k}{2}+\binom{n-k-1}{2}\geq 2\binom{\frac{n-1}{2}}{2}=\frac{(n-1)(n-3)}{4}.\)

Így a gráfban található piros és kék cseresznyék száma összesen legalább \(\displaystyle \frac{n(n-1)(n-3)}{4}\), hiszen a középső csúcs \(\displaystyle n\)-féle lehet.

Most visszatérve fenti megfigyelésünkre, tekintsük az egyszínű cseresznyék szélső pontpárjait. Ha \(\displaystyle a\) és \(\displaystyle c\) két különböző csúcs, és \(\displaystyle p\) (illetve \(\displaystyle k\)) az olyan piros (illetve kék) cseresznyék száma, melyek szélső pontjai \(\displaystyle a\) és \(\displaystyle c\), akkor az olyan piros (illetve kék) négy hosszú körök száma, melyek két szemköztes csúcsa \(\displaystyle a\) és \(\displaystyle c\) pontosan \(\displaystyle \binom{p}{2}\) (illetve \(\displaystyle \binom{k}{2}\)). Ezek alapján, ha az \(\displaystyle N:=\binom{n}{2}\) pontpárhoz (mint szélső csúcsokhoz) tartozó piros (illetve kék) cseresznyék száma \(\displaystyle p_1,p_2,\dots,p_N\) (illetve \(\displaystyle k_1,k_2,\dots,k_N\)), akkor a gráfban található egyszínű négy hosszú körök száma:

\(\displaystyle \frac{1}{2}\left(\sum\limits_{i=1}^N \binom{p_i}{2}+\sum\limits_{i=1}^N \binom{k_i}{2} \right),\)

hiszen minden négy hosszú kört kétszer számolunk: kétféleképpen választható ki benne a szemköztes pontpár.

Ismét a Jensen-egyenlőtlenséget használva:

\(\displaystyle \frac{1}{2}\left(\sum\limits_{i=1}^N \binom{p_i}{2}+\sum\limits_{i=1}^N \binom{k_i}{2} \right)\geq \frac{1}{2}\left(2N \binom{\frac{\sum p_i+\sum k_i}{2N}}{2} \right). \)\(\displaystyle {(*)}\)

Tudjuk, hogy a gráf egyszínű cseresznyéinek száma (ami éppen \(\displaystyle \sum\limits_{i=1}^N p_i+\sum\limits_{i=1}^N k_i\)) legalább \(\displaystyle \frac{n(n-1)(n-3)}{4}\), ezért

\(\displaystyle \frac{\sum p_i+\sum k_i}{2N}\geq \frac{\frac{n(n-1)(n-3)}{4}}{2N}=\frac{n-3}{4}.\)

Az \(\displaystyle \binom{x}{2}=\frac{x(x-1)}{2}\) függvény az \(\displaystyle [1/2,\infty)\) intervallumon szigorúan monoton növekedő, ezért \(\displaystyle n\geq 5\) esetén kapjuk, hogy

\(\displaystyle \binom{\frac{\sum p_i+\sum k_i}{2N}}{2}\geq\binom{\frac{n-3}{4}}{2}=\frac{(n-3)(n-7)}{32}.\)

Ezt \(\displaystyle (*)\)-gal egybevetve adódik, hogy a gráfban található egyszínű négy hosszú körök száma legalább

\(\displaystyle \frac{1}{2}\cdot 2N\cdot \frac{(n-3)(n-7)}{32}=\frac{n(n-1)(n-3)(n-7)}{64}.\)

Végül megmutatjuk, hogy \(\displaystyle n(n-1)(n-3)(n-7)\geq (n-5)^4\), ha \(\displaystyle n\geq 8\). Mivel \(\displaystyle n(n-7)=n^2-7n=(n-5)^2+(3n-25)\) és \(\displaystyle (n-1)(n-3)=n^2-4n+3=(n-5)^2+(6n-22)\), ezért \(\displaystyle n\geq 8\) esetén

$$\begin{multline*}n(n-1)(n-3)(n-7)=[(n-5)^2+(3n-25)][(n-5)^2+(6n-22)]\geq\\ \geq[(n-5)^2-1][(n-5)^2+26]= (n-5)^4+25(n-5)^2-26>(n-5)^4.\end{multline*}$$

Ezzel a feladat állítását igazoltuk.


Statisztika:

A B. 5035. feladat értékelése még nem fejeződött be.


A KöMaL 2019. májusi matematika feladatai