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

Az 1999. decemberi 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öMaL-ban folyamatosan közöljük.


A. 224. Bizonyítsuk be, hogy tetszőleges pozitív a1, a2, ..., an számokra

(1)  

1. megoldásvázlat. Könnyen elllenőrizhető, hogy

(2)  

(Beszorzás és rendezés után az (ai-ai+1)20 egyenlőtlenséget kapjuk.) A (2) egyenlőtlenséget i=1,2,...,n-re felírva és összezorozva éppen a bizonyítandó állítást kapjuk.

Csóka Endre (Debrecen, Fazekas M. Gimn., 9. o.)

2. megoldásvázlat. Az állítást teljes indukcióval bizonyítjuk. Ha n=1, akkor (1) mindkét oldalán 1+a1 áll.

Tegyük fel, hogy az állítás igaz n=k-1 esetén. Ebből bebizonyítjuk n=(k+1)-re is.

Az a1, ..., an számok ciklikus cseréjével a bizonyítandó állítás nem változik, ezért feltehetjük, hogy an az (egyik) legnagyobb. Írjuk fel az indukciós feltevést az a1, ..., an-1 számokra:

(3)  

Ahhoz, hogy ebből (1) következzen, elégséges, ha

Beszorozva és rendezve:

(an+an-12)(a1+an2)an(1+an)(a1+an-12)

(an-a1)(an-an-1)(a1+an)0.

Mivel ana1 és anan-1, a baloldalon mindhárom tényező nemnegatív.

3. megoldásvázlat. Tetszőleges H{1,2,...,n} nem üres halmaz esetén legyen

illetve legyen P0=1.

(1) jobboldala beszorzva nem más, mint

(4)  

Jelölje H' azt a halmazt, amit úgy kapunk, hogy H mindegyik elemét 1-gyel növeljük modulo n (azaz n+1 helyett 1-et írunk). (1) baloldala beszorozva

(5)  

Azt kell tehát igazolnunk, hogy

(6)  

Megmutatjuk, hogy (6) következik az úgynevezett rendezési tételből (megtalálható pl. Matematikai Versenytételek, II. rész, 60-61.oldal; Tankönyvkiadó, Budapest, 1988):

Legyenek x1, x2, ..., xn és y1, y2, ..., yn pozitív valós számok, és jelentse z1, z2, ..., zn a második sorozat egy permutációját. Az

S=x1z1+x2z2+...+xnzn

alakú összegek közül az a legnagyobb, amelyben a z1,...,zn számok ugyanúgy vannak rendezve, mint az x1,...,xn számok, vagyis xi<xj esetén zizj. A legkisebb öszzeg pedig az, amelyben a z1,...,zn számok ellentétesen vannak rendezve, mint az x1,...,xn számok, vagyis xi<xj esetén zizj.

Alkalmazzuk a rendezési tételt a PH2, az 1/PH illetve az 1/PH' (H{1,...,n}) számokra. Az 1/PH alakú számok az 1/PH' alakú számok egy permutációját adják, és rendezésük éppen ellentétes az PH2 alakú számokéval. Ezért

Baharev Ali (Vác, Boronkai Gy. Gimn., 12. o.) és

Gyenes Zoltán (Budapest, ELTE Apáczai Csere J. Gyak. Gimn., 12.o)

dolgozata alapján


A. 225. Jelölje S1 és S2 az 1, 2, ..., n számok páratlan, illetve páros osztói számának összegét. Igazoljuk, hogy

Megoldásvázlat. Tetszőleges k pozitív egész az 1,2,...,n számok közül pontosan darabnak osztója, ezért és . (Az összegek egy idő után csupa 0-ból állnak.)

Ismeretes, hogy vagyis

(1)  

Mivel tetszőleges k pozitív egészre

tetszőleges m pozitív egészre

(2)  

Legyen m tetszőleges pozitív egész. (1) és (2) felhasználásával

(3)  

Hasonlóképpen

(4)  

A (3) és (4) egyenlőtlenségek összevetéséből

(5)  

és ez tetszőleges m pozitív egészre igaz. Az választással azt kapjuk, hogy


A. 226. Adott egy gráf, amelynek csúcsai a pozitív egész számok és nem tartalmaz kxk-as teljes páros részgráfot. (k egy rögzített pozitív egész.) Igazoljuk, hogy létezik tetszőlegesen hosszú számtani sorozat, amelynek semelyik két eleme között nincs él.

Javasolta: Solymosi József, Budapest

Megoldásvázlat. Legyen m>1 tetszőleges pozitív egész. Bebizonyítjuk, hogy létezik olyan m hosszúságú számtani sorozat, amelynek semelyik két eleme között nincs él.

A továbbiakban, az egyszerűbb számolás kedvéért, tetszőleges valós x számra definiáljuk az számot a következőképpen:

Legyen N>max(k,3m) egy nagy pozitív egész. (Később pontosan definiáljuk.) Vizsgáljuk meg, hogy az 1,2,...,N csúcsú gráfban hány élt kell behúzni ahhoz, hogy tetszőleges m hosszú számtani sorozat valamelyik két eleme között legyen él. A d differenciájú, m hosszúságú számtani sorozatok száma N-(m-1)d. Az összes m hosszúságú számtani sorozatok száma pedig

Mindegyik számtani sorozathoz található egy él, ami két elem között halad. Egy él legfeljebb darab m hosszú számtani sorozat elemei között haladhat, ezért a gráf éleinek száma e>.

Most vizsgáljuk meg, hogy ha egy N pontú gráf nem tartalmaz kxk-as teljes páros részgráfot, akkor legfeljebb hány éle lehet.

Legyenek a csúcsok fokszámai f1, f2, ..., fN; az élek száma e=(f1+f2+...+fN)/2.

Számoljuk meg, hogy a gráf hány 1xk-as teljes páros részgráfot tartalmaz. Az i-edik csúcshoz, amelynek foka fi, összesen -féleképpen választhatunk ki k darabot, amelyek szomszédosak vele. Az 1xkas teljes páros részgráfok száma tehát

Ha egy csúcs k-ast k alkalommal kiválasztanánk, akkor ez azt jelentené, hogy létezik egy kxk-as teljes páros részgráf. Ezért mindegyik csúcs k-ast legfeljebb k-1 alkalommal választottuk ki. Az 1xk-as teljes részgráfok száma tehát legfeljebb

Az függvény konvex, ezért felírhatjuk rá a Jensen-egyenlőtlenséget. A korábban kapott becsléssel együtt

Átrendezve

A kapott becsléseket összegezve

,

azaz N<(2m)3k. Ha N ennél nagyobb, akkor az 1,2,...,N számok közül biztosan kiválasztható olyan számtani sorozat, amelynek semelyik két eleme között nincs él.