Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Lejárt határidejű KÖMAL feladatokról

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]  

Szeretnél hozzászólni? Jelentkezz be.
[983] S:R.2015-05-25 14:04:13

Igazad van, eleinte különböző szögeket vettem mindenhol, aztán jutott eszembe a lent írt gondolat, de ezek szerint nem véletlenül írtam fel először különbözőkkel :D Valóban, így viszont már jóval nehezebb bármit is kezdeni ezzel az ötlettel(bár a bal oldali kifejezések még így is elég szimpatikusak lehetnek)

Előzmény: [982] nadorp, 2015-05-25 13:18:36
[982] nadorp2015-05-25 13:18:36

... legyenek a páratlan indexű tagok egy szög szinuszai, a következő tag pedig ugyanannak a szögnek a koszinuszai...

Ez hibás kiindulás, ugyanis a feltételek nem garantálják, hogy pld. &tex;\displaystyle x_1^2+x_2^2=1&xet;.

Előzmény: [981] S:R., 2015-05-25 12:33:31
[981] S:R.2015-05-25 12:33:31

A B4703. feladattal kapcsolatban gondolkoztam egy olyan megoldáson, ami trigonometrikus helyettesítést használ. Mivel minden xi-re fennáll -1<=xi<=1, ezért legyenek a páratlan indexű tagok egy szög szinuszai, a következő tag pedig ugyanannak a szögnek a koszinuszai. Ekkor a bal oldali gyökös kifejezésekben ki lehet használni a trigonometrikus Pit. tételt, és az adott oldalon ugyanazoknak a szögeknek a szinuszainak és koszinuszainak abszolútértéke marad 3mal szorozva, ill. lesz egy szög, aminek csak a szinusza áll majd a bal oldalon egy 3s szorzóval. A jobb oldalon marad 3 olyan tag, amelynek minimuma gyök7, illetve 3, aminek minimuma gyök5. Sajnos ezek a becslések elég durvák, és nem is használtuk ki, hogy a 6 tag összege 0. Viszont nem sok hiányzik hozzá, szerintem egy kis finomítással lehetne értelme egy ilyen bizonyításnak. Ötletek?

[980] nadorp2015-05-25 12:07:34

A643-ra létezik olyan megoldás, amelyik nem azt használja ki, hogy végtelen sok &tex;\displaystyle n^2+1&xet; alakú prím létezik?

[979] csábos2015-05-23 16:48:07

Vegyük észre, hogy

&tex;\displaystyle (n+1)A^2B+(n-2)B^2 -A^4-(2n-2)AC= 2\sum_{i,j,k}(x_ix_j-x_ix_k)^2+2\sum_{i,j,k,t}x_jx_k(x_i-x_t)^2&xet;

A kérdés persze az, hogy ezt hogy vesszük észre. Először is kivonjuk a baloldalt, majd kiszámoljuk, hogy pont mennyi a különbség. Erre az adódik, hogy

&tex;\displaystyle (4n-8)\sum x_i^2x_j^2+(2n-10)\sum x_i^2x_jx_k-12\sum x_ix_jx_kx_t.&xet;

Én úgy szoktam kiszámolni, hogy készítek egy táblázatot, amely sorai a homogén negyedfokú monomok: &tex;\displaystyle x_i^4, x_i^3x_j, x_i^2x_j^2, x_i^2x_jx_k,x_ix_jx_kx_t &xet;, oszlopai a kifejezéseim, és mindnhova beírom, hogy miből mennyi van. A szimmetria miatt megúsztam az egészet egy 5-ször 4-es táblázattal. Utána összeadom az oszlopokat, és megvan a különbség.

Bátorítólag hat rám, hogy az &tex;\displaystyle x_i^4&xet;-es és az &tex;\displaystyle x_i^3x_j&xet;-s tagok kiestek.

Most tudom, hogy a feladat nemnegatív valós számokról szól, ezért ha minden &tex;\displaystyle x_i&xet; helyébe &tex;\displaystyle x_i^2&xet;-et írok, akkor egy olyan egyenlőtlenséget kapok, ami már minden valós számra igaz. Most, Hilbert tétele alapján, ez a polinom (amennyiben tényleg pozitív mindenütt) előáll racionális törtfüggvények négyzeteinek összegeként. Én persze reménykedem, hogy előáll polinomok négyzetösszegeként is. Ilyenkor van biztos módszer, a szisztematikus teljes négyzetté alakítás MINDIG működik. A konkrét esetben a polinom olyannyira szimmertrikus, hogy megpróbálom szimmetrikus módon előállítani négyzetösszegként. A első próbálkozás bejött.

Ha valaki szeretné látni, hogy hogyan lehet megkeresni a legkevesebb négyzetösszeggé való alakítást, az találhat rá EGY módszert itt:

http://www.math.uiuc.edu/ reznick/quartic.pdf

Aki ellenpéldát szeretne arra, hogy hogyan néz ki egy polinom, ami mindig pozitív, de nem polinomok, hanem csak racionális törtfüggvények négyzetösszege, annak íme:

http://www.math.uiuc.edu/documenta/vol-ismp/61_schmuedgen-konrad.pdf

Előzmény: [978] emm, 2015-05-22 06:24:00
[978] emm2015-05-22 06:24:00

Jogos, annyi módosítás kell, hogy legyen &tex;\displaystyle k&xet; a &tex;\displaystyle 0&xet; változók száma, &tex;\displaystyle n=n_1+k&xet;, és a szimmetrikus részt csak a pozitívakra definiáljuk, mert a &tex;\displaystyle 0&xet;-s tényezős tagok úgyis kiesnek. Kell:

&tex;\displaystyle -A^4+A^2 B (k+n_1+1)-2 A C (k+n_1-1)+B^2 (k+n_1-2)\geq 0&xet;

Módosításokkal átrendezve:

&tex;\displaystyle (n-1) n^2 \left((n_1-1)(k+n_1-2) \sigma_{n_1,2}^2-(n_1-2)(k+n_1-1) \sigma_{n_1,1}\sigma_{n_1,3}\right)\geq 0&xet;

És &tex;\displaystyle (n_1-1) (k+n_1-2)-(n_1-2) (k+n_1-1)=k&xet; miatt Newtonnal kész. (ettől csak gyengébb lett)

Előzmény: [975] Fálesz Mihály, 2015-05-21 16:59:15
[977] w2015-05-21 22:15:14

A B4703 szövege így kezdődik: Tegyük föl, hogy az &tex;\displaystyle x_1,x_2,x_3,x_4,x_5,x_6&xet; számok abszolút értéke legfeljebb 1, összegük pedig 0.

Az eredeti javaslatom pontosan ugyanez a feladat volt, csak úgy, hogy ennek a mondatnak a helyén a következő mondat volt: Tegyük föl, hogy az &tex;\displaystyle x_1,x_2,x_3,x_4,x_5&xet; számok abszolút értéke legfeljebb &tex;\displaystyle 1&xet;, összegük pedig &tex;\displaystyle 0&xet;, és legyen &tex;\displaystyle x_6=x_1&xet;.

A Szerkesztőség úgy fest, az eredeti kitűzést túl könnyűnek ítélte (amúgy tényleg kedves, egyszerű), és csavart rajta, nem is keveset. Vagy elszúrták a kitűzést és mivel így is igaz volt, nem volt kedvük vele törődni. Mindenesetre állítólag így is igaz.

Sokat dolgoztam azon, hogy legalább én megoldjam azt a feladatot, amihez a nevem van odaírva, de végül csak abban az esetben sikerült belátnom, hogy &tex;\displaystyle \sqrt{1-a_1^2}\le 4\sqrt 2-4\sqrt 3+\sqrt 5\approx 0,9647&xet;.

Előzmény: [976] rizsesz, 2015-05-21 21:20:58
[976] rizsesz2015-05-21 21:20:58

A B.4703-et hogyan sikerult igy?

Előzmény: [972] w, 2015-05-12 20:28:50
[975] Fálesz Mihály2015-05-21 16:59:15

Egy zavaró körülmény: az A. 642.-ben akkor is egyenlőség van, ha &tex;\displaystyle x_1=1&xet; és &tex;\displaystyle x_2=\dots=x_n=0&xet;.

A belinkelt oldal hibás. Ha a változók között szerepel a &tex;\displaystyle 0&xet;, akkor nem tudjuk elérni, hogy a szorzat &tex;\displaystyle 1&xet; legyen.

A Wikipedia oldal még rosszabb...

Előzmény: [974] emm, 2015-05-20 19:40:34
[974] emm2015-05-20 19:40:34

A.642

&tex;\displaystyle \sigma_{n,k}:=\binom{n}{k}^{-1}\sum_{1\leq i_1<...<i_k\leq n} \prod_{r=1}^k x_{i_r} &xet;

&tex;\displaystyle n&xet; elemhez tartozó &tex;\displaystyle k&xet;-adrendű normált szimmetrikus polinomok. Ekkor:

&tex;\displaystyle A=n\sigma_{n,1}\qquad B=n^2\sigma_{n,1}^2-n(n-1)\sigma_{n,2}\qquad C=n^3\sigma_{n,1}^3-\frac{3}{2}n^2(n-1)\sigma_{n,1}\sigma_{n,2}+\frac{1}{2}n(n-1)(n-2)\sigma_{n,3} &xet;

Azt kell belátnunk tehát, hogy:

&tex;\displaystyle (n+1)A^2B+(n-2)B^2\geq A^4+2(n-1)AC&xet;

&tex;\displaystyle (n+1)\left(n\sigma_{n,1}\right)^2\left(n^2\sigma_{n,1}^2-n(n-1)\sigma_{n,2}\right)+(n-2)\left(n^2\sigma_{n,1}^2-n(n-1)\sigma_{n,2}\right)^2\geq\left(n\sigma_{n,1}\right)^4+(n-1)\left(2n^3\sigma_{n,1}^3-3n^2(n-1)\sigma_{n,1}\sigma_{n,2}+n(n-1)(n-2)\sigma_{n,3}\right)&xet;

Kibontva és átrendezve:

&tex;\displaystyle n^5 \sigma_{n,2}^2-n^5 \sigma_{n,1} \sigma_{n,3}-4 n^4 \sigma_{n,2}^2+4 n^4 \sigma_{n,1} \sigma_{n,3}+5 n^3 \sigma_{n,2}^2-5 n^3 \sigma_{n,1} \sigma_{n,3}-2 n^2 \sigma_{n,2}^2+2 n^2 \sigma_{n,1}\sigma_{n,3}\geq 0 &xet;

És szorzattá alakítva:

&tex;\displaystyle (n-2) (n-1)^2 n^2 \left(\sigma_{n,2}^2-\sigma_{n,1} \sigma_{n,3}\right)\geq 0&xet;

Viszont ez éppen a Newton-féle egyenlőtlenség: &tex;\displaystyle \sigma_{n,k}^2\geq \sigma_{n,k-1}\sigma_{n,k+1}&xet; miatt igaz (bizonyítást elemien lásd a Sklarszkij-Jaglom-Csencov könyvben, analízist használva itt) , egyenlőség csak akkor áll, ha &tex;\displaystyle x_1=x_2=...=x_n&xet;.

[973] Nagypapa2015-05-12 20:33:49

"Mondjuk a B4694-es olyan ocsmány volt, hogy semmi kedvem volt vele már órákat vesződni,......."

Pont Rád gondoltam, nézvén a pontszámaidat :)

Előzmény: [972] w, 2015-05-12 20:28:50
[972] w2015-05-12 20:28:50

Általában a B-feladatok nehézségi sorrendje egy hónapon belül nem követi a pontértéksorrendet. Ebben szerintem benne lehet, hogy a szerkesztők mást ítélnek könnyű vagy nehéz feladatnak, mint a megoldók, vagy nagyobb eséllyel az, hogy néhány könnyebb feladatnak nagyobb pontértéket adván juttat versenyzőket sikerélményhez, ami kedvet ad arra, hogy foglalkozzanak a nehezebb feladatokkal is.

Mondjuk a B4694-es olyan ocsmány volt, hogy semmi kedvem volt vele már órákat vesződni, míg végigmennek a számítások. Azért valaki írhatna megoldást. Érdekességnek mondjuk jó volt kitűzni. Tehát személyesen örültem, hogy a hónapban nem volt a 6 legtöbb pontot érő feladatban.

Előzmény: [971] Nagypapa, 2015-05-12 19:52:46
[971] Nagypapa2015-05-12 19:52:46

Mi a véleményetek a B. 4711. feladat pontozásáról (5pont)?

Egyszerű számolással látható, hogyha x+y=1, akkor f(x)+f(y)=1, így a kérdéses összeg elejéről-hátuljáról párosítva az összeadandókat, az eredmény 1008.

Eközben a B.4694. feladat csupán 4 pontot ér és a beérkezett/4 pontos megoldások aránya 15/2 a statisztika alapján.

[970] Sinobi2015-04-12 20:14:51

Vagy: a gömb középpontjából vetítünk egy, vele párhuzamos síkra, és akkor azt kapjuk hogy van egy kör. őt érintő négy egyenes, meg mondjuk ezek metszései valahogy. A szög változása a kör sugarának változásának felel meg, az érintőegyenesek irányai maradnak. De a nagyítás az euklideszi sík egy hasonlósága, mindent megtart.

=> akárhány félegyenes akármilyen illeszkedésrendszere esetén igaz lesz, hogy a kapott sík metszése az alapsíkkal nem függ a forgatás &tex;\displaystyle \varphi&xet; szögétől.

Előzmény: [908] Fálesz Mihály, 2014-07-21 13:51:23
[969] w2015-04-12 20:09:12

B.4698. megoldása: először is ha &tex;\displaystyle H^*_n&xet; jelöli az &tex;\displaystyle \frac1n,\frac2n,\dots,\frac nn&xet; törtek halmazát, akkor jól láthatóan &tex;\displaystyle |H^*_n|=n&xet; és &tex;\displaystyle H^*_n\cap H^*_k=H^*_{(n,k)}&xet;. Ha pedig &tex;\displaystyle f&xet; bijekció a racionális számok és pozitív egészek között, akkor &tex;\displaystyle H_n&xet; halmazok, mint &tex;\displaystyle H^*_n&xet; képei &tex;\displaystyle f&xet; után, meg fognak felelni.

[968] Róbert Gida2015-03-21 21:44:20

Közölt a635. megoldásánál jónéhány helyen &tex;\displaystyle \sigma (\varphi(n))&xet; szerepel &tex;\displaystyle \varphi (\sigma (n))&xet; helyett

Egyébként felcserélve elég érdektelen lett volna a feladat: legyen &tex;\displaystyle n=p=k*T!+1&xet; alakú prím (Dirichlet tétele miatt lesz ilyen prím), és ez jó lesz, ha &tex;\displaystyle T&xet;-t elég nagynak választjuk.

[967] w2015-03-08 21:26:06

Gondolom azt a jól bevált módszert használod, hogy rekurzívan megjelölöd a nyerő és vesztő helyzeteket. Csinálj egy jó nagy ilyen (k,n)-es táblázatot (mondjuk 20x25-öst), mely mezőibe beírod, hogy nyerő vagy vesztő. Majd pedig keress mintát. (A játékok gyakran szeretik a kettes számrendszert. A minta csak kicsit bonyolult.)

Előzmény: [966] Bátki Zsolt, 2015-03-08 10:28:41
[966] Bátki Zsolt2015-03-08 10:28:41

A. 620. Artúrnak és Benőnek van egy k×n-es csokoládéja, ezzel a következő játékot játsszák. Felváltva esznek egy-egy darabot a csokoládéból, Artúr kezd. Minden lépésben a soron következő játékos a vonalak mentén két kisebb téglalap alakú darabra töri szét a csokoládét, és megeszi a kisebbik darabot. (Ha történetesen a két darab ugyanakkora, akkor szabadon választhat, hogy melyiket eszi meg.) Aki először eszik valamelyik lépésben egyetlen csokoládékockát, veszít, a másik játékos nyer.

Határozzuk meg mindazokat a (k,n) párokat, amikre Artúrnak van nyerő stratégiája.

1xn,2xn,3xn...7xn-re van vélhetően jó megoldásom.

Általános kxn-re nekem nem jött össze. Aki tudja írja meg!

A lap hivatalos megoldásában, csak a megoldók neve szerepel. A megoldás nem.

[965] w2015-02-12 10:00:02

Én is így indultam ki (nagyjából). Megjegyzem, ehhez hasonló módszerrel ki is jön a &tex;\displaystyle k=2,3&xet; eset (&tex;\displaystyle n^{k-\epsilon}&xet;-nal), hiszen akkor

&tex;\displaystyle [a,b]=\frac{ab}{(a,b)},\qquad [a,b,c]\ge \frac{abc}{(a,b)(b,c)(c,a)}.&xet;

(Ezeknek azt hiszem, annyi a jelentősége, hogy legfeljebb &tex;\displaystyle k&xet; tényezővel kell visszaosztani. De most már nem emlékszem pontosan a kezdő kísérletekre, ha érdekel valakit, megpróbálom kifejteni. Egyébként kicsit gyanús volt, hogy pont már &tex;\displaystyle k=4&xet;-re nem működik ez a módszer.)

Előzmény: [964] Róbert Gida, 2015-02-12 07:38:19
[964] Róbert Gida2015-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
[963] Róbert Gida2015-02-12 07:38:10

Ügyes vagy, [-1,1]-en értelmezett fv-nek olvastam.

Előzmény: [961] Fálesz Mihály, 2015-02-11 22:27:51
[962] Fálesz Mihály2015-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
[961] Fálesz Mihály2015-02-11 22:27:51

Az &tex;\displaystyle x^2&xet; mint korlátos függvény? :-o

Előzmény: [958] Róbert Gida, 2015-02-11 20:41:00
[960] w2015-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 Gida2015-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.

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]