 |
Az A. 784. feladat (2020. október) |
A. 784. Legyenek \(\displaystyle n\), \(\displaystyle s\), \(\displaystyle t\) pozitív egész számok és \(\displaystyle 0<\lambda<1\). Adott egy \(\displaystyle n\) csúccsal és legalább \(\displaystyle \lambda n^2\) éllel rendelkező egyszerű gráf. Azt mondjuk, hogy az \(\displaystyle (x_1,\ldots,x_s,y_1,\ldots y_t)\) egy jó beillesztés, ha az \(\displaystyle x_i\) és \(\displaystyle y_j\) betűk nem feltétlenül különböző csúcsokat jelölnek, és mindegyik \(\displaystyle x_iy_j\) éle a gráfnak (\(\displaystyle 1~\le i \le s\), \(\displaystyle 1\le j\le t\)). Bizonyítsuk be, hogy a jó beillesztések száma legalább \(\displaystyle \lambda^{st}n^{s+t}\).
Javasolta: Williams Kada (Cambridge)
(7 pont)
A beküldési határidő 2020. november 10-én LEJÁRT.
Megoldási ötletek. Számozzuk a csúcsokat az \(\displaystyle 1,2,\dots,n\) számokkal. Ha \(\displaystyle x\) és \(\displaystyle y\) csúcsa a \(\displaystyle G\) gráfnak, akkor legyen \(\displaystyle G(x,y)=1\), ha \(\displaystyle xy\) él, és \(\displaystyle G(x,y)=0\), ha \(\displaystyle xy\) nem él. Feltéve, hogy \(\displaystyle G\) éleinek száma legalább \(\displaystyle \frac12\lambda n^2\), fennáll, hogy
\(\displaystyle \sum_{x,y=1}^n G(x,y)\ge \lambda n^2.\)
A jó beillesztések száma pedig:
\(\displaystyle S=\sum_{x_1,\dots,x_s,y_1,\dots,y_t=1}^n \left[\prod_{i=1}^s \prod_{j=1}^t G(x_i,y_j)\right].\)
(Ugyanis \(\displaystyle (x_1,\dots,x_s,y_1,\dots,y_t)\) jó beillesztés akkor és csak akkor, ha \(\displaystyle G(x_i,y_j)=1\) minden \(\displaystyle i=1,\dots,s\) és \(\displaystyle j=1,\dots,t\) esetén.)
Példaképpen tekintsük előbb az \(\displaystyle s=t=2\) esetet (ami, jegyezzük meg, az elemi kombinatorikában cseresznyeszámolásként ismeretes):
\(\displaystyle S=\sum_{x,x',y,y'=1}^n G(x,y)G(x',y)G(x,y')G(x',y').\)
Adott \(\displaystyle y,y'\) érték mellett legyen \(\displaystyle G_{y,y'}(x)=G(x,y)G(x,y')\). Ekkor
\(\displaystyle S=\sum_{y,y'=1}^n \sum_{x=1}^n \sum_{x'=1}^n G_{y,y'}(x)G_{y,y'}(x'),\)
ami teljes négyzetként ismerhető fel:
\(\displaystyle S=\sum_{y,y'=1}^n \left(\sum_{x=1}^n G_{y,y'}(x)\right)^2.\)
Használjuk fel \(\displaystyle t\in [0,\infty)\), \(\displaystyle t\mapsto t^2\) konvexitását (tehát a Jensen-egyenlőtlenséget):
\(\displaystyle \frac1{n^2}\sum_{y,y'=1}^n \left(\sum_{x=1}^n G_{y,y'}(x)\right)^2\ge \left(\frac1{n^2} \sum_{y,y'=1}^n \sum_{x=1}^n G_{y,y'}(x)\right)^2.\)
A zárójelben szereplő összeggel járjunk el ugyanígy. Cseréljük fel a szummát és alkalmazzunk konvexitási becslést.
\(\displaystyle \sum_{y,y'=1}^n \sum_{x=1}^n G_{y,y'}(x)=\sum_{x=1}^n \sum_{y,y'=1}^n G(x,y)G(x,y')=\)
\(\displaystyle =\sum_{x=1}^n \left(\sum_{y=1}^n G(x,y)\right)^2 \ge n\cdot \left(\frac1n \sum_{x=1}^n \sum_{y=1}^n G(x,y)\right)^2.\)
Végtermékként az élszámot látjuk. Ez teszi lehetővé a kitűzött alsó becslést.
A feladatbeli általánosítás hasonlóképp bizonyítható. Az eltérés mindössze annyi, hogy \(\displaystyle s\)-edik, illetve \(\displaystyle t\)-edik hatványokat tudunk felismerni.
Statisztika:
1 dolgozat érkezett. 0 pontot kapott: 1 versenyző.
A KöMaL 2020. októberi matematika feladatai