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:

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

A KöMaL 2020. októberi matematika feladatai