KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

Kifordítható

tetraéder

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

A. 580. Show that for every positive integer k and real number \varepsilon>0 there exists a polynomial p(x)=xn+an-1xn-1+...+a1x+a0 with real coefficients such that p(x) is divisible by the polynomial (x-1)k+1 and


\sum_{\ell=0}^{n-1} |a_\ell| < 1+\frac{(2+\varepsilon)k^2}{n}.

(5 points)

Deadline expired on 11 February 2013.


Google Translation (Sorry, the solution is published in Hungarian only.)

Az A. 574. feladat megoldásában a Tk(x) Csebisev-polinom abszolút értékét 1-gyel becsültük az \frac{2\ell}{n-1}-1 alakú helyeken, ahol 0\le\ell\len-1 egész szám volt:


  \left|a_\ell T_k\bigg(\frac{2\ell}{n-1}-1\bigg)\right| \le |a_\ell|.

Ez a becslés csak akkor lehet éles, ha \frac{2\ell}{n-1}-1 közel az +1 vagy -1 pontokhoz, vagy pedig a Tk valamelyik lokális szélsőértékéhez, ahol Tk(x) értéke szintén \pm1 (ez összesen k+1 pont a [-1,1] intervallumban), vagy pedig |a_\ell| kicsi, például 0.

A feladat megoldásához egy "ritka" polinomot fogunk konstruálni, aminek összesen csak k+2 nemnulla együtthatója van. (A polinom foka sokkal nagyobb lesz, mint k.)

Megoldás. Fel fogjuk használni az A. 574. feladat megoldásának több elemét, így a következő lemmát:

1. lemma. Ha a p(x)=x^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0 polinom osztható az (x-1)k+1 polinommal, akkor tetszőleges, legfeljebb k-adfokú q(y) polinomra

\sum\limits_{\ell=0}^n a_\ell \, q(\ell) = 0.

(A lemma bizonyítása megtalálható az A. 574. feladat megoldásánál.)

Legyen k és \varepsilon>0 rögzített; ezekhez szeretnénk a p polinomot megkonstruálni. Legyen \delta>0 és n egy nagy pozitív egész; ezeket majd később definiáljuk.

Legyenek -1=u_0<u_1<\ldots<u_k=1 azok a pontok, ahol a Tk Csebisev-polinom értéke \pm1: ekkor Tk(ui)=(-1)k-i. (Könnyű ellenőrizni, hogy u_i=\cos\frac{(k-i)\pi}{k}, de erre a képletre nem lesz szükség.) Minden i=0,1,\ldots,k-ra legen di az (az egyik) nemnegatív egész szám, ami a legközelebb van (n-1)\frac{1+u_i}2 számhoz, azaz


\left|d_i-(n-1)\frac{1+u_i}2\right|\le\frac12.

Ha


n>\max_{0\le i<k}\frac2{u_{i+1}-u_i}+1, (1)

akkor a di értékek különbözők: 0=d_0<d_1<\ldots<d_k=n-1. Ezen kívül legyen dk+1=n. A p(x) polinomot a következő alakban keressük:


p(x)=b_0x^{d_0}+b_1x^{d_1}+\ldots+b_{k+1}x^{d_{k+1}}

avagy, adi=bi, és minden i\not\in\{d_0,d_1,\ldots,d_{k+1}\} indexre ai=0.

2. lemma. (a) A b_0,b_1,\ldots,b_{k+1} valós számokat meg lehet választani úgy, hogy ne legyen mindegyikük nulla, és a p(x) polinom osztható legyen (x-1)k+1-gyel.

(b) A b_0,b_1,\ldots,b_{k+1} számok egyike sem lehet nulla, és a (b_0,b_1,\ldots,b_{k+1}) sorozat biztosan váltakozó előjelű.

Bizonyítás. (a) Legyen minden 0\lei\lek+1-re az xdi polinom osztási maradéka ri(x). Ez összesen k+2 polinom, mindegyikük foka legfeljebb k. Ezért a maradékok lineárisan összefüggnek: alkalmas b_0,b_1,\ldots,b_{k+1} számokkal, amelyek nem miond nullák, b_0r_0(x)+\ldots+b_{k+1}r_{k+1}(x)=0.

(b) Tegyük fel indirekte, hogy a (b_0,b_1,\ldots,b_{k+1}) sorozat nem váltakozó előjelű: valamelyik j indexre bj és bj+1 azonos előjelű, vagy egyikük 0. Lehetséges, hogy vannak szomszédos nulla értékek a sorozatban; olyan j-t válasszunk, amikor bj és bj+1 valamelyike nem nulla.

Legyen h(x)=(x-d_0)\ldots(x-d_{j-1})\cdot(x-d_{j+2})\ldots(x-d_{k+1}). Ez egy k-adfokú polinom, amire alkalmazhatjuk az 1. lemmát:


\sum\limits_{i=0}^{k+1} b_i\, h(d_i) = \sum\limits_{i=0}^n a_i\, h(i)
= 0.

A baloldalon kettő kivétellel minden tagban h(di)=0. A maradék két tagban h(dj) és h(dj+1) egyike sem nulla, és azonos előjelű. A bj és bj+1 együtthatók szintén azonos előjelűek, és nem mindettő nulla. Az összegben tehát egy vagy két, azonos előjelű nemnulla tag van, így az összeg nem lehet nulla, ellentmondás. Ezzel a lemmát igazoltuk. \Box

(Megjegyzés. Az is igaz, hogy a p(x) polinom konstans szorzótól eltekintve egyértelmű, de erre szintén nem lesz szükségünk.)

Most már van egy p(x) polinomunk, ami osztható a (x-1)k+1 polinommal. A p(x) polinomot végigosztva bk+1-gyel elérhetjük, hogy an=bk+1=1 legyen. A váltakozó előjel miatt ekkor b_k,b_{k-2},\ldots pozitív, b_{k-1},b_{k-3},\ldots pedig negatív lesz.

Az A. 574. feladat hasonlóan legyen


q(x) = T_k\left(\frac2{n-1}x-1\right).

Az 1. lemma szerint


\sum\limits_{i=0}^{k+1} b_i q(d_i) =\sum\limits_{i=0}^n a_i\, q(i) =0,

avagy, átrendezve,


\sum\limits_{i=0}^k (-b_i q(d_i)) = b_{k+1}q(d_{k+1}) = q(n).
(*)

A di számokat azért választottuk így, hogy q(di) "közel" legyen (-1)k-i-hez. Ezt most pontosabban megbecsüljük.

Az i=0 és i=k esetekben q(d0)=q(0)=Tk(-1)=(-1)k, illetve q(dk)=q(n-1)=Tk(1)=1.

Minden 1\lei\lek-1-re a Tk polinomnak lokális szélsőértéke van az ui helyen, ezért Tk'(ui)=0. Ezért van olyan \varthetai>0 szám, hogy 1\lei\lek-1 és |x-ui|<\varthetai esetén |Tk(x)-Tk(ui)|<\delta|x-ui|. Ha n-et olyan nagynak választjuk, hogy


n> \frac1{\min(\vartheta_1,\ldots,\vartheta_{k-1})}+1, (2)

akkor


\left|\Big(\tfrac2{n-1}d_i-1\Big)-u_i\right| =
\tfrac2{n-1} \left| d_i-(n-1)\tfrac{1+u_i}2 \right| \le
\tfrac2{n-1} \cdot \tfrac12 = \tfrac1{n-1} < \vartheta_i,

és


\big|q(d_i)-(-1)^{k-i}\big| =
\left| T_k\Big(\tfrac2{n-1}d_i-1\Big)-T_k(u_i)\right| \le
\delta \left| \Big(\tfrac2{n-1}d_i-1\Big)-u_i \right| <
\tfrac{\delta}{n-1}.

Ha

n>1+\delta,(3)

akkor |q(di)-(-1)k-i|<1 minden i-re, ezért q(d_0),q(d_1),\ldots,q(d_k) sorozat váltakozó előjelű, és


|q(d_i)| > 1-\tfrac{\delta}{n-1}.

Még szükségünk lesz q(dk+1)=q(n) felső becslésére is. Az A. 574. feladat megoldásából is tudjuk, hogy Tk(1)=1 és Tk'(1)=k2. Ezért van olyan \psi>0, hogy 1\lex\le1+\psi esetén Tk(x)<1+(1+\delta)k2(x-1). Ha


n>1+\frac2\psi,  (4)

akkor tehát


q(n) = T_k\left(1+\frac2{n-1}\right) < 1 + (1+\delta)k^2\cdot\tfrac2{n-1}.

Az (*) azonosság baloldalát alulról, a jobboldalt felülről becsüljük. A baloldalon minden tag pozitív, ezért


\sum\limits_{i=0}^k (-b_i q(d_i)) = 
\sum\limits_{i=0}^k |b_i|\cdot |q(d_i)| \ge
\Big(1-\tfrac{\delta}{n-1}\Big) \sum_{i=0}^k |b_i| =
\Big(1-\tfrac{\delta}{n-1}\Big) \sum_{i=0}^{n-1} |a_i|,

illetve


q(n) < 1 + (1+\delta)k^2\cdot\tfrac2{n-1}.

Tehát


\sum_{i=0}^{n-1} |a_i| <
\frac1{1-\tfrac{\delta}{n-1}} \sum\limits_{i=0}^k (-b_i q(d_i)) = 
\frac1{1-\tfrac{\delta}{n-1}} q(n) <
\frac{1 + (1+\delta)k^2\cdot\tfrac2{n-1}}{1-\tfrac{\delta}{n-1}}.

Már csak a feladatbeli alakra kell rendeznünk ezt a becslést.


\frac{1 + (1+\delta)k^2\cdot\tfrac2{n-1}}{1-\tfrac{\delta}{n-1}} =
\frac{(n-1) + 2(1+\delta)k^2}{n-1-\delta} =
1 + \frac{2(1+\delta)k^2+\delta}n
\cdot\left(1+\frac{1+\delta}{n-1-\delta}\right)

Válasszuk \delta-t olyan kicsinek, hogy


2(1+\delta)k^2+\delta \le (2+\tfrac\varepsilon2)k^2

teljesüljön, például legyen


d=\frac{k^2\varepsilon}{k^2+1}.

Ezután válasszuk n-et olyan nagynak, hogy


1+\frac{1+\delta}{n-1-\delta} < \frac{2+\varepsilon}{2+\tfrac\varepsilon2},

is érvényes legyen. Ezt is elérhetjük, ha


n > (1+\delta)\left(\frac4\varepsilon+2\right).   (5)

Ekkor tehát


\sum_{i=0}^{n-1} |a_i| < 
1 + \frac{2(1+\delta)k^2+\delta}n
\cdot\left(1+\frac{1+\delta}{n-1-\delta}\right) <
1 + \frac{(2+\tfrac\varepsilon2)k^2}{n} \cdot \frac{2+\varepsilon}{2+\tfrac\varepsilon2}
= 1 + \frac{(2+\varepsilon)k^2}{n}.

A becsléseink akkor érvényesek, ha (1)-(5) mindegyike teljesül. Ez csak véges sok, csak a k-tól függő alsó korlát az n-re.


Statistics on problem A. 580.
0 student sent a solution.


  • Problems in Mathematics of KöMaL, January 2013

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley