![]() |
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:
|
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
n∑i=1((i−1)n+ai)2=n2n∑i=1(i−1)2+n∑i=1a2i+2nn∑i=1(i−1)ai.
Az első két összeg értéke nem függ az ai-k kiválasztásától:
n2n∑i=1(i−1)2=n2⋅(n−1)n(2n−1)6=n3(n−1)(2n−1)6,
n∑i=1a2i=n∑i=1i2=n(n+1)(2n+1)6.
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
2nn∑i=1(i−1)(n−i+1)=2n⋅(n−1)n(n+1)6,
illetve
2nn∑i=1(i−1)i=2n⋅(n−1)n(n+1)3.
Egy kis számolással ellenőrizhető, hogy n kis értékeire lehetséges értékei a következők:
|
Indukcióval bizonyítjuk, hogy nge5 esetén minden egész értéket felvesz
és (n−1)n(n+1)3 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,
∑i=1n(i−1)ai=m∑i=1ai+(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 A=(m−1)m(m+1)6+m(m+1) és közötti
egészek.
Ha a1=m+1, akkor
n∑i=1(i−1)ai=m+1∑i=2(i−1)ai=m∑i=1iai+1=
=m∑i=1(i−1)ai+1+n∑i=1ai+1=m∑i=1(i−1)ai+1+m(m+1)2,
ezért ebben az esetben is ugyanazokat az összegeket kapjuk, de
ezúttal m(m+1)2-vel növelve. A kapott összegek tehát a és
D=(m−1)m(m+1)3+m(m+1)2 közötti egészek.
Könnyen ellenőrizhető, hogy mge4 esetén C<AD<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 nne3 esetén egy számtani sorozatot alkotnak, amelynek legkisebb eleme
n3(n−1)(2n−1)6+n(n+1)(2n+1)6+2n⋅(n−1)n(n+1)6=n(2n4−n3+3n2+n+1)6,
legnagyobb eleme
n3(n−1)(2n−1)6+n(n+1)(2n+1)6+2n⋅(n−1)n(n+1)3=n(2n4+n3+3n2−n+1)6,
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 ,
ahol
1 valós
szám. Bizonyítsuk be, hogy
n∑i=11(xi+1)1/α≥1.
Megoldás. Legyen f(t)=1(t+1)1/α. Be fogjuk bizonyítani a következő két lemmát:
1. lemma. Ha aleblecled pozitív számok és ad=bc, akkor
f(a)+f(d)≥min
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 , 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 1t1\displaystyle let2, é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,) 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\alphat^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 mekkora.
1. eset: \displaystyle alpha=1 és m\displaystyle le1.
2. eset: \displaystyle alpha=1 és m>1.
3. eset: \displaystyle alpha>1 és m\displaystyle le.
4. eset: >1 és m>
.
Az 1. esetben tetszőleges t>1-re
h(t)=(1-m)(t-1)0, tehát a (1,
) intervallumban h
0.
A 2. esetben tetszőleges t>1-re
h(t)=(1-m)(t-1)<0, tehát az (1,)
intervallumban h<0.
A 3. esetben h'(1)0 és t>1 esetén h''>0,
tehát a teljes (1,
) intervallumban h'>0. Mivel h(1)=0,
ebből következik, hogy az (1,
) intervallumban h>0.
A 4. esetben h'(1)<0 és az (1,m/)
intervallumban h''<0, így ebben az intervallumban
h'<0. Mivel h(1)=0, ebből következik, hogy az
(1,m/
] intervallumban h<0. Az (m/
,
)
intervallumban h''>0, vagyis a h függvény
konvex. Mivel h(m/
)<0 és
, ebből következik, hogy létezik egy olyan
>1 valós
szám, hogy az (1,
) intervallumon h<0 és a (
,
) intervallumon
h>0.
Bármelyik esetről is legyen szó, ha
h(t2)0, akkor a teljes
(t2,
) intervallumban h
0, azaz g'
0. Ezért a g
függvény a [t2,
) intervallumban monoton fogy, és
Ha pedig
h(t2)
0, akkor az (1,t2)
intervallumban h
0, azaz g'
0, tehát g monoton nő, és
g(t1)
g(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 n2, é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 x1m
x2. Jelöljük az m és az
x1x2/m számok közül a
kisebbiket y1-gyel, a nagyobbikat
y2-vel. Ekkor x1
y1
y2
x2
és
y1y2=x1x2. Ezért
az 1. lemma alapján
(1) | ![]() |
Az y2,x3,...,xn számok mértani közepe szintén m, ezért az indukciós feltevés alapján
(2) | ![]() |
Ha
f(x1)+f(x2)>1,
akkor
f(x1)+...+f(xn)f(x1)+f(x2)>1,
tehát az állítás igaz. Ha
f(x1)+f(x2)
1, akkor (1) azt
mondja, hogy
f(x1)+f(x2)
f(m)+f(y2). Ezt és
(2)-t felhasználva,
f(x1)+f(x2)...+f(xn)f(m)+f(y2)+f(x3)+...+f(xn)
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 k-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=k(Hk), és azt kell igazolnunk, hogy a
n-1(
n-2(...
2(
1(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 m(
k(P))=
k(
m(P)). Legyenek P pontjai p1, ..., pn. Ekkor -- az indexeket modulo n értelmezve --
- a k(P) sokszög i-edik pontja 2pi+k-pi;
- a m(P) sokszög i-edik pontja 2pi+m-pi;
- a m(
k(P)) sokszög i-edik pontja 2(2pi+m+k-pi+m)-(2pi+k-pi)=4pi+m+k-2pi+k-2pi+m+pi;
- a k(
m(P)) sokszög i-edik pontja 2(2pi+k+m-pi+k)-(2pi+m-pi)=4pi+m+k-2pi+k-2pi+m+pi.
A m(
k(P)) és a
k(
m(P)) pont n-es tehát ugyanaz.
A transzformációk felcserélhetőségéből következik, hogy a 1,
2, ...,
n-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 m az
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
k(
m(P))=
m(
km(P)).
Ezt az azonosságot (n-1)-szer alkalmazva,
n-1(
n-2(...
1(
m(H1))...))=
m(
(n-1)m(
(n-2)m(...
m(H1)...))).
Mivel n prímszám, a m,
2m, ...,
(n-1)m transzformációk között
1, ...,
n-1 mindegyike pontosan egyszer fordul elő. Ezért a jobboldalon
m(Hn)=(gm,g2m,...,gnm) áll.
A baloldalon a transzformációkat a m(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 az első n-edik komplex egységgyök. Az X szám n-es Fourier-transzformáltja az a
(X) szám n-es, amelyre tetszőleges j esetén
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 (c.X)=c.
(X).
- A Fourier-transzformált invertálható. Mint könnyen ellenőrizhető,
Az 1. megoldáshoz hasonlóan legyen k 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
k(X)j=2Xj+k-Xj.
A Fourier-transzformált és k definíciójából következik, hogy tetszőleges x szám n-esre
azaz
(
k(x))=(1,2
-k-1,2
-2k-1,...,2
-(n-1)k-1).
(x).
Ezt minden 0<k<n-re alkalmazva,
Ha j=0, akkor . Ha 0<j<n, akkor -- mivel n prímszám --
. Jelöljük ezt a számot C-vel.
Azt kaptuk tehát, hogy
(4) | ![]() ![]() ![]() ![]() ![]() ![]() |
Tekintsük a (H1) és a
(Hn) szám n-eseket. A súlypont megválasztása miatt
(H1)0=0, és ezért (4)-et a következő alakba is írhatjuk:
(Hn)=
(
n-1(
n-2(...
2(
1(H1))...)))=C.
(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-)(t-
2).(t-
n-1)=xn-1+xn-2+...+x+1
polinom felhasználásával
(Felhasználtuk, hogy n páratlan prímszám, és n(n-1)/2 osztható n-nel.)