A B. 5509. feladat (2026. január)

B. 5509. Egy $\displaystyle n$ csúcsú gráf csúcshalmaza legyen: $\displaystyle V=\{ v_1,v_2,\ldots,v_n \}$, a $\displaystyle v_i$ csúcs fokszáma $\displaystyle d_i$. Egy a gráf csúcsaihoz nemnegatív valós számokat rendelő $\displaystyle f$ függvényt verőceinek nevezünk, ha a gráf minden $\displaystyle v_iv_j$ élére teljesül, hogy

$\displaystyle f(v_i)+f(v_j) \geq {d_i+d_j}. $

Határozzuk meg azt a legnagyobb $\displaystyle \lambda$ valós számot, amelyre minden $\displaystyle n$-re, minden $\displaystyle n$ csúcsú egyszerű gráfra és minden $\displaystyle f$ verőcei függvényre teljesül, hogy

$\displaystyle f(v_1)+f(v_2)+\ldots+f(v_n) \geq \lambda (d_1+d_2+\ldots+d_n). $

Javasolta: Varga Boldizsár (Verőce)

(6 pont)

A beküldési határidő 2026. február 10-én LEJÁRT.

1. megoldás. Ha $\displaystyle n\ge2$, és a gráf egy csillaggráf, azaz például a $\displaystyle v_1$ csúcs – ez lesz csillag közepe – össze van kötve az összes többi csúccsal, azok között pedig nincs további él, akkor a fokszámok $\displaystyle d_1=n-1$ és $\displaystyle d_2=d_3=\ldots=d_n=1$, ezek összege $\displaystyle d_1+\ldots+d_n=2(n-1)$. Az $\displaystyle f(v_1)=n$, $\displaystyle f(v_2)=f(v_3)=\ldots=f(v_n)=0$ függvény eleget tesz a feltételnek, és $\displaystyle f(v_1)+\dots+f(v_n)=n$, tehát ebben az esetben

$\displaystyle f(v_1) + f(v_2) + \ldots + f(v_n) = \dfrac{n}{2n-2} (d_1 + d_2 + \ldots + d_n). $

$\displaystyle (1) $

Ez a példa mutatja, hogy

$\displaystyle \lambda\le\dfrac{n}{2n-2}=\dfrac12+\frac{1}{2(n-1)}. $

Az $\displaystyle n\to\infty$ határátmenetből azt kapjuk, hogy $\displaystyle \lambda\le\dfrac12$.

Megmutatjuk, hogy a $\displaystyle \lambda=\dfrac12$ számra igaz a feltétel: tetszőleges $\displaystyle n$ csúcsú egyszerű gráf és verőcei függvény esetén

$\displaystyle f(v_1) + f(v_2) + \ldots + f(v_n) \ge \dfrac12(d_1 + d_2 + \ldots + d_n). $

$\displaystyle (2) $

Legyen a gráf éleinek (a megfelelő $\displaystyle \{i,j\}$ indexpárok) halmaza $\displaystyle E$; vegyük észre, hogy a jobb oldalon éppen gráf éleinek száma áll: $\displaystyle \dfrac12(d_1 + d_2 + \ldots + d_n)=|E|$.

Színezzük pirosra azokat a $\displaystyle v_i$ csúcsokat, amelyekre $\displaystyle f(v_i)\ge d_i$. Vegyük észre, hogy bármely két szomszédos $\displaystyle v_i$ és $\displaystyle v_j$ csúcs közül legalább az egyik piros, mert a feltétel szerint $\displaystyle f(v_i)+f(v_j)\ge d_i+d_j$, és emiatt $\displaystyle f(v_i)\ge d_i$ és $\displaystyle f(v_j)\ge d_j$ közül legalább az egyik teljesül.

Minden piros csúcsra jelöljük meg a belőle kiinduló éleket (egy élt akár mindkét végénél is megjelölhetünk), ezzel minden élt legalább egyszer megjelölünk. Másrészt minden piros $\displaystyle v_i$ csúcsnál legfeljebb $\displaystyle d_i$ élt jelölünk meg, ezért

$\displaystyle \sum_{i=1}^n f(v_i) \ge \sum_{\text{\(\displaystyle v_i$ piros}} f(v_i) \ge \sum_{\text{$\displaystyle v_i$ piros}} d_i \ge |E| = \dfrac12\sum_{i=1}^n d_i. \)

Ezzel megmutattuk, hogy $\displaystyle \lambda=\dfrac12$ a legnagyobb szám amely minden egyszerű gráf és verőcei függvény esetén teljesíti a feltételt.

2. megoldás. Az 1. megoldáshoz hasonlóan látjuk, hogy $\displaystyle n\ge$ esetén $\displaystyle \lambda\le\dfrac{n}{2(n-1)}$.

Megmutatjuk, hogy tetszőleges $\displaystyle n\ge2$ csúcsú egyszerű gráf és verőcei $\displaystyle f$ függvény esetén

$\displaystyle \sum_{i=1}^n f(v_i) \ge \dfrac{n}{2(n-1)}\sum_{i=1}^n d_i. $

A becslést úgy kapjuk, hogy a gráf összes élére összeadjuk az $\displaystyle \dfrac{f(v_i)+f(v_j)}{d_i+d_j}\ge1$ egyenlőtlenséget. Az éleket mindkét irányban számolva,

$$\begin{gather*} \sum_{i=1}^n d_i =2|E| =\sum_{\substack{1\le i,j\le n\\\{i,j\}\in E}}1 \le\sum_{\substack{1\le i,j\le n\\\{i,j\}\in E}}\dfrac{f(v_i)+f(v_j)}{d_i+d_j} =\sum_{\substack{1\le i,j\le n\\\{i,j\}\in E}}\dfrac{f(v_i)}{d_i+d_j}+\sum_{\substack{1\le i,j\le n\\\{i,j\}\in E}}\dfrac{f(v_j)}{d_i+d_j} =\\ =2\sum_{i=1}^n \left(\sum_{\substack{1\le j\le n\\\{i,j\}\in E}} \dfrac{f(v_i)}{d_i+d_j}\right) =2\sum_{i=1}^n f(v_i)\left(\sum_{\substack{1\le j\le n\\\{i,j\}\in E}} \dfrac1{d_i+d_j}\right) \le2\sum_{i=1}^n f(v_i)\left(\sum_{\substack{1\le j\le n\\\{i,j\}\in E}} \dfrac1{d_i+1}\right) =\\ =2\sum_{i=1}^n f(v_i)\dfrac{d_i}{d_i+1} \le 2\sum_{i=1}^n f(v_i)\dfrac{n-1}{n} =\dfrac{2(n-1)}{n}\sum_{i=1}^n f(v_i), \end{gather*}$$

tehát

$\displaystyle \sum_{i=1}^n f(v_i) \ge \dfrac{n}{2(n-1)}\sum_{i=1}^n d_i. $

Statisztika:

24 dolgozat érkezett.

6 pontot kapott: Ali Richárd, Bodor Ádám, Bolla Donát Andor, Ercse Ferenc, Gál Mózes, Hajba Milán, Kun Zsófia, Miszori Márton, Pázmándi József Áron, Rajtik Sándor Barnabás, Sajter Klaus, Sánta Gergely Péter, Tóth László Pál.

5 pontot kapott: Balla Ignác , Görömbey Tamás.

2 pontot kapott: 1 versenyző.

1 pontot kapott: 4 versenyző.

0 pontot kapott: 3 versenyző.

Nem versenyszerű: 1 dolgozat.

A KöMaL 2026. januári matematika feladatai

24 dolgozat érkezett.
6 pontot kapott:	Ali Richárd, Bodor Ádám, Bolla Donát Andor, Ercse Ferenc, Gál Mózes, Hajba Milán, Kun Zsófia, Miszori Márton, Pázmándi József Áron, Rajtik Sándor Barnabás, Sajter Klaus, Sánta Gergely Péter, Tóth László Pál.
5 pontot kapott:	Balla Ignác , Görömbey Tamás.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	4 versenyző.
0 pontot kapott:	3 versenyző.
Nem versenyszerű:	1 dolgozat.

Már regisztráltál?
Új vendég vagy?