KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum
Versenykiírás
Tudnivalók
Nevezési lap
Feladatok
Eredmények
Korábbi évek
Arcképcsarnok
Munkafüzet

Rendelje meg a KöMaL-t!

MBUTTONS

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

A 2001. novemberi 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. 275. Egy nxn-es táblázatba beírjuk sorban az 12, 22, 32, ..., (n2)2 számokat:

12 22 ... n2
(n+1)2 (n+2)2 ... (2n)2
... ...   ...
(n2-n+1)2 (n2-n+2)2 ... (n2)2

Minden sorból kiválasztunk egy-egy számot úgy, hogy semelyik kettő ne legyen ugyanabban az oszlopban.

Mik a kiválasztott számok összegének lehetséges értékei?

Terpai Tamás ötletéből

 

Megoldás. Tegyük fel, hogy az i-edik sorból rendre az ai-edik elemet választottuk ki. (i=1,2,...,n.) Az a1,...,an számok az 1,2,...,n egy permutációja, a kiválasztott számok összege pedig

\(\displaystyle \sum_{i=1}^n\big((i-1)n+a_i\big)^2=n^2\sum_{i=1}^n(i-1)^2+\sum_{i=1}^na_i^2+2n\sum_{i=1}^n(i-1)a_i.\)

Az első két összeg értéke nem függ az ai-k kiválasztásától:

\(\displaystyle n^2\sum_{i=1}^n(i-1)^2=n^2\cdot{(n-1)n(2n-1)\over6}={n^3(n-1)(2n-1)\over6},\)

\(\displaystyle \sum_{i=1}^na_i^2=\sum_{i=1}^ni^2={n(n+1)(2n+1)\over6}.\)

A harmadik összeg a rendezési tétel szerint akkor a legkisebb, illetve legnagyobb, amikor az ai számok csökkenő, illetve növekvő sorozatot alkotnak. Ezért a legkisebb és legnagyobb érték

\(\displaystyle 2n\sum_{i=1}^n(i-1)(n-i+1)=2n\cdot{(n-1)n(n+1)\over6},\)

illetve

\(\displaystyle 2n\sum_{i=1}^n(i-1)i=2n\cdot{(n-1)n(n+1)\over3}.\)

Egy kis számolással ellenőrizhető, hogy n kis értékeire \sum_{i=1}^n(i-1)a_i lehetséges értékei a következők:

n\sum_{i=1}^n(i-1)a_i lehetséges értékei
10
21, 2
34, 5, 7, 8
410, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Indukcióval bizonyítjuk, hogy n\(\displaystyle ge\)5 esetén \sum_{i=1}^n(i-1)a_i minden egész értéket felvesz {(n-1)n(n+1)\over6} és \(\displaystyle {(n-1)n(n+1)\over3}\) között. Mint láttuk, n=4 esetén ez igaz.

Ha az állításunk igaz valamely n=m-re, akkor n=m+1 esetén vizsgáljuk meg azokat az a1,...,am+1 sorozatokat, amikor am+1=m+1 illetve a1=m+1.

Abban az esetben, amikor am+1=m+1,

\(\displaystyle \sum{i=1}^n(i-1)a_i=\sum_{i=1}^ma_i+(m-1)m,\)

és ugyanazokat az összegeket kapjuk, mint az n=m esetben, csak m(m+1)-gyel megnövelve. Az ilyen összegek tehát az \(\displaystyle A={(m-1)m(m+1)\over6}+m(m+1)\) és B={(m-1)m(m+1)\over3}+m(m+1)={m(m+1)(m+2)\over3} közötti egészek.

Ha a1=m+1, akkor

\(\displaystyle \sum_{i=1}^n(i-1)a_i=\sum_{i=2}^{m+1}(i-1)a_i=\sum_{i=1}^mia_{i+1}=\)

\(\displaystyle =\sum_{i=1}^m(i-1)a_{i+1}+\sum_{i=1}^na_{i+1}=\sum_{i=1}^m(i-1)a_{i+1}+{m(m+1)\over2},\)

ezért ebben az esetben is ugyanazokat az összegeket kapjuk, de ezúttal \(\displaystyle {m(m+1)\over2}\)-vel növelve. A kapott összegek tehát a C={(m-1)m(m+1)\over6}+{m(m+1)\over2}={m(m+1)(m+2)\over6} és \(\displaystyle D={(m-1)m(m+1)\over3}+{m(m+1)\over2}\) közötti egészek.

Könnyen ellenőrizhető, hogy m\(\displaystyle ge\)4 esetén C<AleD<B, ezért az összes C és B közötti egész előáll. Ezzel állításunkat igazoltuk.

A végeredmény: a táblázatból kiválasztott elemek összegének lehetséges értékei n\(\displaystyle ne\)3 esetén egy számtani sorozatot alkotnak, amelynek legkisebb eleme

\(\displaystyle {n^3(n-1)(2n-1)\over6}+{n(n+1)(2n+1)\over6}+2n\cdot{(n-1)n(n+1)\over6}={n(2n^4-n^3+3n^2+n+1)\over6},\)

legnagyobb eleme

\(\displaystyle {n^3(n-1)(2n-1)\over6}+{n(n+1)(2n+1)\over6}+2n\cdot{(n-1)n(n+1)\over3}={n(2n^4+n^3+3n^2-n+1)\over6},\)

differenciája pedig 2n.

Az n=3 esetben az eredmény hasonló, de a sorozat középső eleme, a 95 nem áll elő; a lehetséges értékek 83, 89, 101 és 107.


A. 276. Az x1, ..., xn pozitív számok szorzata (n^\alpha-1)^n, ahol alphage1 valós szám. Bizonyítsuk be, hogy

\(\displaystyle \sum_{i=1}^n{1\over(x_i+1)^{1/\alpha}}\ge1.\)

Megoldás. Legyen \(\displaystyle f(t)={1\over(t+1)^{1/\alpha}}\). Be fogjuk bizonyítani a következő két lemmát:

1. lemma. Ha a\(\displaystyle le\)b\(\displaystyle le\)c\(\displaystyle le\)d pozitív számok és ad=bc, akkor

\(\displaystyle f(a)+f(d)\ge\min\big(f(b)+f(c),1\big).\)

2. lemma. Ha az x1,x2,...,xn számok mértani közepe m, akkor

\(\displaystyle f(x_1)+f(x_2)+\dots+f(x_n)\ge\min\big(n\cdot f(m),1\big).\)

A feladat állítása a 2. lemma speciális esete, ugyanis ha az x1,...,xn pozitív számok szorzata (n\(\displaystyle alpha\)-1)n, azaz a mértani közepük m=n\(\displaystyle alpha\)-1, akkor n.f(m)=1.

Az 1. lemma bizonyítása. Legyen m=\sqrt{ad}=\sqrt{bc}, tetszőleges pozitív t esetén

\(\displaystyle g(t)=f(mt)+f(m/t)=\bigg(mt+1\bigg)^{-{1\over\alpha}}+\bigg({m\over t}+1\bigg)^{-{1\over\alpha}},\)

továbbá t1=c/m és t2=d/m. Ekkor 1let1\(\displaystyle le\)t2, és a bizonyítandó állítás az, hogy

\(\displaystyle g(t_2)\ge\min\big(g(t_1),1\big).\)

A definícióból látható, hogy \(\displaystyle \lim\limits_\infty g=1.\)

Vizsgáljuk meg a g függvényt az [1,infty) intervallumon monotonitás szempontjából. A g függvény deriváltja

\(\displaystyle g'(t)={m\over\alpha}\left(-\bigg(mt+1\bigg)^{-{\alpha+1\over\alpha}}+{1\over t^2}\bigg({m\over t}+1\bigg)^{-{\alpha+1\over\alpha}}\right).\)

ami akkor és csak akkor pozitív, ha

\(\displaystyle \bigg(mt+1\bigg)^{\alpha+1\over\alpha\)t^2\bigg({m\over t}+1\bigg)^{\alpha+1\over\alpha}.">

\(\displaystyle {\alpha\over\alpha+1}\)-edik hatványra emelve és rendezve:

\(\displaystyle t^{2\alpha\over\alpha+1}-mt+mt^{\alpha-1\over\alpha+1}-1<0.\)

Jelöljük a baloldalt h(t)-vel. A további diszkusszióhoz szükségünk lesz a h függvény első két deriváltjára, valamint a h(1) és h'(1) értékére. Tehát,

\(\displaystyle h(t)=t^{2\alpha\over\alpha+1}-mt+mt^{\alpha-1\over\alpha+1}-1,\qquad h(1)=0;\)

\(\displaystyle h'(t)={2\alpha\over\alpha+1}t^{\alpha-1\over\alpha+1}-m+{\alpha-1\over\alpha+1}mt^{-{2\over\alpha+1}},\qquad h'(1)={2\over\alpha+1}(\alpha-m);\)

\(\displaystyle h''(t)={2\alpha(\alpha-1)\over(\alpha+1)^2}t^{-{\alpha+3\over\alpha+1}}\bigg(t-{m\over\alpha}\bigg).\)

Ezután több esetet fogunk vizsgálni aszerint, hogy m és alpha mekkora.

1. eset: \(\displaystyle alpha\)=1 és m\(\displaystyle le\)1.

2. eset: \(\displaystyle alpha\)=1 és m>1.

3. eset: \(\displaystyle alpha\)>1 és m\(\displaystyle le\)alpha.

4. eset: alpha>1 és m>alpha.

Az 1. esetben tetszőleges t>1-re h(t)=(1-m)(t-1)ge0, tehát a (1,infty) intervallumban hge0.

A 2. esetben tetszőleges t>1-re h(t)=(1-m)(t-1)<0, tehát az (1,infty) intervallumban h<0.

A 3. esetben h'(1)ge0 és t>1 esetén h''>0, tehát a teljes (1,infty) intervallumban h'>0. Mivel h(1)=0, ebből következik, hogy az (1,infty) intervallumban h>0.

A 4. esetben h'(1)<0 és az (1,m/alpha) intervallumban h''<0, így ebben az intervallumban h'<0. Mivel h(1)=0, ebből következik, hogy az (1,m/alpha] intervallumban h<0. Az (m/alpha,infty) intervallumban h''>0, vagyis a h függvény konvex. Mivel h(m/alpha)<0 és \lim\limits_\infty
h=\infty, ebből következik, hogy létezik egy olyan varrho>1 valós szám, hogy az (1,varrho) intervallumon h<0 és a (varrho,infty) intervallumon h>0.

Bármelyik esetről is legyen szó, ha h(t2)ge0, akkor a teljes (t2,infty) intervallumban hge0, azaz g'le0. Ezért a g függvény a [t2,infty) intervallumban monoton fogy, és g(t_2)\ge\lim\limits_\infty g=1. Ha pedig h(t2)le0, akkor az (1,t2) intervallumban hle0, azaz g'ge0, tehát g monoton nő, és g(t1)leg(t2). Ezzel az 1. lemmát igazoltuk.

A 2. lemma bizonyítása. Az állítást teljes indukcióval igazoljuk. Ha n=1, akkor csak x1=m lehetséges, és az állítás semmitmondó. Tegyük fel, hogy nge2, és kevesebb változó esetén az állítás igaz.

Az x1,...,xn számok között van m-nél nem nagyobb és nem kisebb is; a szimmetria miatt feltehetjük például, hogy x1lemlex2. Jelöljük az m és az x1x2/m számok közül a kisebbiket y1-gyel, a nagyobbikat y2-vel. Ekkor x1ley1ley2lex2 és y1y2=x1x2. Ezért az 1. lemma alapján

(1)f(x_1)+f(x_2)\ge\min\big(f(y_1)+f(y_2),1\big)=\min\big(f(m)+f(y_2),1\big)

Az y2,x3,...,xn számok mértani közepe szintén m, ezért az indukciós feltevés alapján

(2)f(y_2)+f(x_3)+\dots+f(x_n)\ge\min\big((n-1)f(m),1\big)

Ha f(x1)+f(x2)>1, akkor f(x1)+...+f(xn)gef(x1)+f(x2)>1, tehát az állítás igaz. Ha f(x1)+f(x2)le1, akkor (1) azt mondja, hogy f(x1)+f(x2)gef(m)+f(y2). Ezt és (2)-t felhasználva,

f(x1)+f(x2)...+f(xn)gef(m)+f(y2)+f(x3)+...+f(xn)ge

\ge
f(m)+\min\big((n-1)f(m),1\big)=\min(nf(m),f(m)+1\big)\ge\min(nf(m),1\big).

Ezzel a 2. lemmát, egyben a feladat állítását is igazoltuk


A. 277. Legyen H1 egy n-oldalú sokszög. Készítsük el a H1, H2, ..., Hn sokszögsorozatot a következőképpen. Ha Hk-t már elkészítettük, akkor Hk+1-et úgy kapjuk, hogy Hk csúcsait rendre tükrözzük a pozitív körüljárás szerinti k-adik szomszédjukra.

Bizonyítsuk be, hogy ha n prímszám, akkor a H1 és Hn sokszögek hasonlók.

1. megoldás. A megoldás során, a kimondott segédállítások világosabb megfogalmazása érdekében az n-oldalú sokszögek helyett pont n-eseket fogunk használni.

Tetszőleges 0<k<n egész szám esetén jelöljük tauk-val azt a transzformációt, amelynek során egy pont n-esből úgy állítunk elő egy másik pont n-est, hogy mindegyik pontot tükrözzük a k-adik rákövetkezőjére. A transzformáció definícióját tetszőleges k egész számra is értelmezhetjük, ha k-t modulo n vizsgáljuk.

A feladat szerint Hk+1=tauk(Hk), és azt kell igazolnunk, hogy a taun-1(taun-2(...tau2(tau1(H1))...)) n-szög hasonló a H1-hez.

Először bebizonyítjuk, hogy a transzformációk felcserélhetők, azaz tetszőleges k,m egész számokra és P pont n-esre taum(tauk(P))=tauk(taum(P)). Legyenek P pontjai p1, ..., pn. Ekkor -- az indexeket modulo n értelmezve --

- a tauk(P) sokszög i-edik pontja 2pi+k-pi;

- a taum(P) sokszög i-edik pontja 2pi+m-pi;

- a taum(tauk(P)) sokszög i-edik pontja 2(2pi+m+k-pi+m)-(2pi+k-pi)=4pi+m+k-2pi+k-2pi+m+pi;

- a tauk(taum(P)) sokszög i-edik pontja 2(2pi+k+m-pi+k)-(2pi+m-pi)=4pi+m+k-2pi+k-2pi+m+pi.

A taum(tauk(P)) és a tauk(taum(P)) pont n-es tehát ugyanaz.

A transzformációk felcserélhetőségéből következik, hogy a tau1, tau2, ..., taun-1 transzformációkat tetszőleges sorrendben végrehajthatjuk, az eredmény mindig ugyanaz lesz.

Legyen H1=(h1,...,hn) és Hn=(g1,...,gn). Mivel minden egyes transzformáció a pontokat egy-egy lineáris kombinációra cseréli ki, a g1, ..., gn pontok mindegyike a h1, ..., hn pontok egy-egy alkalmas lineáris kombinációjaként írható fel. Mivel pedig az indexek ciklikus cseréjére a transzformációsorozat szimmetrikus, az egyes kombinációk együtthatói egymásból ciklikus cserével kaphatók, azaz léteznek olyan a0, a1, ..., an-1 konstansok, hogy tetszőleges i esetén

(3)gi=a0hi+a1hi+1+...+an-1hi+n-1.

Még azt is megmutatjuk, hogy a1=a2=...=an-1.

Legyen tetszőleges 0<m<n egészre pim az (x_1,\dots,x_n)\to(x_m,x_{2m},\dots,x_{nm}) permutáció. (Ez valóban permutáció, ha n prímszám.) A definíciót behelyettesítve ellenőrizhető, hogy tetszőleges k egész és P pont n-es esetén

tauk(pim(P))=pim(taukm(P)).

Ezt az azonosságot (n-1)-szer alkalmazva,

taun-1(taun-2(...tau1(pim(H1))...))=pim(tau(n-1)m(tau(n-2)m(...taum(H1)...))).

Mivel n prímszám, a taum, tau2m, ..., tau(n-1)m transzformációk között tau1, ..., taun-1 mindegyike pontosan egyszer fordul elő. Ezért a jobboldalon pim(Hn)=(gm,g2m,...,gnm) áll.

A baloldalon a transzformációkat a pim(H1)=(hm,h2m,...,hnm) sokszögre alkalmazzuk. A (3) azonosság szerint az eredményül kapott pont n-es i-edik tagja

a0him+a1h(i+1)m+...+an-1h(i+n-1)m.

Az eredményeket összegezve, tetszőleges i esetén

a0him+a1h(i+1)m+...+an-1h(i+n-1)m=

=gim=a0him+a1him+1+...+an-1him+n-1.

A h(i+1)m együtthatója a baloldalon a1, a jobboldalon am, ezért am=a1. Mivel ez minden 0<m<n-re igaz, a1=a2=...=an-1.

A H1 és a Hn sokszög i-edik élvektora hi+1-hi, illetve gi+1-gi=(a0-a1)(hi+1-hi). Ezért a két sokszög hasonló, a hasonlóság aránya a0-a1.

2. megoldás. A feladatot komplex számok és az úgynevezett véges Fourier-transzformált segítségével oldjuk meg. A sokszögeket komplex számokból álló szám n-eseknek tekintjük. Hogy a későbbi számolás valamivel egyszerűbb legyen, helyezzük el H1-et a komplex számsíkon úgy, hogy súlypontja a 0 legyen.

A szám n-esek tagjait indexeléssel fogjuk jelölni. Ha X egy szám n-est jelöl, akkor Xj fogja jelölni a j-edik elemét. Az indexelés mindig modulo n történik, például Xn=X0 vagy X-1=Xn-1.

A komplex szám n-esek körében értelmezzük a tagonkénti összeadást, kivonást és szorzást, továbbá a számmal való szorzást. Ezen kívül definiáljuk a szám n-esek véges Fourier-transzformáltját a következőképpen. Legyen \varepsilon=\cos{2\pi\over n}+i\sin{2\pi\over n} az első n-edik komplex egységgyök. Az X szám n-es Fourier-transzformáltja az a varphi(X) szám n-es, amelyre tetszőleges j esetén

\varphi(X)_j=\sum_{m=0}^{n-1}\varepsilon^{mj}\cdot X_m.

A véges Fourier-transzformáltnak sok érdekes tulajdonsága és alkalmazása ismert, ezekről bővebben például Gács Péter és Lovász László Algoritmusok c. könyvében olvashatunk. Most a következőkre lesz szükségünk:

- Tetszőleges c számra és X szám n-esre varphi(c.X)=c.varphi(X).

- A Fourier-transzformált invertálható. Mint könnyen ellenőrizhető,

X_j={1\over n}\sum_{m=0}^{n-1}\varepsilon^{-mj}\cdot\varphi(X)_m.

Az 1. megoldáshoz hasonlóan legyen tauk az a transzformáció, amely során egy szám n-es mindegyik elemét tükrözzük a k-adik rákövetkezőjére, azaz

tauk(X)j=2Xj+k-Xj.

A Fourier-transzformált és tauk definíciójából következik, hogy tetszőleges x szám n-esre

\varphi(\tau_k(x))_j=\sum_{m=0}^{n-1}\varepsilon^{jm}\cdot\tau_k(x)_m=\sum_{m=0}^{n-1}\varepsilon^{jm}\cdot(2x_{m+k}-x_m)=

=2\varepsilon^{-kj}\sum_{m=0}^{n-1}\varepsilon^{j(m+k)}\cdot x_{m+k}-\sum_{m=0}^{n-1}\varepsilon^{jm}\cdot x_m=(2\varepsilon^{-jk}-1)\varphi(x)_j,

azaz

varphi(tauk(x))=(1,2varepsilon-k-1,2varepsilon-2k-1,...,2varepsilon-(n-1)k-1).varphi(x).

Ezt minden 0<k<n-re alkalmazva,

\varphi(\tau_{n-1}(\tau_{n-2}(\dots\tau_2(\tau_1(x))\dots)))_j=\prod_{k=1}^{n-1}(2\varepsilon^{-kj}-1)\varphi(x)_j.

Ha j=0, akkor \prod_{k=1}^{n-1}(2\varepsilon^{-kj}-1)=1. Ha 0<j<n, akkor -- mivel n prímszám -- \prod_{k=1}^{n-1}(2\varepsilon^{-kj}-1)=\prod_{k=1}^{n-1}(2\varepsilon^k-1). Jelöljük ezt a számot C-vel.

Azt kaptuk tehát, hogy

(4)varphi(taun-1(taun-2(...tau2(tau1(x))...)))=(1,C,C,...,C).varphi(x).

Tekintsük a varphi(H1) és a varphi(Hn) szám n-eseket. A súlypont megválasztása miatt varphi(H1)0=0, és ezért (4)-et a következő alakba is írhatjuk:

varphi(Hn)=varphi(taun-1(taun-2(...tau2(tau1(H1))...)))=C.varphi(H1).

Ebből következik, hogy Hn=C.H1, vagyis Hn a H1 0 középpontú, C-szeres nagyítása.

Megjegyzés. A

p(t)=(t-varepsilon)(t-varepsilon2).(t-varepsilonn-1)=xn-1+xn-2+...+x+1

polinom felhasználásával

C=\prod_{k=1}^{n-1}(2\varepsilon^k-1)=\varepsilon^{1+2+...+(n-1)}p(2)=\varepsilon^{n(n-1)/2}(2^n-1)=2^n-1.

(Felhasználtuk, hogy n páratlan prímszám, és n(n-1)/2 osztható n-nel.)

Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley