![]() |
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.
Statisztika:
1 dolgozat érkezett. 0 pontot kapott: 1 versenyző.
A KöMaL 2020. októberi matematika feladatai