[964] Róbert Gida | 2015-02-12 07:38:19 |
 Szerintem igaz. Egy gyengébb állítást belátok: minden L>0-ra létezik &tex;\displaystyle c(L,k)>0&xet;, hogy, ha az n különböző pozitív egész mindegyike kisebb, mint L*n, akkor kiválasztható k darab (&tex;\displaystyle n\ge k&xet; esetén), hogy azok lkktje nagyobb, mint &tex;\displaystyle c(L,k)*n^k&xet;.
Legyen &tex;\displaystyle H=\frac {\prod_{i=1}^k c_i}{\prod_{1\le i<j\le k}lnko(c_i,c_j)}&xet;, ugyan H nem mindig egész (k<4-re viszont egész), de mindig igaz, hogy &tex;\displaystyle H\le lkkt(c_1,..,c_k)&xet; (használjuk az lnko,lkkt prímtényezős alakját). Az &tex;\displaystyle a_1,..,a_n&xet; számok közül dobjuk ki az &tex;\displaystyle \frac n2&xet;-nél kisebbeket, marad legalább &tex;\displaystyle \frac n2&xet; szám az &tex;\displaystyle [\frac n2,Ln]&xet; intervallumból. Az egyszerűség kedvéért legyen n osztható &tex;\displaystyle k&xet;-val, és tekintsük az &tex;\displaystyle (u*L*k,(u+1)*L*k]&xet; intervallumokat &tex;\displaystyle u=0,..,\frac{n}{k}-1&xet;-re. Ezek uniója lefedi &tex;\displaystyle [\frac n2,Ln]&xet;-et, így skatulyaelv alapján van olyan intervallum, amibe legalább k darab &tex;\displaystyle a_i&xet; szám esik. Válasszunk ki ezek közül k darabot: &tex;\displaystyle c_1,..,c_k&xet;, ekkor &tex;\displaystyle \frac n2\le c_i&xet; és létezik S, hogy &tex;\displaystyle S< c_i \le S+r&xet;, ahol &tex;\displaystyle r=L*k&xet; konstans, de akkor &tex;\displaystyle i\neq j&xet;-re &tex;\displaystyle lnko(c_i,c_j)<r&xet;, így &tex;\displaystyle H\ge \frac {({\frac n2})^k}{r^{\frac{k(k-1)}{2}}}=const*n^k&xet;, ami kellett.
Az eredeti problémánál anno még pont így indultam ki.
|
Előzmény: [962] Fálesz Mihály, 2015-02-11 22:45:34 |
|
|
[962] Fálesz Mihály | 2015-02-11 22:45:34 |
 Engem jobban érdekelne egy &tex;\displaystyle \varepsilon&xet; nélküli megoldás: &tex;\displaystyle n^{k-\varepsilon}&xet; helyett &tex;\displaystyle cn^k&xet; valamilyen pozitív &tex;\displaystyle c&xet; konstanssal.
&tex;\displaystyle k=2&xet;-re mutatok egyet. Az egyszerűség kedvéért legyen &tex;\displaystyle n&xet; páros, &tex;\displaystyle n=2m&xet;. Vegyük a számok nagyobbik felét: legyen &tex;\displaystyle a_1,a_2,\dots,a_{m+1}&xet; az &tex;\displaystyle m+1&xet; legnagyobb szám. Ezeknél van &tex;\displaystyle m-1&xet; kisebb, tehát &tex;\displaystyle a_1,a_2,\dots,a_{m+1}\ge m&xet;.
Tekintsük az &tex;\displaystyle \frac1{a_1},\dots,\frac1{a_{m+1}}&xet; számokat. Ez &tex;\displaystyle m+1&xet; különböző valós szám a &tex;\displaystyle \left(0,\frac1m\right]&xet; intervallumban; van tehát közöttük kettő, &tex;\displaystyle a_i&xet; és &tex;\displaystyle a_j&xet; aminek a különbsége kisebb, mint &tex;\displaystyle \frac1{m^2}&xet;. Ezekre
&tex;\displaystyle
\frac1{m^2} > \left|\frac1{a_i}-\frac1{a_j}\right|
\ge \frac1{lkkt(a_i,a_j)};
&xet;
&tex;\displaystyle
lkkt(a_i,a_j) > m^2 = \frac{n^2}4.
&xet;
|
Előzmény: [960] w, 2015-02-11 21:48:10 |
|
|
[960] w | 2015-02-11 21:48:10 |
 Csak egy kis apróság: kérlek, tedd olvashatóvá a megoldásaidat. Lehet, hogy egyedül vagyok ezzel, de nehezen átlátható az, amit írsz, bármennyire is érdekes lehet.
Lehet ezt indukció nélkül is. Leírom - remélem - átlátható(bb)an.
A.633. megoldása.
Felhasználjuk, hogy ha &tex;\displaystyle d(m)&xet; az &tex;\displaystyle m>0&xet; egész pozitív osztóinak száma, és &tex;\displaystyle t>0&xet; adott, akkor van olyan &tex;\displaystyle C(t)&xet; konstans, melyre &tex;\displaystyle d(m)<C(t)m^t&xet; teljesül bármely &tex;\displaystyle m>0&xet; egészre. (Ennek belátása a 2008-as Kürschák 1. feladatához hasonló - utóbbi pl. megtalálható a VersenyVizsga portálon.)
Azt is belátjuk, hogy adott &tex;\displaystyle \epsilon>0&xet; és &tex;\displaystyle k>1&xet; egész esetén elég nagy &tex;\displaystyle n&xet;-re bármely &tex;\displaystyle n&xet; különböző pozitív egész között van &tex;\displaystyle k&xet; darab, aminek legkisebb közös többszöröse &tex;\displaystyle n^{k-\epsilon}&xet;-nál nagyobb.
A megoldáshoz legyen &tex;\displaystyle t>0&xet; adott (később megválasztjuk), és írjuk le egy listában mind a &tex;\displaystyle \binom nk&xet; legkisebb közös többszöröst. Legyen a kapott lista &tex;\displaystyle L&xet;, és jelölje &tex;\displaystyle x&xet; a benne előforduló különböző számok számát. Bármely &tex;\displaystyle m\in L&xet;-re jelölje &tex;\displaystyle E(m)&xet; az &tex;\displaystyle m&xet; előfordulását &tex;\displaystyle L&xet;-ben. Ekkor felírhatjuk, hogy
&tex;\displaystyle \binom nk=|L|=\sum_{m\in L}E(m).&xet; | (1) |
Hogyha van olyan &tex;\displaystyle m\in L&xet;, melyre &tex;\displaystyle m\ge n^k&xet;, akkor teljesül az állítás. Tegyük most fel, hogy bármely listabeli szám legfeljebb &tex;\displaystyle n^k&xet;.
Hogyha &tex;\displaystyle k&xet; darab szám legkisebb közös többszöröse &tex;\displaystyle m&xet;, akkor ezek mind osztják &tex;\displaystyle m&xet;-et, vagyis &tex;\displaystyle d(m)&xet;-félék lehetnek. Ebből következik, hogy
&tex;\displaystyle E(m)\le \binom{d(m)}k\le&xet;
&tex;\displaystyle \le d(m)^k< C(t)^km^{tk}\le C(t)^k(n^k)^{tk}.&xet; | (2) |
Másfelől, hogyha &tex;\displaystyle n\ge 2k&xet;, akkor
&tex;\displaystyle \binom nk=\frac{n(n-1)\dots(n-k+1)}{k!}\ge \frac{(n/2)^k}{k!}=\frac1{2^k\cdot k!}n^k.&xet; | (3) |
Beleírva &tex;\displaystyle (2)&xet;-t és &tex;\displaystyle (3)&xet;-at &tex;\displaystyle (1)&xet;-be, &tex;\displaystyle n\ge 2k&xet;-ra
&tex;\displaystyle \frac1{2^k\cdot k!}n^k<x\cdot C(t)^k(n^k)^{tk},&xet;
&tex;\displaystyle c(t)\cdot n^{k-tk^2}<x,&xet; | (4) |
ahol &tex;\displaystyle c(t)=\frac1{2^k\cdot k!\cdot C(t)^k}&xet;. Most válasszunk &tex;\displaystyle t=\frac{\epsilon}{2k^2}&xet;-et, és tegyük fel, hogy &tex;\displaystyle n>c(t)^{-2/\epsilon}&xet;: ekkor &tex;\displaystyle (4)&xet;-ből adódik:
&tex;\displaystyle x>c(t)n^{\epsilon/2}\cdot n^{k-\epsilon}>n^{k-\epsilon},&xet;
tehát a legnagyobb a legkisebb közös többszörösök közül &tex;\displaystyle n^{k-\epsilon}&xet;-nál nagyobb lesz.
Tehát ha &tex;\displaystyle n> \max\left\{2k,c\left(\frac{\epsilon}{2k^2}\right)^{-2/\epsilon}\right\}&xet;, akkor mindenképpen lesz &tex;\displaystyle n&xet; különböző pozitív egész között &tex;\displaystyle k&xet;, aminek legkisebb közös többszöröse &tex;\displaystyle n^{k-\epsilon}&xet;-nál nagyobb.
|
Előzmény: [959] Róbert Gida, 2015-02-11 20:41:13 |
|
[959] Róbert Gida | 2015-02-11 20:41:13 |
 &tex;\displaystyle {\bf a633.}&xet; megoldása: Többet látok be. Minden pozitív k egészre és c>0 valós számra igaz, hogy létezik N(k,c), hogy n>N(k,c) esetén n különböző pozitív egész szám közül kiválasztható k, hogy azok lkkt-je nagyobb, mint &tex;\displaystyle n^{k-c}&xet;(a feladat N(4,0.01) létezéséről szól).
Az állítás &tex;\displaystyle k=1&xet;-re trivi, N(1,c)=1 megfelelő (egyetlen szám lkkt-je maga a szám). Teljes indukció. Ha &tex;\displaystyle (k-1)&xet;-re és minden &tex;\displaystyle c>0&xet;-ra igaz az állítás, akkor kell &tex;\displaystyle k&xet;-ra. Legyen &tex;\displaystyle n\ge k&xet; (hogy egyáltalán tudjunk k számot választani). Legyenek a számaink &tex;\displaystyle a_1,..,a_n&xet;, ha létezik köztük nagyobb, mint &tex;\displaystyle n^k&xet;, akkor készen vagyunk (válasszunk még ezen szám mellé (k-1)-et tetszelőgesen). Így feltehető &tex;\displaystyle a_i\le n^k&xet; minden &tex;\displaystyle i&xet;-re. Legyen &tex;\displaystyle m&xet; az &tex;\displaystyle a_i&xet; számok legnagyobbika, ekkor persze &tex;\displaystyle n\le m\le n^k&xet; teljesül.
Szükségem lesz a következő ismert tételre: minden &tex;\displaystyle \epsilon >0&xet;-ra létezik &tex;\displaystyle M(\epsilon)&xet;, hogy &tex;\displaystyle m>M(\epsilon)&xet; esetén &tex;\displaystyle m&xet;-nek kevesebb, mint &tex;\displaystyle m^{\epsilon}&xet; (pozitív) osztója van. Nyilvánvalóan minden i-re &tex;\displaystyle d=lnko(m,a_i)&xet; az m egy osztója, amire az előző tétel alapján rögzített t-re csupán &tex;\displaystyle m^t\le n^{k*t}&xet; lehetőség van. De akkor a skatulyaelv alapján van olyan d, ami legalább &tex;\displaystyle \frac{n-1}{n^{kt}}>n^{1-2*k*t}&xet;-szer szerepel. A számunkra érdekes eset persze az, amikor &tex;\displaystyle 1-2kt>0&xet;. Válasszuk ki ezen &tex;\displaystyle b_1,..,b_s&xet; számokat az &tex;\displaystyle a_i&xet; számok közül (&tex;\displaystyle s>n^{1-2kt}&xet;). Vegyük észre, hogy, ha ezen számok közül (k-1)-et kiválasztunk &tex;\displaystyle c_1..,c_{k-1}&xet;, akkor &tex;\displaystyle lkkt(m,c_1,..c_{k-1})=lkkt(d\frac md,d\frac {c_1}{d},..,d\frac{c_{k-1}}{d})=d*lkkt(\frac md,\frac {c_1}{d},..,\frac{c_{k-1}}{d})&xet; &tex;\displaystyle =d\frac md lkkt(\frac {c_1}{d},..,\frac{c_{k-1}}{d})=m*lkkt(e_1,..e_{k-1})\ge n*lkkt(e_1,..,e_{k-1})&xet;, ahol használtuk, hogy &tex;\displaystyle lnko(m,c_i)=d&xet; miatt &tex;\displaystyle \frac md,\frac {c_i}{d}&xet; rel. prímek, és azt, hogy &tex;\displaystyle m\ge n&xet;, és itt &tex;\displaystyle e_i&xet; egész. Most lehet indukciózni, rögzített &tex;\displaystyle u>0&xet;-ra, ha s elég nagy (azaz &tex;\displaystyle n&xet; elég nagy), akkor kiválasztható a különböző(!) &tex;\displaystyle b_1,..,b_s&xet; számok közül (k-1) úgy, hogy &tex;\displaystyle lkkt(c_1,..,c_{k-1})>s^{k-1-u}&xet;, na de ekkor &tex;\displaystyle lkkt(m,c_1,..c_{k-1})>n^{1+(1-2kt)(k-1-u)}&xet;, ha ez nagyobb, mint &tex;\displaystyle n^{k-c}&xet;, akkor vagyunk készen. Azaz kell:
&tex;\displaystyle 1+(1-2kt)(k-1-u)>k-c&xet;, azaz k-2k(k-1)t-u+2ktu>k-c, tehát &tex;\displaystyle c>2k(k-1)t+u-2ktu&xet;, de &tex;\displaystyle 2ktu>0&xet; így elég: &tex;\displaystyle c>2k(k-1)t+u&xet;, de ekkor &tex;\displaystyle u=\frac {c}{4}&xet; és &tex;\displaystyle t=min(\frac{1}{4k},\frac{c}{8k(k-1)})>0&xet; jó választás, mert így &tex;\displaystyle 2k(k-1)t+u\le \frac c4+\frac c4<c&xet;, és a jóval korábbi &tex;\displaystyle 1-2kt>0&xet; egyenlőtlenség is teljesül. Ezzel a feladat állítását beláttuk.
|
|
[958] Róbert Gida | 2015-02-11 20:41:00 |
 &tex;\displaystyle {\bf a634.}&xet; megoldása: az állítás hamis, &tex;\displaystyle n=2;f(x)=x^2&xet; egy trivi ellenpélda. Mindegy, majd újra kitűzitek.
|
|
[957] w | 2015-01-31 10:02:38 |
 A.630. hivatalos megoldása megjelent, szép, tetszik.
Két megoldást találtam, egyik sem az, úgyhogy miért is ne gyorsan leírom őket. Szerintem érdekesek. (Az eleje, hogy megnézzük az érintőszakaszokat, nálam is ugyanaz.)
Nézzük a &tex;\displaystyle P&xet;-ből &tex;\displaystyle FG&xet;-re állított merőlegest. Triviálisan &tex;\displaystyle Q&xet; rajta van ezen. Tehát ha belátjuk, hogy &tex;\displaystyle IP&xet; is merőleges &tex;\displaystyle FG&xet;-re, készen vagyunk.
1. befejezés: ez ismert módon ekvivalens azzal, hogy &tex;\displaystyle IF^2+PG^2=IG^2+PF^2&xet;. Ami pedig nyilvánvaló, hisz mindkét oldal az &tex;\displaystyle F&xet;-ből és &tex;\displaystyle G&xet;-ből a beírt körhöz húzott érintőszakasznak, illetve a beírt kör sugarának a négyzetösszege.
2. befejezés: tekintsük a &tex;\displaystyle P&xet; elfajuló kört és a beírt kört. Az &tex;\displaystyle F&xet; pont és &tex;\displaystyle G&xet; pont hatványa mindkét körre megegyezik, így &tex;\displaystyle FG&xet; a hatványvonaluk, ami merőleges az &tex;\displaystyle IP&xet; centrálisra.
[talán mindhárom megoldás átalakítható egymásba, de különböző megközelítésűek]
|
|
|
|
[954] Kovács 972 Márton | 2015-01-20 16:15:42 |
 Tudna valaki megoldást/segítséget mutatni az A.536-hoz? A feladat szövege megtalálható itt.
|
|
[953] w | 2015-01-16 16:55:14 |
 Az A.630. feladat szerintem is nagyon könnyű volt. Könnyű kitűzni feladatot úgy, hogy sokkal bonyolultabb megoldásra gondol valaki. (Ha meg van cél mögötte, akkor olyasmi lehet, hogy népszerűsítse a pontversenyt.)
A B.4673. feladat alulértékelését azzal magyaráznám, hogy nagyon ismert példa.
|
Előzmény: [952] HoA, 2015-01-16 16:11:24 |
|
[952] HoA | 2015-01-16 16:11:24 |
 Mit gondoltok, miért volt "A" kategóriás feladat &tex;\displaystyle \bf A 630&xet; ? Szerintem a hasonló témájú &tex;\displaystyle \bf B 4673&xet; nehezebb volt.
|
|
[951] Róbert Gida | 2014-12-19 15:05:48 |
 10 hosszú a leghosszabb sorozat ami nem tartalmaz 4 hosszú számtani sorozatot, egy ilyen: 1,2,3,2,1,2,1,0,1,2.
Továbbá nagyon úgy tűnik számomra, hogy 5 hosszú már mindig lesz benne, 70000 tagút is könnyű találni. 54 tagúból pedig összesen 1514921499 darab van, ha &tex;\displaystyle x_1=0;x_2=1&xet;-gyel indul a sorozat (nyilván &tex;\displaystyle x_1&xet; nem érdekes, és feltehetjük &tex;\displaystyle x_2=1&xet;-et is, különben szorozzunk minden tagot (-1)-gyel).
|
Előzmény: [949] w, 2014-12-17 23:16:46 |
|
[950] w | 2014-12-18 15:28:11 |
 Az &tex;\displaystyle A=11,8&xet; választással és
&tex;\displaystyle f(t)=\sum_{k=1}^\infty A^k\sin\frac{t}{(2A)^k}&xet;
függvénnyel számolva, nem lesz &tex;\displaystyle 215&xet; hosszú számtani sorozat.
Remélem, azért nem számoltam el.
A hivatalos megoldásnál sokkal kevésbé hanyag a számolás, de az alapötletek ugyanazok. A fő eltérés, hogy a (3) becslésnél &tex;\displaystyle \frac 15&xet; helyett &tex;\displaystyle 4\sin^2\frac12\sin\frac\pi3>0,7962&xet;-es szorzótényező jön ki, mert &tex;\displaystyle D=(h+1)d&xet; esetén már &tex;\displaystyle D\in\left[(2A)^s;2\cdot (2A)^s\right]&xet;.
|
Előzmény: [946] Fálesz Mihály, 2014-12-16 16:21:22 |
|
[949] w | 2014-12-17 23:16:46 |
 Nagyon köszönöm. Végül nagyjából ugyanúgy számoltam, mint a megjelent megoldásban (az ötletet követve, a "4 hosszú számtani sorozat"-dolog kicsit bonyolultabbá tette a számításokat).
Biztos lehetne még rágni ezen a szinuszos függvényen párszázat a korláton, ahhoz mondjuk le kellene írni egy megoldást, csak a lényeget kiemelve. Kíváncsi lennék másik függvényre is.
Az már picit nemtriviális, hogy azért &tex;\displaystyle 4&xet;-tagú számtani sorozat biztos van, de még egyszerűen kijön fabunkóval. Ennek bizonyításához írjunk &tex;\displaystyle x_k&xet; alá &tex;\displaystyle +&xet; jelet, ha &tex;\displaystyle x_{k+1}-x_k=1&xet; és &tex;\displaystyle -&xet; jelet, ha &tex;\displaystyle x_{k+1}-x_k=-1&xet;. 1.) Hogyha &tex;\displaystyle 6&xet; tagon keresztül semely két szomszédos jel sem egyezik meg, akkor kész, mert lesz &tex;\displaystyle +,-,+,-,+,-&xet; típusú rész, ami négytagú (konstans) számtani sorozatot jelez. 2.) Ha három szomszédos jel azonos, akkor az is négytagú sz.s.-t ad. 3.) Egyébként: Van a sorozatunk közepén két szomszédos azonos jel, mondjuk &tex;\displaystyle -&xet;. Akkor mivel már harmadik &tex;\displaystyle -&xet; nem lesz mellettük, így &tex;\displaystyle +,-,-,+&xet; részünk van; akkor utóbbi &tex;\displaystyle +&xet; után ha &tex;\displaystyle +,-&xet; vagy &tex;\displaystyle -,+&xet; jön, akkor találunk négytagú sz.s.-t, mert &tex;\displaystyle +,-&xet; vagy &tex;\displaystyle -,+&xet; esetén &tex;\displaystyle x_{k+2}=x_k&xet;. Ha &tex;\displaystyle +,+&xet; jön, akkor van három &tex;\displaystyle +&xet; egymás után, marad az a lehetőség, hogy &tex;\displaystyle +,-,-,+,-,-&xet; lesz. Ezt bármeddig folytathatnám: &tex;\displaystyle +,-,-,+,-,-,+,-,-,...&xet;. De akkor találunk három darab &tex;\displaystyle +,-,-&xet; blokkot, ezekben egyenlőt változik &tex;\displaystyle (x_k)&xet; => 4-tagú sz.s.
Remélem, senkit sem zavar, hogy &tex;\displaystyle +,-&xet; írására volt éppen kedvem &tex;\displaystyle 0,1&xet; helyett.
|
Előzmény: [946] Fálesz Mihály, 2014-12-16 16:21:22 |
|
|
[947] Kovács 972 Márton | 2014-12-16 16:53:40 |
 Leírnád kérlek a megoldását? Gondolkodtam rajta, de azóta sem sikerült rájönni.
Az világos, hogy &tex;\displaystyle A&xet; és &tex;\displaystyle B&xet; játszani fog egymással, mert ha az &tex;\displaystyle A&xet; csapat megszerzett &tex;\displaystyle x&xet; pontja mellett &tex;\displaystyle B&xet; megver mindenki mást, (ekkor még biztosan &tex;\displaystyle A&xet; nyer) akkor ennél &tex;\displaystyle B&xet; nem tud több pontot szerezni, így &tex;\displaystyle A&xet; &tex;\displaystyle y>x&xet; esetén is biztosan nyer.
|
Előzmény: [942] w, 2014-12-13 14:31:46 |
|
[946] Fálesz Mihály | 2014-12-16 16:21:22 |
 Endre a következő megoldási ötletet küldte az A. 628. feladathoz.
Vegyük ezt a függvényt: &tex;\displaystyle f(x) = \sum_{k=1}^{\infty} 50^k \sin\frac{x}{100^k}&xet;. Ha egy 4 hosszú számtani sorozat különbségei &tex;\displaystyle 100^s&xet; közelében vannak, akkor az &tex;\displaystyle 50^s \sin\frac{x}{100^s}&xet; függvény szerinti értékei nagyon távol vannak a lineáristól. &tex;\displaystyle \sum_{k=1}^{s-1} 50^k \sin\frac{x}{100^k}&xet; amplitúdója kicsi, &tex;\displaystyle \sum_{k=s+1}^{\infty} 50^k \sin\frac{x}{100^k}&xet; pedig ilyen skálán nézve majdnem lineáris, ezért mindezek összege nem adhat 4 ponton lineáris függvényt. |
|
Közben leírtam valamivel részletesebben, de érdemes lehet kipróbálni, hogy ki tudod-e számolni magad is, illetve a megoldásbeli kb. 900-es korlátot meddig tudod lenyomni.
|
Előzmény: [943] w, 2014-12-15 16:39:56 |
|
|
[944] Róbert Gida | 2014-12-15 19:25:03 |
 Korlátos sorozatra igaz, következik a Van der Waerden tételből. Ekkor az sem kell, hogy &tex;\displaystyle |x_k-x_{k+1}|=1&xet; teljesül.
(igazából korlátosság sem kell, csak, hogy jó hosszan az &tex;\displaystyle x_k&xet; nem sokat változik).
|
Előzmény: [943] w, 2014-12-15 16:39:56 |
|
[943] w | 2014-12-15 16:39:56 |
 Az A628-ra valaki [Fálesz] mondana segítséget/megoldást?
|
|
[942] w | 2014-12-13 14:31:46 |
 B.4660. Igazából csak el kell kezdeni, és elegendő apró következtetéssel kijön. Azt mondják, hogy ha &tex;\displaystyle A&xet; csak &tex;\displaystyle x&xet; pontot szerez, akkor mindenképpen nyer, ám megeshet, hogy egy &tex;\displaystyle B&xet; csapat megveri, úgy, hogy &tex;\displaystyle A&xet; &tex;\displaystyle y>x&xet; pontot szerez.
Ebből következik, hogy &tex;\displaystyle A&xet; és &tex;\displaystyle B&xet; egymás ellen fog játszani. Mi lehet ezen meccs eredménye?
|
Előzmény: [941] Kovács 972 Márton, 2014-12-12 23:47:33 |
|
[941] Kovács 972 Márton | 2014-12-12 23:47:33 |
 Kedves fórumosok!
B.4660 megoldásához tudna valaki ötletet adni? Nem sikerült vele dűlőre jutni, még csak részeredményem sincs.
Egyelőre csak ötletet szeretnék, ha úgysem megy, akkor a megoldásra is kíváncsi leszek.
Köszönöm előre is!
|
|
[940] w | 2014-12-12 19:43:25 |
 A.627. feladatra megjelent a hivatalos megoldás. Leírok egy másik megközelítést (vázlatos lesz).
A hiv. megoldás jelöléseivel élve, legyen &tex;\displaystyle t_n&xet; a Csebisev-polinom megfelelő transzformáltja és &tex;\displaystyle 1=a_0>a_1>\dots>a_n=0&xet; az extremális helyei, továbbá &tex;\displaystyle d=\frac1{2^{2n-1}}&xet;. Tudjuk, hogy &tex;\displaystyle t_n(a_j)=(-1)^j\cdot d&xet;.
Tegyük fel indirekt, hogy &tex;\displaystyle \max_{[0,1]}|f-p|&xet; valamely &tex;\displaystyle f,p&xet; párra kisebb, mint &tex;\displaystyle d&xet;. Legyen &tex;\displaystyle q(x)=-p(x)-t_n(x)+x^n&xet; egy &tex;\displaystyle n&xet;-nél kisebb fokú polinom, akkor
&tex;\displaystyle f(x)-p(x)=f(x)+q(x)-x^n+t_n(x)&xet; | (1) |
alakú.
Felhasználva az indirekt feltevést: &tex;\displaystyle f(a_j)-p(a_j)<d=t_n(a_j)&xet; páros &tex;\displaystyle j&xet;-kre és &tex;\displaystyle f(a_j)-p(a_j)>-d=t_n(a_j)&xet; páratlan &tex;\displaystyle j&xet;-kre, vagyis
&tex;\displaystyle (-1)^{j-1}[f(a_j)-p(a_j)-t_n(a_j)]>0.&xet;
Ebbe (1)-et beírva:
&tex;\displaystyle (-1)^{j-1}q(a_j)>(-1)^{j-1}[x^n-f(a_j)].&xet;
Írjuk fel a Lagrange-féle interpolációs képletet &tex;\displaystyle q(x)&xet;-re és az &tex;\displaystyle (a_j,q(a_j))&xet; pontokra &tex;\displaystyle j=1,2,\dots,n&xet;-re. Ebből kiderül, hogy
&tex;\displaystyle 0>q(a_0)=q(1)=\sum_{j=1}^n q(a_j)\prod_{i\neq j}\frac{1-a_i}{a_j-a_i}>&xet;
&tex;\displaystyle >\sum_{j=1}^n [a_j^n-f(a_j)]\prod_{i\neq j}\frac{1-a_i}{a_j-a_i}=:S.&xet; | (2) |
Szeretnénk belátni, hogy &tex;\displaystyle S\ge 0&xet;, akkor ellentmondást kapunk. Világos, hogy ehhez elég belátni, hogy bármely &tex;\displaystyle k&xet; pozitív egész kitevőre
&tex;\displaystyle 0\le S_k=\sum_{j=1}^n (a_j^k-a_j^{k+1})\prod_{i\neq j}\frac{1-a_i}{a_j-a_i}=&xet;
&tex;\displaystyle =\left[\prod_{i=1}^n (1-a_i)\right]\cdot \sum_{j=1}^n \frac{a_j^k}{\prod_{i\neq j}(a_j-a_i)}=&xet;
&tex;\displaystyle =\prod_{i=1}^n (1-a_i)\cdot X^k[a_1,a_2,\dots,a_n].&xet; | (3) |
Például az osztott differenciák középértéktételéből, vagy a hivatalos megoldásbeli &tex;\displaystyle (2)&xet; azonosságból következik, hogy utóbbi mennyiség nemnegatív. Ez adja az ellentmondást.
A megoldás átgondolásával jól leolvasható az egyenlőség esete is (de végül is ezt a feladat nem kérte). Ha az infimum &tex;\displaystyle d&xet;, akkor &tex;\displaystyle (2)&xet;-ben egyenlőség is megengedhető, ám &tex;\displaystyle k\ge n\ge 2&xet; esetén &tex;\displaystyle S_k&xet; pozitív, így &tex;\displaystyle f(x)\neq x^n&xet;-re &tex;\displaystyle S&xet; is pozitív lesz. Vagyis &tex;\displaystyle n\ge 2&xet;-re csak &tex;\displaystyle f(x)=x^n&xet; lehet, &tex;\displaystyle n=1&xet;-re pedig triviális a feladat.
|
|