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: "ujjgyakorlatok"

  [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]  

Szeretnél hozzászólni? Jelentkezz be.
[478] Ali2005-11-25 11:52:21

Megoldás 78. -ra:

x0=0 és x_{n+1}=\sqrt{a+x_n}.

a.) x_n < \frac{1}{2} + \sqrt{a + \frac{1}{4}} teljes indukcióval igazolható. x_1 = \sqrt a -ra igaz. Tfh n-re igaz. x_{n+1} = \sqrt{a+x_n} < \frac{1}{2} + \sqrt{a + \frac{1}{4}} -t kell igazolni. Négyzetreemelés és rendezés után pontosan az x_n < \frac{1}{2} + \sqrt{a + \frac{1}{4}} egyenlőtlenséget kapjuk, amely az indukciós feltevés miatt teljesül.

Továbbá xn monoton növő, ugyanis

x_{n+1} = \sqrt{a+x_n} > x_n \qquad a+x_n > x_n^2 \qquad x_n^2 - x_n - a < 0

kellene, ami teljesül is, mivel xn az x2-x-a=0 egyenlet gyökei között van: \frac{1}{2} - \sqrt{a + \frac{1}{4}} < 0 < x_n < \frac{1}{2} + \sqrt{a + \frac{1}{4}}

Egy monoton növő felülről korlátos sorozatnak létezik határértéke, esetünkben ez az x = \sqrt{a+x} egyenlet pozitív gyöke. \lim_{n\to\infty} x_n = A = \frac{1}{2} + \sqrt{a + \frac{1}{4}} > 1

b.) Teljes indukcióval igazoljuk, hogy x_k > A - \frac{1}{A^{k-1}} , k>0. Ez k=1 -re igaz, mert

x_1 = \sqrt a > A - \frac{1}{A^0} = \frac{1}{2} + \sqrt{a + \frac{1}{4}} - 1, \qquad \sqrt a + \frac{1}{2}> \sqrt{a + \frac{1}{4}} \qquad triv.

Tfh k -ra igaz.

x_{k+1} = \sqrt {a+x_k} > A - \frac{1}{A^k}

a+x_k > A^2-\frac{2}{A^{k-1}}+\frac{1}{A^{2k}}=A+a-\frac{2}{A^{k-1}}+\frac{1}{A^{2k}}

x_k>A-\frac{1}{A^{k-1}}-\left(\frac{1}{A^{k-1}}-\frac{1}{A^{2k}}\right)

teljesül egyrészt az indukciós feltevés , másrészt a zárójelben levő kifejezés pozitív volta miatt.

Legyen 1>\varepsilon>0 és k olyan, hogy  \frac{1}{A^{k-1}}>\varepsilon\geq\frac{1}{A^k}. Ilyen k létezik. Ekkor n\geq \frac{\ln(\frac{A}{\varepsilon})}{\ln A}>\frac{\ln(AA^{k-1})}{\ln A}=k

n>k miatt n\geqk+1 és A>x_n\geq x_{k+1}>A-\frac{1}{A^k}\geq A-\varepsilon. Ezért |A-xn|<\varepsilon

c.) Megmutatjuk teljes indukcióval, hogy x_k<A-\frac{A}{(2A)^k}. Ez k=1 -re jó, mert

x_1=\sqrt a < A-\frac{1}{2},\qquad \sqrt a +\frac{1}{2}<A=\frac{1}{2}+\sqrt{a+\frac{1}{4}}

Tfh k -ra igaz,ekkor

x_{k+1}=\sqrt{a+x_k}<A-\frac{A}{(2A)^{k+1}} \qquad kellene

a+x_k<A^2-\frac{2A^2}{(2A)^{k+1}}+\frac{A^2}{(2A)^{2k+2}}=A+a-\frac{2A^2}{(2A)^{k+1}}+\frac{A^2}{(2A)^{2k+2}}

x_k<A-\frac{A}{(2A)^k}+\frac{A^2}{(2A)^{2k+2}}

teljesül az indukciós feltevés miatt.

Legyen 1>\varepsilon>0 és k olyan, hogy  \frac{A}{(2A)^k}\geq\varepsilon>\frac{A}{(2A)^{k+1}}. Ilyen k létezik. Ekkor n\leq \frac{\ln(\frac{A}{\varepsilon})}{\ln 2A}<\frac{\ln(A\frac{(2A)^{k+1}}{A})}{\ln 2A}=k+1.

Tehát n<k+1 \to n\leq k \to x_n \leq x_k < A-\frac{A}{(2A)^k} \le A-\varepsilon \to x_n<A-\varepsilon \to |A-x_n|>\varepsilon

Előzmény: [396] Lóczi Lajos, 2005-10-30 20:46:24
[477] Ali2005-11-22 10:33:55

Nagyjából így: Ha a p_{n+1}=\frac{1}{2}\left(p_n+\frac{a}{p_n}\right) rekurzióban a p_n = r_n \sqrt a helyettesítést alkalmazzuk, akkor az r_{n+1}=\frac{1}{2}\left(r_n+\frac{1}{r_n}\right) = \frac{1}{\frac{2r_n}{1+(r_n)^2}} rekurzióhoz jutunk. A tg(2x) kifejtése hasonlít a nevezőhöz, csak éppen '-' -al. Melyik lehet az az f fv, melyre f(2x) kifejtésében '+' van ? A th(x).

Előzmény: [476] Lóczi Lajos, 2005-11-21 20:45:01
[476] Lóczi Lajos2005-11-21 20:45:01

Szép. Nagyon kíváncsi vagyok, hogyan jöttél rá (én eredetileg okos számítógép segítségével). De persze utólag meg lehet találni az explicit képletet, l. pl.

http://mathworld.wolfram.com/NewtonsIteration.html

Azt írja: "has the clever closed-form solution..."

Itt "area tangens hiperbolikusszal" van megadva, de ez, mint tudjuk, kifejezhető a logaritmussal.

Előzmény: [473] Ali, 2005-11-21 15:54:56
[475] Lóczi Lajos2005-11-21 20:37:48

Így is sejtettem (én is ezekre a konklúziókra jutottam a Mathematicával kapcsolatban legalábbis).

Előzmény: [474] Róbert Gida, 2005-11-21 17:05:43
[474] Róbert Gida2005-11-21 17:05:43

Maple 9.5 és Mathematica 5.1 sem tudja kiszámolni!!! Stirling formulából adódik, hogy 4>n!*e^n*n^{-n-\frac 12}>1 ha n nagy. Így írhatjuk, hogy az eredeti sor pontosan akkor konvergens, ha \sum _{n=2}^{\infty} \frac 1{n\ln  n} konvergens, viszont ez utóbbi sorról integrálközelítő összegekkel ismert, hogy divergens, így az eredeti sor is az.

Érdekes, de még ez utóbbi sorról sem tudja a Mathematica, hogy divergens, így ez a fő oka, hogy nem tudja kiszámolni. Kipróbáltam a Stirling formulát ismeri, tehát el tud elvileg jutni a mi összegünkig, de tovább nem. Ekkor próbáltam ki, hogy mit ad a primek reciprokösszegére és ez a megdöbbentő, hogy ezt sem ismeri, aminek most talán nem az az oka, hogy ezt a sorösszeget nem ismeri, hanem az, hogy idáig el sem tud jutni!!! mert nem ismeri azt az alapvető formulát, hogy \lim_{n\to\infty} \frac {p_n}{n*\ln n}=1 teljesül, ahol pn az n-edik prím ( ez egyébként a prímszámtételből adódik ). Bár ismert persze elemi bizonyítás a prímek reciprokösszegének a divergenciájára Erdős Páltól például.

Előzmény: [471] Lóczi Lajos, 2005-11-21 14:32:42
[473] Ali2005-11-21 15:54:56

Érdekes, nem engedett többet beírni...

akkor folytatva qn+1=2qn=2n+1q0 , n\ge0. qn -t kifejezve pn segítségével,

q_n = \frac{1}{2}ln\frac{p_n+\sqrt a}{p_n-\sqrt a}=2^{n-1}ln\frac{p_0+\sqrt a}{p_0-\sqrt a}

Ebből

p_n = \sqrt a \cdot\frac{(p_0+\sqrt a)^{2^n} + (p_0-\sqrt a)^{2^n}}{(p_0+\sqrt a)^{2^n} - (p_0-\sqrt a)^{2^n}}

Előzmény: [472] Ali, 2005-11-21 15:54:11
[472] Ali2005-11-21 15:54:11

Megoldás a 79. feladatra:

p_{n+1}=\frac{1}{2}\left(p_n+\frac{a}{p_n}\right) \qquad ,a>0

a.) eset: p0>0

\left(\sqrt{p_n} - \sqrt{\frac{a}{p_n}}\right)^2 \ge 0 \quad miatt \quad p_{n+1}=\frac{1}{2}\left(p_n+\frac{a}{p_n}\right) \ge \sqrt a \quad ,n\ge 0

pn monoton fogyó, ugyanis n\ge1 esetén p_{n} \ge \sqrt a miatt

p_{n+1}=\frac{1}{2}\left(p_n+\frac{a}{p_n}\right) \le p_n

Egy monoton fogyó alulról korlátos sorozatnak létezik határértéke, esetünkben az

x = \frac{1}{2} \left(x + \frac{a}{x} \right)

egyenlet pozitív gyöke. Ezért \lim_{n\to\infty} p_n = \sqrt a

c.) eset: p0<0. ekkor pn monoton növő -\sqrt a -hoz konvergáló sorozat.

b.) eset: p2005=? Tfh a>0 és p_0 > \sqrt a és legyen p_n = \frac{\sqrt a}{\th q_n} ,

ahol \th x =\frac{e^x - e^{-x}}{e^x + e^{-x}}

\frac{1}{\th 2x} = \frac{1}{2}\left(\th x + \frac{1}{\th x}\right) és a rekurzív összefüggés miatt \frac{1}{\th q_{n+1}} = \frac{1}{2}\left(\th q_n + \frac{1}{\th q_n}\right) = \frac{1}{\th2q_n}

Előzmény: [397] Lóczi Lajos, 2005-10-30 21:09:38
[471] Lóczi Lajos2005-11-21 14:32:42

Kíváncsi vagyok, hogy a matematikai programcsomagok hogyan reagálnának arra, ha megkérdeznék tőlük, mennyi a


\sum _{n=2005}^{\infty } \frac{e^n n^{-n-\frac{3}{2}}
   n!}{\log_2 n}

összeg értéke. És szerintünk mennyi?

[470] Róbert Gida2005-11-18 00:47:56

94. feladat

Egy nxn-es mátrixot nevezzünk k-büvős négyzetnek, ha elemei pontosan az 1,2,3,...,n2 számok továbbá teljesül minden 1\leqd\leqk-ra, hogy minden sorban, minden oszlopban és a két átlóban az elemek d-edik hatványösszege ugyanaz. Bizonyítsuk be ,hogy (4p+2)x(4p+2)-es k-büvős négyzet nem létezik, ha k\geq3 ( itt p egész ).

[469] Lóczi Lajos2005-11-17 22:26:32

Köszönöm az érdekes fejleményeket az ügyben (és hogy vetted a fáradságot bepötyögni a mátrixokat :)

(Én kb. 2000-ben foglalkoztam ezzel a kérdéssel (lám, azóta sokminden felkerült az internetre...) és emlékszem, többszáz CPU-órát használtam fel. A 40800 ezek szerint a 4x4-es maximum, én is azt sejtettem, most már beugrott a szám. Láttam, hogy a 7x7-es eset alsó becslésével Pfoertner több, mint 2 évet számolt :-) )

A legérdekesebb, hogy ezek szerint nem mindig akkor adódik a maximális determináns, ha a főátlóban vannak a legnagyobb elemek.

Előzmény: [467] Róbert Gida, 2005-11-17 21:10:06
[468] Róbert Gida2005-11-17 21:17:16

93. feladat

Egy nxn-es komplex elemű mátrix determinánsának kifejtésénél azt a meglepő dolgot tapasztaltuk, hogy mind az n! tag valós része pozitív. Milyen n-re lehetséges ez?

[467] Róbert Gida2005-11-17 21:10:06

Legyen x(n) a maximális determináns az nxn-es mátrixok közt, melynek elemei pontosan az 1,2,..,n2 számok. Triviálisan x(1)=1 és x(2)=10 ( főátlóban 4 és 3 ). Megoldásom szerint x(3)=412 Ekkor Sloane adatbázisában az 1,10,412 sorozatra rákeresve egyetlen találatot ad, a miénket! Ez az A085000 sorozat: http://www.research.att.com/projects/OEIS?Anum=A085000 Még állítólag 3 tag ismert a sorozatból!

x(4)=40800, mátrixot nem ad meg hozzá.

x(5)=6839492 mátrixot is ad hozzá:

A=\left(\matrix {25&15&9& 11 &4\cr 7& 24& 14& 3& 17 \cr 6& 12& 23& 20& 5\cr 10& 13& 2& 22& 19\cr 16& 1&18& 8& 21 \cr}\right)

x(6)=1865999570 ehhez is ad mátrixot:

B=\left(\matrix {36& 24& 21& 17& 5& 8\cr 3& 35& 25& 15& 23& 11\cr 13& 7& 34& 16& 10& 31\cr 14& 22& 2& 33& 12& 28 \cr 20& 4& 19& 29& 32& 6\cr 26& 18& 9& 1& 30& 27\cr}\right)

Alsó becslések ( Hugo Pfoertner ): x(7)\geq762140212575 és x(8)\geq440857916120379, x(7)-re ez már jobb becslés, mint amit Sloane-nál találhatunk, ez a http://www.recmath.org-on található. Itt éppen a te problémád egy javasolt programozási versenyfeladat, hogy minnél jobb becslést találjunk x(n) sorozatra. Nagyon kevés nyílt programozási verseny van a weben, jó ha 2. Ezek közül az egyik a híres Al Zimmermann prog. verseny: évente van 3-4 feladat és nagyon nagy dolognak számít ezen nyerni. Jelenleg is tart egy verseny: cél az 1,2,3,...,n sugarú körök bepakolása egy minimális sugarú körbe, hogy a körök diszjunktak legyenek. Ez a feladat 5\leqn\leq50-re.

Előzmény: [464] Lóczi Lajos, 2005-11-17 19:10:22
[466] Káli gúla2005-11-17 20:21:54

Igazad van, bár csupa negatív tagnál felcserélhetnénk két sort, és akkor csupa pozitív tagot kapnánk.

Egy újj gyakorlat. 92. feladat. A két és háromdimenziós kockának van egy érdekes tulajdonsága: ha a csúcsokat valahogy két azonos elemszámú részre bontjuk (elfelezzük), akkor a két ponthalmaz egybevágó lesz. Megvan-e ez a tulajdonsága a négydimenziós kockának is?

Előzmény: [462] Róbert Gida, 2005-11-17 18:24:53
[465] Róbert Gida2005-11-17 19:15:26

Megoldás a 90. feladatra:

Ha A egy nxn-es mátrix, melynek minden eleme +-1, akkor a mátrix determinánsa osztható 2n-1-gyel. Ez n=1-re trivi, indukcióval, ha n=k-ra igaz, akkor n=k+1-re is igaz. Induljunk a csupa 1 mátrixból, ennek sorai összefüggnek, így determinánsa nulla, egy-egy lépésben a mátrix egy elemét -1-re változtatva bármely mátrixot megkaphatunk. Egy lépésben a mátrix determinánsát kifejtve abban a sorban, ahol egy elemet megváltoztattunk: az eredeti determináns+-2*aldetermináns lesz az új determináns, de az aldetermináns az indukció miatt osztható 2k-2-vel, így a determináns 2k-1-gyel osztható marad. Ami kellett.

Ha n>1 akkor a 0 mindig lehet a determináns: legyen A csupa 1 mátrix. Elég pozitív determinánsokat előállítani, mivel a determináns előjelet vált, ha két oszlopát felcseréljük.

n=3-ra a determináns legfeljebb 6, mivel 6 darab kifejtési tag van. De a determináns osztható 4-gyel. Így csak -4,0,4 lehet, ezek közül mindegyik előáll, az előbbiek miatt elég 4-re előállítást mutatni: legyen

A=\left(\matrix{-1&1&1\cr  1&-1&1\cr 1&1&-1\cr}\right)

n=4-re 24 darab kifejtési tag van és a determináns osztható 8-cal, így csak -16,-8,0,8,16 lehet és mindegyik előáll, elég -8-ra és -16-ra példát mutatni: legyen

B=\left(\matrix{ -1&1&1&1\cr 1&-1&1&1 \cr 1&1&-1&1 \cr 1&1&1&-1 \cr}\right)

. Ekkor det(B)=-16 . Legyen

C=\left(\matrix{-1&-1&1&1 \cr 1&-1&1&1 \cr 1&1&-1&1 \cr 1&1&1&-1\cr}\right)

Ekkor det(C)=-8

[464] Lóczi Lajos2005-11-17 19:10:22

Régebben a 4x4-es analóg esetet is végigszámoltam, azzal a feltevéssel, hogy a főátlóban állnak a maximális elemek (tehát 16, 15, 14, 13). Aztán ha jól emlékszem valaki végigszámolta mindet és meghatároztuk a maximális elrendezést. Sajnos, nem látszott az általános minta. Milyen jó lenne látni pl. az 5x5-ös, stb. eseteket is... (tehát a mátrixot 1,2, ... , n2 számokkal feltöltve)

Aki ehhez hasonló problémákat akar keresgetni az interneten, az a Hadamard-féle maximális determinánsproblémára keressen pl. rá. Számos speciális alakú mátrix esetén ismert a maximum, de nem találtam eddig sehol eredményeket a fent feltett kérdésemre. Persze általánosabban is vizsgálható lenne a kérdés. Pl. egy ujjgyakorlat a következő:

Adott 4 valós szám. Mely elrendezés mellett lesz a belőlük képzett 2x2-es determináns abszolút értéke maximális?

Előzmény: [463] Róbert Gida, 2005-11-17 18:41:47
[463] Róbert Gida2005-11-17 18:41:47

Megoldás a 89. feladatra:

A minimum egyszerű, legyen ugyanis:

A=\left(\matrix {1&2&3 \cr 4&5&6 \cr 7&8&9 \cr } \right)

Ekkor A sorai lineárisan összefüggnek, így determinánsa nulla, így a minimum is nulla. A maximumra egy egyszerű program segítségével mind a 9! esetet végignézve ( persze lehetne kevesebbel is ), kapjuk, hogy a maximum 412 és ezt pl.

B=\left(\matrix {9&4&2 \cr 3&8&6 \cr 5&1&7 \cr}\right)

mátrixon vétetik fel. Egyébként nem véletlenül 412-öt is felveszi, mert ha -412 állna elő, akkor 2 oszlopát felcserélve a determináns ellentettjére vált.

[462] Róbert Gida2005-11-17 18:24:53

Valójában az indukció miatt az is kell, hogy pozítiv tag is van a kifejtési tagok közt. Amit persze ugyanúgy beláthatsz.

Megoldásom: n=3-ra szorozzuk össze a kifejtési tagokat, ekkor mivel a mátrix minden eleme két permutációban szerepel és a 6 féle permutáció közt 3 páros és 3 páratlan, ezért szorzatuk páratlan, így a kifejtési tagok szorzata - \prod _{i,j}{a_{i,j}}^2<0, de akkor a kifejtési tagok közt van pozitív és negatív is, ami kellett.

Előzmény: [456] Káli gúla, 2005-11-16 23:29:23
[461] Lóczi Lajos2005-11-17 14:13:01

Igen, ezért (is) érdekes az 1/2 !

(Csak az elütést teszem szóvá: 1+1/x-et gondoltál írni f definíciójában. - Javítottam - Sirpi)

Előzmény: [460] Ali, 2005-11-17 12:10:35
[460] Ali2005-11-17 12:10:35

f(x)=\left(1+\frac{1}{x}\right)^{x+\alpha}

f'(x)=\left(ln(1+\frac{1}{x})-\frac{\alpha}{x}-\frac{1-\alpha}{x+1}\right)\left(1+\frac{1}{x}\right)^{x+\alpha}

Jelölje g(x)=ln(1+\frac{1}{x})-\frac{\alpha}{x}-\frac{1-\alpha}{x+1}

g'(x)=\frac{\alpha}{x^{2}}+\frac{1-\alpha}{(x+1)^{2}}-\frac{1}{x(x+1)}=\frac{1}{x^{2}(x+1)^{2}}\left(\frac{1}{2}-(\frac{1}{2}-\alpha)(2x+1)\right)

További részletezés nélkül ebből már látszik, hogy miért is olyan érdekes az 1/2 :-)

Előzmény: [442] Ali, 2005-11-14 16:00:17
[459] Lóczi Lajos2005-11-16 23:53:33

90. feladat. Milyen értéket vehet fel egy 3x3-as mátrix determinánsa, ha minden mátrixelem (+1) vagy (-1)?

91. feladat. Mi a helyzet 4x4-es mátrix esetén?

[458] Lóczi Lajos2005-11-16 23:45:56

89. feladat. Mennyi lehet egy 3x3-as mátrix determinánsa abszolút értékének

a.) maximuma

b.) minimuma,

ha a mátrix elemei az 1, 2, 3,..., 9 számok (mindegyik pontosan egyszer)? Adjunk meg egy-egy extremális determinánsú elrendezést.

[457] Lóczi Lajos2005-11-16 23:39:47

88. feladat. Milyen \alpha\in[0,1] esetén lesz a [-1,1] intervallum komplementerén értelmezett x\mapsto \left(1+\frac{1}{x}\right)^{x+\alpha} függvény grafikonjának tükörszimmetriája?

[456] Káli gúla2005-11-16 23:29:23

Ha mínuszból páratlan sok van, akkor valamelyik pozitív együtthatós hármasban is páratlan sok mínusz van. Ha mínuszból páros sok van, akkor valamelyik negatív együtthatós hármasban is páros sok van.

Előzmény: [455] Róbert Gida, 2005-11-16 22:51:06
[455] Róbert Gida2005-11-16 22:51:06

Jó megoldás, először én is így csináltam n>3-ra, és n=3-ra végignéztem számítógéppel az 512 esetet, ez persze nem sok egy mai számítógéppel, kevesebb mint 1 másodperc alatt lefut. Aztán észrevettem egy számolás mentes bizonyítást n=3-ra! Mi lenne az?

Előzmény: [454] Lóczi Lajos, 2005-11-16 22:36:09
[454] Lóczi Lajos2005-11-16 22:36:09

Mivel csak az előjel számít, feltehető, hogy minden elem a mátrixban +1 vagy -1.

n=2-re lehet minden kifejtési tag pozitív, pl. a bal alsó sarokban -1, a többi +1.

n=3-ra összesen 29-féle \pm1 mátrix van, ezeket szisztematikusan végigvizsgálva 32-féle különböző "kifejtési tag 6-os" adódik, ám mindegyik tartalmaz legalább egy (-1)-est, ÉS +1-est, tehát a kívánt tulajdonságú 3x3-as mátrix már nincs.

És nincs n>3 esetén sem, mert -- pl. első sor szerint kifejtve -- a kifejtési tétel szerint ezt az nxn-es determinánst felírhatjuk n db (n-1)x(n-1)-es determináns előjeles összegeként, de akármelyik ilyen eggyel kisebb determináns kifejtésében lesz előjelváltás, tehát az eredeti nxn-es mátrix első sorát akárhogyan is választjuk meg \pm1-ek közül, az n db (n-1)! tagból álló kupac mindegyikében lesz előjelváltás.

Előzmény: [450] Róbert Gida, 2005-11-16 19:42:03

  [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]