A B. 4330. feladat (2011. január)

B. 4330. Melyik az a kétváltozós p polinom, amelyre

Javasolta: Hraskó András (Budapest)

(4 pont)

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

Megoldás. Tetszőleges $\displaystyle n$ természetes számra legyen $\displaystyle p_n=p_n(u,v)$ az a kétváltozós polinom, amelyre

$\displaystyle p_n(x+y,xy)=\sum_{k=0}^nx^{n-k}y^k.$

Ekkor $\displaystyle p_0(u,v)=1$, $\displaystyle p_1(u,v)=u$, $\displaystyle p_2(u,v)=u^2-v$, és minden $\displaystyle n$ pozitív egészre fennáll az

$\displaystyle (x+y)p_n(x+y, xy)=p_{n+1}(x+y,xy)+xyp_{n-1}(x+y,xy)$

összefüggés, ami azt jelenti, hogy

$\displaystyle p_{n+1}(u,v)=up_n(u,v)-vp_{n-1}(u,v)$

teljesül minden $\displaystyle (u,v)$ párra, ahol $\displaystyle u^2\ge 4v$. Mivel ez az összefüggés bármely rögzített $\displaystyle v$ érték mellett végtelen sok $\displaystyle u$ esetén fennáll, minden $\displaystyle u$-ra fenn kell állnia, hiszen ha $\displaystyle v$ értéke rögzített, akkor már csak egyváltozós polinomról van szó. A $\displaystyle p_n$ polinomsorozatot tehát a fenti rekurzió egyértelműen meghatározza.

Azt állítjuk, hogy tetszőleges $\displaystyle n$ természetes számra

$\displaystyle p_n(u,v)=\sum_{i=0}^{[n/2]}(-1)^i {n-i\choose i}u^{n-2i}v^i.$

Ez $\displaystyle n=0$ és $\displaystyle n=1$ esetén nyilván igaz. Ha pedig $\displaystyle n$-ig bezárólag már igazoltuk ezt az összefüggést, akkor a rekurzió alapján

$\displaystyle p_{n+1}(u,v)=u\left\{ \sum_{i=0}^{[n/2]}(-1)^i {n-i\choose i}u^{n-2i}v^i \right\}-v\left\{ \sum_{j=0}^{[(n-1)/2]}(-1)^j {n-1-j\choose j}u^{n-1-2j}v^j \right\}$

$\displaystyle =\left\{ \sum_{i=0}^{[n/2]}(-1)^i {n-i\choose i}u^{n+1-2i}v^i \right\} +\left\{ \sum_{i=1}^{[(n+1)/2]}(-1)^i {n-i\choose i-1}u^{n+1-2i}v^i \right\}$

$\displaystyle =\sum_{i=0}^{[(n+1)/2]}(-1)^i {n+1-i\choose i}u^{n+1-2i}v^i,$

hiszen $\displaystyle u^{n+1-2i}v^i$ együtthatója $\displaystyle i=0$ esetén mind a két kifejezésben 1, $\displaystyle 1\le i\le [n/2]$ esetén

$\displaystyle (-1)^i {n-i\choose i}+(-1)^i {n-i\choose i-1}=(-1)^i {n+1-i\choose i},$

ha pedig $\displaystyle n+1$ páros, akkor $\displaystyle i=(n+1)/2$ esetén $\displaystyle (-1)^{(n+1)/2}$.

Ezen összefüggés alapján a keresett polinom

$\displaystyle p(u,v)=p_{20}(u,v)=\sum_{i=0}^{10}(-1)^i{20-i\choose i}u^{20-2i}v^i =u^{20}-19u^{18}v+153u^{16}v^2-680u^{14}v^3+$

$\displaystyle +1820u^{12}v^4-3003u^{10}v^5+3003u^8v^6-1716u^6v^7+495u^4v^8-55u^2v^9+ v^{10}.$

Statisztika:

38 dolgozat érkezett.
4 pontot kapott:	Ágoston Péter, Baráti László, Beleznay Soma, Bősze Zsuzsanna, Bunth Gergely, Czipó Bence, Énekes Péter, Halász Dániel, Homonnay Bálint, Kabos Eszter, Kiss 542 Robin, Kúsz Ágnes, Lenger Dániel, Ódor Gergely, Sándor Áron Endre, Strenner Péter, Szabó 928 Attila, Tekeli Tamás, Tran Trong Hoang Tuan, Vajk Dóra, Viharos Andor, Vuchetich Bálint, Weisz Gellért, Zelena Réka.
3 pontot kapott:	Barczel Nikolett, Sagmeister Ádám, Schultz Vera Magdolna, Zsakó András.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	4 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2011. januári matematika feladatai