Cím: A 43. Nemzetközi Matematikai Diákolimpia feladatainak megoldásai
Füzet: 2002/október, 386 - 395. oldal  PDF  |  MathML 
Témakör(ök): Nemzetközi Matematikai Diákolimpia

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A hagyományoknak megfelelően ebben az évben is közöljük a nyári matematikai diákolimpia feladatainak a megoldásait úgy, ahogyan a legilletékesebbek, a magyar csapat tagjai leírták. Közreműködésüket köszönjük és ezúton is gratulálunk eredményeikhez.

 
A szerkesztőség

1. Legyen n pozitív egész szám. Legyen T a sík azon (x,y) pontjainak halmaza, amelyekre x és y nemnegatív egész számok és x+y<n. T minden pontját pirosra vagy kékre színezzük. Ha az (x,y) pont színe piros, akkor T minden olyan (x',y') pontjának a színe is piros, amelyre x'≤x és y'≤y mindegyike teljesül. Nevezzük X-halmaznak az olyan halmazokat, amelyek n olyan kék pontból állnak, amelyek x-koordinátái mind különbözőek, és nevezzük Y-halmaznak az olyan halmazokat, amelyek n olyan kék pontból állnak, amelyek y-koordinátái mind különbözőek.
Bizonyítsuk be, hogy az X-halmazok száma megegyezik az Y-halmazok számával.
 
 


Gerencsér Balázs megoldása. A T halmaz adott színezésére jelölje |X| és |Y| az X-halmazok, illetve az Y-halmazok számát. |X| értéke nyilván az adott x-koordinátájú, a színezés nyomán kialakuló háromszög alakú mintázat egyes ,,oszlopaiban'' lévő kék pontok számának a szorzata. (Ha egy oszlopban nincs kék pont, akkor a megfelelő tényező és így a szorzat értéke is 0, összhangban azzal, hogy ilyenkor természetesen nem jön létre X-halmaz.) Hasonlóan kapjuk |Y| értékét az egyes sorokban lévő kék pontok elemszámának a szorzataként.
 
 

A balról legszélső oszloppal kezdve számozzuk most meg a piros pontokat, az egyes oszlopokban alulról felfelé haladva. Ha egyáltalán nincsen piros pont, akkor az ábra szimmetriája miatt nyilvánvalóan teljesül az állítás. Induljunk ki tehát az ,,azonosan kék'' mintázatból, és számozásunknak megfelelően fessük át a megfelelő kék pontokat egyesével pirosra. Megmutatjuk, hogy |X| és |Y| minden lépésben ugyanúgy változnak, ebből a bizonyítandó állítás nyilván következik.
Ha a (j;i) koordinátájú P pont ‐ ami az i-edik sor és a j-edik oszlop közös eleme ‐ színét változtatjuk kékről pirosra, akkor mivel a számozás szerkezete követi a piros pontoknak a feltételben megadott elrendezését, a P-től balra, illetve lefelé lévő valamennyi pont már piros. P(j;i) átfestésekor |X| csak a j-edik oszlop miatt változik. Ebben az oszlopban összesen n+1-j pont van, a piros pontok száma (i-1)-ről i-re nő, a kékeké pedig ennek megfelelően eggyel csökken, (n+2-j-i)-ről (n+1-j-i)-re. Ebben a lépésben tehát |X| értéke n+1-i-jn+2-i-j-szeresére változik.
Az i-edik sorban ezután i és j fölcserélésével hasonlóan kapjuk |Y| értékének a megváltozását: a bizonyítandó állítás most már következik abból, hogy a kapott együttható értéke nem változik ennek a cserének a során.
 
2. Legyen BC az O középpontú Γ kör egy átmérője. Legyen A a Γ kör egy olyan pontja, amelyre 0∘<AOB∢<120∘. Legyen D a C-t nem tartalmazó AB ív középpontja. Az O-n keresztül DA-val párhuzamosan húzott egyenes messe az AC egyenest a J pontban. OA felezőmerőlegesének és Γ-nak metszéspontjai legyenek E és F. Bizonyítsuk be, hogy J a CEF háromszög beírt körének a középpontja.
 
 


Csikvári Péter megoldása. Legyen BCA∢=α. Mivel a feltétel szerint BC a kör átmérője és így a Thalész-tétel miatt BAC∢=90∘, ezért CBA∢=90∘-α. Az egyenlő szárú OAB háromszögben OAB∢=90∘-α és így az egyenlő szárú OAC háromszögben OAC∢=OCA∢=α.
D felezi az AB ívet, így a BD íven feleakkora kerületi szög nyugszik, mint az AB-n: BAD∢=α2. Végül mivel OJ∥DA, így DAO∢=AOJ∢=90∘-α2. (1. ábra)
Tekintsük most az AOJ háromszög szögeit. AOJ∢=90∘-α2 és OAJ∢=α, tehát az AJO∢ szintén 90∘-α2, a háromszög egyenlő szárú: AO=AJ.
 
 

 1. ábra 2. ábra 
 

A feltétel szerint EF merőlegesen felezi a kör OA=r sugarát, AEOF tehát r oldalú rombusz. Így r=AF=FO=AO, az utóbbi szakaszról pedig láttuk, hogy AJ-vel egyenlő. Másfelől a fenti rombusz szimmetriája miatt A az EF ív felezőpontja. Ekkor pedig CA felezi az ECF szöget. Megmutatjuk, hogy a fenti két összefüggésből (AJ=AF, illetve CA felezi az ECF szöget) már következik az állítás.
Legyen ECF∢=γ, ekkor, mint láttuk, ACF∢=γ2. Így az AF íven nyugvó AEF∢ ugyancsak γ2 (2. ábra; a két ábrán az EFC háromszög nem egybevágó!). Ha φ jelöli az EC íven nyugvó kerületi szöget, akkor EFC∢=EAC∢=φ.
Ha most az EFC háromszög harmadik szögét, a CEF szöget ε-nal jelöljük, akkor ε+φ+γ=180∘ és EA=AJ miatt AEJ∢=180∘-φ2=90∘-φ2=ε+γ2. Így pedig FEJ∢=AEJ∢-AEF∢=(ε+γ2)-ε2=γ2. Az EJ egyenes tehát felezi a CEF szöget, ezzel pedig két belső szögfelező metszéspontjaként J valóban az EFC háromszög beírt körének a középpontja.
A fenti bizonyítás mindaddig érvényes, amíg J az AC szakasz belső pontja. Ez pedig pontosan akkor teljesül, ha AOJ∢<AOC∢, vagyis 90∘-α2<2(90∘-α). Ez pedig éppen az α<60∘, azaz a feltételül adott AOB∢<120∘ esetén teljesül.
 
3. Határozzuk meg az összes olyan (m,n) párt, ahol m, n egész számok, amelyekre m,n≥3, amelyekhez létezik végtelen sok olyan a pozitív egész szám, amire
am+a-1an+a2-1
egész szám.
 
 


Rácz Béla András megoldása. Legyen p(x)=xm+x-1 és q(x)=xn+x2-1. Először megmutatjuk, hogy ha egy (m,n) párra teljesül a feladat feltétele, akkor a nevező, mint polinom is osztója a számlálónak, azaz q(x)∣p(x).
Végezzük ehhez el a p(x) és a q(x) polinomok között a maradékos osztást, azaz legyen p(x)=h(x)⋅q(x)+r(x), ahol a maradék fokszáma kisebb, mint az osztóé, degr<degq. Mivel az osztó főegyütthatója 1, ezért mind a hányados, mind pedig a maradék egész együtthatós polinomok.
A feltétel szerint végtelen sok egész a-ra teljesül, hogy p(a)q(a)=h(a)+r(a)q(a) egész szám. Láttuk, hogy az a egész értékeire h(a) egész, így viszont végtelen sok egész a-ra lesz az r(a)q(a) hányados értéke is egész szám. A fokszámok összehasonlításából következik, hogy r(a)q(a)→0, ez pedig azt jelenti, hogy ennek a hányadosnak az értéke végtelen sok egész a-ra 0. Ugyanez ekkor a számlálóra is teljesül és ha egy polinom végtelen sok helyen veszi fel a 0 értéket, akkor a polinom azonosan nulla. Az r(x) polinom tehát azonosan nulla, a q(x) polinom tehát valóban osztója a p(x) polinomnak.
Ha m<n, akkor nyilván nem állhat fönn a talált oszthatóság. Föltehető ezért, hogy m≥n. Ekkor a q(x) polinom az
(x+1)⋅p(x)-q(x)=xn(xm-n+1+xm-n-1)
polinomnak is osztója. Mivel xn és xn+x2-1 relatív prímek és föltevésünk szerint a második tényező is polinom, ezért innen következik, hogy
xn+x2-1∣xm-n+1+xm-n-1.
Vezessük be a k=m-n jelölést. Ekkor k≥0, q(x)=xn+x2-1∣xk+1+xk-1 és nyilván k+1≥n.
Mivel q(x) folytonos függvény és q(0)<0<q(1), azért van olyan 0<α<1, hogy q(α)=0, azaz αn+α2=1. A q(x)∣xk+1+xk-1 oszthatóságot felhasználva innen αk+1+αk=1 következik. Így tehát
αn+α2=αk+1+αk=1.(*)
Ha k=1, akkor a második egyenlőség semmilyen valós α-ra nem teljesülhet. Ha k≥2, akkor n≥3 és így a már látott k+1≥n feltétellel együtt azt kapjuk, hogy
k≥n-1≥2.

Mivel 0<α<1, innen αn≥αk+1, illetve α2≥αk következik. Ez pedig (*) miatt csak akkor teljesülhet, ha αn=αk+1 és α2=αk, vagyis ha n=k+1 és 2=k, azaz ha m=5 és n=3.
Erre a számpárra másfelől a5+a-1=(a3+a2-1)(a2-a+1). Ha pedig a pozítiv egész, akkor a3+a2-1≥1+1-1>0, ezért a5+a-1a3+a2-1=a2-a+1, ami minden pozitív egész a-ra egész szám.
Egyetlen olyan számpár van tehát, amelyre teljesülnek a feladat feltételei: az (5;3).
 
4. Legyen n 1-nél nagyobb egész szám. n összes pozitív osztója
d1,d2,...,dk,ahol1=d1<d2<...<dk=n.
Legyen
D=d1d2+d2d3+...+dk-1dk.

(a) Bizonyítsuk be, hogy D<n2.
(b) Határozzuk meg az összes olyan n számot, amire D osztója n2-nek.
 
 


Kovács Erika Renáta megoldása. (a) Becsüljük felülről a didi+1 szorzatokat. Mivel d1=1 és di<di+1, azért i≤di. Miután pedig az osztópárokra n=djd(k+1)-j teljesül, ha 1≤j≤k, így
dj=nd(k+1)-j≤nk+1-j.
Ebből következik, hogy
didi+1≤nk+1-i⋅n(k+1)-(i+1)=n2(k-i+1)(k-i).
Ha összegezzük ezeket az egyenlőtlenségeket, akkor azt kapjuk, hogy
D≤n2(1k(k-1)+1(k-1)(k-2)+...+13⋅2+12⋅1).(1)
Mivel 1(j+1)j=-1j+1+1j, a zárójelben úgynevezett teleszkopikus összeg áll: értéke
-1k+1k-1-1k-1+1k-2-...+12-12+1=1-1k,
kisebb, mint 1 és pozitív. Ebből pedig (1) felhasználásával a bizonyítandó állítást kapjuk.
(b) Tegyük fel, hogy D∣n2. Mivel az első rész állítása szerint D=n2 nem lehetséges, ezért D valódi osztója n2-nek. Legyen az n legkisebb prímosztója p. Ekkor d2=p, tehát osztópárja, dk-1=np. A dk-1dk szorzat értéke tehát n2p és így persze D≥n2p. Mármost p választása szerint n2 legnagyobb valódi osztója éppen n2p, így ha D∣n2, akkor D=n2p=dk-1dk!
Így a k értéke 2, tehát p=d2=dk=n, az n egyenlő a legnagyobb prímosztójával, vagyis maga is prím. Az pedig nyilvánvaló, hogy ha n tetszőleges prímszám, akkor D=n, ami osztója n2-nek.
 
5. Határozzuk meg az összes olyan f függvényt, ami a valós számok R halmazát önmagába képezi és amelyre
(f(x)+f(z))(f(y)+f(t))=f(xy-zt)+f(xt+yz)
teljesül minden x,y,z,t∈R esetén.
 
 


Harangi Viktor megoldása. Helyettesítsünk az egyenletben mind a négy változó helyére u-t: azt kapjuk, hogy minden u valós számra
4f2(u)=f(0)+f(2u2).(1)
Ha most u=0, akkor 4f2(0)=f(0)+f(0)=2f(0). Innen rendezés után
f(0)(2f(0)-1)=0,
azaz vagy f(0)=0 vagy pedig f(0)=12.
Vizsgáljuk először a második esetet.
Végezzük el az eredeti függvényegyenletben az y=t=0, z=x helyettesítéseket:
(f(x)+f(x))⋅(12+12)=12+12,
ahonnan 2f(x)=1, azaz f(x)=12, erre a függvényre pedig nyilvánvalóan teljesül a feladat függvényegyenlete.
Tekintsük ezután az f(0)=0 lehetőséget.
Ha a z és a t változók helyére 0-t írunk, akkor a minden valós x, y számpárra fennálló
f(x)⋅f(y)=f(xy)(2)
egyenlőséget kapjuk, az f függvény tehát ebben az esetben multiplikatív.
Az (1) egyenlet most 4f2(u)=f(2u2) alakú, tehát ha u=12, akkor
4f2(12)=f(12),
ahonnan f(12)=0, vagy f(12)=14.
Az első esetben (2) felhasználásával kapjuk, hogy minden valós x-re
f(x)=f(12⋅2x)=f(12)⋅f(2x)=0,
az azonosan nulla függvény pedig nyilván megoldása az eredeti függvényegyenletnek.
Hátravan még a második lehetőség, az f(12)=14 eset vizsgálata (természetesen az f(0)=0 feltétellel együtt). Ekkor
14=f(12)=f(12⋅1)=f(12)⋅f(1)=14⋅f(1),
vagyis f(1)=1. (Itt és a továbbiakban az f multiplikativitását külön hivatkozás nélkül használjuk.)
A talált összefüggésből következik, hogy ha u tetszőleges nem nulla valós szám, akkor
1=f(1)=f(u⋅1u)=f(u)⋅f(1u),
tehát f(u) sem nulla. Így
f(1u)=1f(u)(3)
teljesül tetszőleges u≠0 valós számra. Legyen most az eredeti egyenletben y=t=1. Ekkor
2f(x)+2f(z)=f(x-z)+f(x+z),
azaz
f(x+z)=2[f(x)+f(z)]-f(x-z).(4)

Az eddig talált f(0)=02, f(1)=12 ‐ valamint (2), (3) és (4) ‐ kellő önbizalmat adhat az eredmény kiterjesztéséhez. Pozitív egészekre használjunk indukciót: legyen k>1 egész szám és tegyük fel, hogy az f függvény a k-nál kisebb nemnegatív egészeken a behelyettesített érték négyzetét veszi fel. Lássuk be, hogy ekkor f(k)=k2 is igaz. Valóban, (4) és az indukciós föltevés szerint
f(k)=2[f(k-1)+f(1)]-f(k-2)=2((k-1)2+1)-(k-2)2=k2.
Pozitív racionális számokra ezután (2) és (3) alapján teljesen szokványos módon
f(pq)=f(p)⋅f(1q)=f(p)f(q)=(pq)2.
Negatív számokra alakítsuk át (4)-et: írjunk x helyére 0-t: f(z)=2[f(z)]-f(-z), azaz minden z valós számra
f(-z)=f(z),(5)
f páros függvény és így eddigi eredményeink szerint minden x racionális számra f(x)=x2. A megoldás befejező részében, amint az várható, ezt terjesztjük ki a valós számok halmazára. Ehhez a talált algebrai összefüggések mellett határátmenet meggondolásokra lesz szükség.
Először ‐ egy ,,közbeiktatott lépéssel'' ‐ azt mutatjuk meg, hogy nullától különböző értékekre a függvény pozitív. Ha x > 0, akkor
f(x)=f(x⋅x)=f2(x)≥0.
Láttuk másfelől, hogy f(u)=0⇔u=0 és így f(x) pozitív, ha x > 0. Mivel pedig a függvény páros, ebből már valóban következik, hogy minden nullától különböző helyen pozitív értéket vesz föl.
Most megmutatjuk, hogy a pozitív számok halmazán az f függvény szigorúan monoton növő. Tekintsük ehhez ‐ utoljára ‐ az eredeti egyenletet és legyen ott t=x és z=y.
Azt kapjuk, hogy [f(x)+f(y)]2=f(x2+y2), ahonnan
f(x2+y2)-f(x2)=[f(x)+f(y)]2-f(x)⋅f(x)=f2(y)+2f(x)⋅f(y),
ami pedig határozottan pozitív, ha y nem nulla. Legyenek most 0≤a<b tetszőleges valós számok. Ekkor nyilván léteznek olyan x, y valós számok, amelyekre a=x2, b=x2+y2 és y≠0. A fentiek szerint ekkor f(b)-f(a)>0, tehát az f függvény valóban szigorúan monoton növő a pozitív valós számok halmazán. Így persze szigorúan monoton fogyó, ha x negatív.
A még hiányzó irracionális helyeken a mindenütt sűrűn elhelyezkedő racionális számokat használjuk fel. Ismeretes, hogy egy szigorúan monoton növő függvénynek mindenütt létezik bal-, illetve jobboldali határértéke. Ha x tetszőleges irracionális szám, akkor egy-egy x-hez balról, illetve jobbról tartó racionális számokból álló sorozaton a függvényértékek sorozata mindkét esetben x2-hez tart, hiszen racionális számokra f(u)=u2. Az f bal- és jobboldali határértéke tehát egyaránt x2-tel egyenlő az x-helyen, így mivel szigorúan monoton, az f itt folytonos és így f(x)=x2 akkor is fennáll, ha x irracionális szám.
Az adott függvényegyenlet tehát három függvényre teljesülhet; ezek:
f(x)=0,f(x)=12ésf(x)=x2.
Mindhárom függvény nyilvánvalóan kielégíti az egyenletet.
 
6. Legyenek Γ1,Γ2,...,Γn egységsugarú körök a síkban, ahol n≥3. Jelölje a középpontjaikat rendre O1,O2,...,On. Tegyük fel, hogy nincs olyan egyenes, aminek kettőnél több körrel van közös pontja. Bizonyítsuk be, hogy
∑1≤i<j≤n1OiOj≤(n-1)π4.

 
 


Csóka Endre megoldása. Először is jegyezzük meg, hogy egy egyenesnek és Γi-nek pontosan akkor van közös pontja, ha Oi legfeljebb egységnyi távolságra van az egyenestől. A feltétel tehát úgy fogalmazható, hogy nincs a síkon olyan egyenes, amelyik az O1,O2,...,On pontok közül háromtól is legfeljebb egységnyi távolságra halad. Ez azt is jelenti, hogy semelyik három középpont nincs egy egyenesen.
Jelöljük a sík egy tetszőleges P pontjának és e egyenesének a távolságát d(P;e)-vel. Ha létezne olyan három középpont, amelyekre d(Oi;OjOk)≤2 (i, j, k különbözők), akkor az OiOjOk háromszög OjOk-val párhuzamos középvonala d(Oi;OjOk)2≤1 távolságra lenne a három középpont mindegyikétől. Láttuk, hogy ezt a feltétel kizárja, azért bármelyik középpont legalább 2 egységnyi távolságra van bármely két további középponton átmenő egyenestől. Ezen az észrevételen múlik a feladat megoldása, a továbbiakban azonban még igen fáradságosan kell ,,megdolgoznunk'' azért, hogy az adott formában kapjuk meg az állítást.
Adott Ok középpontra tekintsük a további n-1 középpontnak azt a P1,P2,...,Pn-1 sorrendjét, amelyben egy az Ok körül pozitív irányba forgó egyenes áthalad rajtuk. Ez a sorrend egyértelmű, hiszen nincsen három kollineáris középpont. (Az indexelést mod (n-1) végezzük.) Legyen még αi az a legkisebb forgásszög, amellyel az OkPi egyenest az Ok körül pozitív irányban elforgatva az OkPi+1 egyenest kapjuk. (1. ábra) Ekkor az αi szögek összege nyilván π, másfelől d(Pi+j;Ok,Pi)>2 miatt sinαi>2OkPi. A minden pozitív számra fennálló x>sinx egyenlőtlenséget is felhasználva kapjuk, hogy
π=∑i=1n-1αi>∑i=1n-1sinαi>∑i=1n-12OkPi,
tehát
 
 

 1. ábra 2. ábra 
 

π2>∑i=1n-11OkPi=∑1≤i≤ni≠k1OkOi.(1)
Ha Ok a középpontok konvex burkának βk külsőszögű pontja (2. ábra), akkor jelölje Ps és Ps+1 a konvex burok Ok-val szomszédos csúcsait. (Ezek különbözők, hiszen n≥3.) Ekkor nyilván βk=αs. Az Ok-n átmenő PsPs+1 egyenessel párhuzamos e egyenesre legyenek αs;1 és αs;2 rendre az e és az OkPs illetve az e és az OkPs+1 egyenesek által bezárt szögek közül azok, amelyek összege αs. Mivel
2<d(Ok;PsPs+1)=d(Ps;e)=d(Ps+1;e),
azért
π-αs;2=αs;1+∑1≤i≤n-1i≠sαi>sinαs;1+∑1≤i≤n-1i≠ssinαi>∑i=1n-12OkPi.
Ugyanezt a becslést a másik körüljárás szerint is elvégezve π-αs;1>∑i=1n-12OkPi adódik. Adjuk össze ezt a két egyenlőtlenséget:
2π-(αs;1+αs;2)=2π-βk>∑i=1n-14OkPi,
azaz
π2-βk4>∑i=1n-11OkPi.(2)
Összegezzük végül a középpontok konvex burkának belső pontjaira az (1), a csúcsaira pedig a (2) becslést:
n⋅π2-∑konvex burokβk4=nπ2-2π4=(n-1)π2>2∑1≤i<j≤n1OiOj,
ahonnan 2-vel osztva éppen a bizonyítandó állítást ‐ pontosabban annak egy élesebb formáját ‐ kapjuk.