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

A 2000 márciusi A-jelű matematika feladatok megoldása

A közöltek csak megoldásvázlatok, esetleg csak végeredmények. A maximális pontszám eléréséhez általában ennél részletesebb megoldás szükséges. A részletes megoldásokat a beküldött dolgozatok alapján a KöMaLban folyamatosan közöljük.


A. 233. Definiáljuk az (an) sorozatot a következőképpen: a0=a1=1, (n+3)an+1=(2n+3)an+3nan-1. Mutassuk meg, hogy a sorozat egész számokból áll.

Megoldásvázlat. A rekurzió alapján a sorozat első néhány eleme: a0=1, a1=1, a2=2, a3=4, a4=9, a5=21, a6=51, a7=127, a8=323, a9=835, a10=2188.

Bebizonyítjuk, hogy tetszőleges n nemnegatív egészre

(2)    an+2=an+1+akan-k.

Ebből a feladat állítása azonnal következik.

A (2) azonosság n8-ra leellenőrizhető a fenti adatok alapján, például n=4 esetén

a5+a0a4+a1a3+a2a2+a3a1+a4a0 = 21+1.9+1.4+2.2+4.1+9.1 = 51 = a6.

A (2) azonosságot n szerinti teljes indukcióval bizonyítjuk. Az n=0,1,2 esetekben behelyettesítéssel ellenőrizhető. Tegyük fel, hogy (2) igaz n<m-re, ahol m3; ebből bebizonyítjuk az n=m esetre is. Az indukciós feltevés és az (1) rekurzió többszöri felhasználásával

(m+4)(am+1+akam-k)=

=(m+4)am+1+(k+2)akam-k+(m-k+2)akam-k=

=(m+4)am+1+(2a0am+3a1am-1+((k+2)ak)am-k) +(ak((m-k+2)am-k)+3am-1a1+2ama0)=

=(m+4)am+1+4am+6am-1+((2k+1)ak-1+3(k-1)ak-2)am-k +ak((2m-2k+1)am-k-1+3(m-k-1)am-k-2)=

=(m+4)am+1+4am+6am-1+(2k+3)akam-1-k+3(k+1)akam-2-k +(2m-2k+1)akam-1-k+3(m-k-1)akam-2-k=

=(m+4)am+1+4am+6am-1 +((2m+4)akam-1-k-6a0am-1)+3makam-2-k=

=(m+4)am+1+4am+(2m+4)akam-1-k +3makam-2-k=

=(m+4)am+1+4am+(2m+4)(am+1-am)+3m(am-am-1)=

=(3m+8)am+1+mam-3mam-1=

=((2m+5)am+1+3(m+1)am)+((m+3)am+1-(2m+3)am-3mam-1)=

=(m+4)am+2+0=(m+4)am+2.

Megjegyzések.

1. A (2) azonoságot nem csak próbálgatással lehet megtalálni. Tekintsük az

f(x)=a0+a1x+a2x2+...

függvényt. (Nem nehéz végiggondolni, hogy an3n, és ezért a hatványsor konvergens |x|< esetén.) Az (an) sorozat definíciójából megállapítható, hogy az f függvényre teljesül a következő differenciál-egyenlet:

(3)    f(0)=1,  (x-2x2-3x3)f'(x)+(2-3x-3x2)f(x)+2=0.

A (3) egyenletet megoldva (fáradságos, de megéri) kapjuk, hogy

Ezt átrendezve pedig az

(4)    x2f2(x)+(x-1)f(x)+1=0

azonosságot kapjuk. A (4) azonosságban az együtthatók vizsgálatából kapjuk a (2) azonosságot.

2. Az (an) sorozat egy másik előállítása:

Itt egész, ez az úgynevezett k-adik Catalan-szám.


A. 234. Az A, B, és C betűk felhasználásával szavakat (véges hosszúságú betűsorozatokat) készítünk. Egy szóval a következő műveleteket végezhetjük:

a) A szóban kiválasztunk néhány egymás utáni betűt - esetleg csak egyetlen egyet, vagy akár a teljes szót -, és ,,megduplázzuk'', például BBCACBBCABCAC;

b) Az a) lépés visszafelé: Ha valahol a szóban két egymás utáni részlet megegyezik, akkor az egyiket elhagyjuk: ABCABCBCABCBC.

Igazoljuk, hogy ilyen lépések sorozatával bármelyik szóból eljuthatunk egy legfeljebb 8-betűs szóhoz.

Megoldásvázlat. Ha az u és v szavak átalakíthatók egymásba, azt így fogjuk jelölni: uv, és azt mondjuk, hogy a két szó ekvivalens. Az u és v szavak egymás után írását pedig uv-vel jelöljük.

Először bebizonyítjuk a következő lemmát.

    Lemma. Ha az u szó az A, B, C betűk mindegyikét tartalmazza, akkor tetszőleges v szóhoz létezik olyan w szó, amelyre uvwu.

    Bizonyítás. Ha v csak egyetlen betű, akkor - mivel u ezt a betűt is tartalmazza -, u felírható u=u1vu2 alakban; ekkor legyen w=u2. Ezzel a választással

    uvw=(u1vu2)vu2=u1((vu2)(vu2))u1(vu2)=u.

    Az általános esetben legyenek v betűi sorrendben a1,...,ak. Mint láttuk, választhatók olyan w1,...,wk szavak, amelyekre (ua1)w1u, (ua1a2)w2ua1, ...,(ua1...ak)wkua1...ak-1. Ekkor

    uua1w1ua1a2w2w1...ua1...akwk...w1=uv(wk...w1),

    vagyis w=wk...w1 egy jó választás. Ezzel a lemmát igazoltuk.

Legyen most a egy olyan szó, amely legalább 9 betűből áll. Megmutatjuk, hogy ez ekvivalens egy rövidebb szóval.

Legyen a=bcd, ahol b az első 4 betűt tartalmazza, d pedig az utolsó 4-et. Könnyű ellenőrizni, hogy ha b vagy d csak kétféle betűből áll, akkor tartalmaz két megegyező, egymás utáni részletet, és ilyenkor a b) lépés közvetlenül alkalmazható.

Ha b és d mindhárom fajta betűt tartalmazza, akkor megmutatjuk, hogy abd. A lemma alapján létezik egy olyan e szó, amelyre b(cd)eb, és létezik egy olyan f szó is, amelyre defd. Ezek felhasználásával

a=bcdbc(def)bc(dedef)=(bcde)(def)bd.

Megjegyzések. 1. Nem minden 9-betűs szó hossza csökkenthető csupán a b) lépéssel. Sőt, akármilyen hosszú szó készíthető, amelyben nincs két egymás utáni megegyező részlet.

2.Egy lehetséges megoldás, ha a szavak kezdeteit vizsgálva minden esetre megadunk egy eljárást, amellyel a legalább 9-betűs szavak hossza csökkenthető, Pl.

    AAxAx;
    ABAAxABAx;
    ABABxABx;
    ABACAAxABACAx;
    ABACABAAxABACABAx;
    ABACABABxABACABx;
    ABACABACxABACx;
    ABACABBxABACABx;
    ...

18 olyan lényegében különböző eset van, amikor a b) lépés közvetlenül nem alkalmazható. Ezek közül 4 esetben két lépésben juthatunk rövidebb szóhoz, például

ABACBCACBABACBCACBCBABACBCB.

(Az utolsó szó tovább rövidíthető az ABACB szóvá.)

A fennmaradó esetekben több lépésre van szükség. A megoldásban látott algoritmus ezekre nem a legrövidebb megoldást adja, pl. az a=ABCBACABC, szóra alkalmazva b=ABCB, c=A, d=CABC, e=ABACACBABCB és f=CBABACBACACACABABCABC. A leghosszabb szó, amelyre az eljárás során szükség van, a 46-betűs

bcdedef = ABCBACABCABACACBABCBCABCABACACBABCBCBABACBACACACABABCABC

szó. Ugyanakkor az ABCBACABC szó egyszerűbben is lerövidíthető, például

(1) ABCBACABCABCBACABCBCABCBACABCBABCBCABCBACABCBACBABCBCABCBACBABCABCBABC.

3. A feladat (kissé más megfogalmazásban) a Keszthelyen, 1999. július 28. és augusztus 2. között, egyetemisták és főiskolások részére megrendezett nemzetközi matematikaverseny (6th International Mathematics Competition for University Students) egyik feladata volt. Az (1) azonosság a szófiai egyetem egyik versenyzőjétől, Najden Kamboucsevtől származik.


A. 235. Legyen a adott komplex szám. Mi a mértani helye azon b komplex számoknak, amelyekhez léteznek olyan nemnegatív x1,x2,...,xn valós számok és egységnyi abszolút értékű z1,z2,...,zn komplex számok, hogy x1+x2+...+xn=1, x1z1+x2z2+...+xnzn=a és x1z12+x2z22+...+xnzn2=b?

Megoldásvázlat. Legyen b=p1z12+...+pnzn2. Megjegyezzük, hogy a és b abszolút értéke is legfeljebb 1 lehet, mivel egységnyi komplez számok súlyozott átlagai.

Azt állítjuk, hogy a keresett halmaz az a2 középpontú, 1-|a|2 sugarú körlemez.

Először is megmutatjuk, hogy b biztosan eleme a körlemeznek. Legyen . Ekkor tetszőleges szögre, felhasználva a cos 2t=1-2sin2t azonosságot, a súlyozott számtani és négyzetes közép közötti egyenlőtlenséget valamint a Re z2=(Re z)2-(Im z)2 azonosságot,

vagyis

(1)    

Ha -t éppen b-a2 argumentumának választjuk, akkor (1) baloldalán |b-a2| áll. Ezért |b-a2|1-|a|2, vagyis b eleme az a2 középpontú, 1-|a|2 sugarú zárt körlemeznek.

Most megmutatjuk, hogy ha |b-a2|=1-|a|2, akkor léteznek olyan p1, p2 nemnegatív valós számok és z1, z2 egységnyi abszolút értékű komplex számok, amelyekre p1+p2=1, p1z1+p2z2=a és p1z12+p2z22=b, vagyis a körlemez határpontjai megfelelőek.

Legyen a b-a2 szám argumentuma , és vizsgáljuk meg, hogy (2)-ben mikor áll egyenlőség. Az egyenlőséghez szükséges és elegendő, ha a és szögek szinusza megegyezik; feltehetjük, hogy alkalmas szöggel és . Ezekre a számokra teljesülnie kell, hogy

(2)  

Láthatjuk, hogy -t úgy kell választanunk, hogy teljesüljön. Ez nyilván lehetséges, mert (2) baloldalának abszolút értéke, |a| legfeljebb 1. Ezután meghatározzuk a p1-p2 együtthatót úgy, hogy (2) két oldalának képzetes része is megegyezzen. Ismét csak amiatt, hogy a baloldal legfeljebb egységnyi abszolút értékű, |p1-p2| nem lehet nagyobb 1-nél. Végül p1-p2 és p1+p2=1 ismeretében meghatározzuk a p1 és p2 számokat. A kapott p1 és p2 nem lehet negatív |p1-p2|1 miatt.

Az ilyen módon konstruált p1, p2, z1, z2 számokra a konstrukció szerint p1z1+p2z2=a. Felhasználva, hogy definíciójából

valamint tetszőleges t-re e2it+1=2eitcos t,

Végül megmutatjuk, hogy a körlemez tetszőleges b pontjához léteznek a feltételeknek megfelelő p1, p2, p3, p4 és z1, z2, z3, z4 számok.

Húzzunk egy tetszőleges egyenest b-n keresztül; messe ez a kör kerületét b1-ben és b2-ben. Ekkor b=q1b1+q2b2 alkalmas q1, q2 nemnegatív számokkal, amelyekre q1+q2=1.

Az előbbieket a b1 és b2 számokra alkalmazva, léteznek olyan x1, y2, y3, y4 nemnegatív valós számok és egységnyi abszolút értékű z1, z2, z3, z4 komplex számok, amelyekre x1+x2=x3+x4=1, x1z1+x2z2=x3z3+x4z4=a, x1z12+x2z22=b1, végül x3z32+x4z42=b2. Ugyanezekkel a z1, z2, z3, z4 számokkkal és a p1=q1x1, p2=q1x2, p3=q2x3, p4=q2x4 választással

p1+p2+p3+p4=q1(x1+x2)+q2(x3+x+4)=q1+q2=1,

x1z1+p2z2+p3z3+p4z4=q1(x1z1+x2z2)+q2(x3z3+x4z4)=q1a+q2a=a,

x1z12+p2z22+p3z32+p4z42=q1(x1z12+x2z22)+q2(x3z32+x4z42)=q1b1+q2b2=b.

A p1z12+...+pnzn2 lehetséges értékeinek mértani helye a komplex számsíkon tehát az a2 középpontú, 1-|a|2 sugarú, zárt körlemez.