Cím: Az 52. Nemzetközi Matematikai Diákolimpia feladatainak megoldásai
Füzet: 2011/október, 386 - 394. 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; lényegében ú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. Az A={a1,a2,a3,a4} halmaz négy, páronként különböző pozitív egész számból áll. Az a1+a2+a3+a4 összeget jelöljük sA-val, és jelölje nA az olyan (i,j) párok (1i<j4) számát, amelyekre ai+aj osztója sA-nak.
Határozzuk meg az összes olyan A halmazt, amelyre nA a lehetséges maximális értékét veszi fel.

 
Janzer Olivér megoldása. Szimmetria miatt feltehetjük, hogy a1<a2<a3<a4.
Először belátjuk, hogy nA4.
Mivel a2+a4>a1+a3, tehát a2+a4>12sA, így nem lehet osztója sA-nak (hiszen a2+a4<sA). Hasonlóan a3+a4>a1+a2, tehát a3+a4>12sA, így ez sem lehet osztó.
Tehát csak az (a1,a2), (a1,a3), (a1,a4), (a2,a3) párok jöhetnek szóba, azaz legfeljebb 4 pár. Nézzük meg, ennyi mikor lesz. Mivel (a1+a4) és (a2+a3) is osztó, azért (a1+a4)12sA és (a2+a3)12sA, így (a1+a2+a3+a4)sA. Az egyenlőségnek kell teljesülni: (a1+a4)=(a2+a3)=12sA.
(a1+a3) is osztja sA-t, ezért (a1+a3)13sA, hiszen (a1+a3)<(a2+a3)12sA. Tegyük fel, hogy (a1+a3)14sA.
14sA=12(12sA)=12(a2+a3),
így
a1+a312(a2+a3)2a1+2a3a2+a32a1+a3a2,
ami a3>a2 miatt ellentmondás. Így 14sA<(a1+a3)13sA, tehát (a1+a3)=13sA.
Mivel a1+a4=a2+a3, a4=a2+a3-a1,
a1+a3=13sA=13(a1+a2+a3+a4)=13(a1+a2+a3+(a2+a3-a1))==13(2a2+2a3).
Így 3a1+3a3=2a2+2a3, tehát a3=2a2-3a1,
a4=a2+a3-a1=a2+(2a2-3a1)-a1=3a2-4a1.
(a1+a2) is osztója sA-nak, de (a1+a2)<(a1+a3)=13sA, tehát (a1+a2)14sA. Tegyük fel, hogy (a1+a2)16sA. Ekkor
(a1+a2)16(a1+a2+(2a2-3a1)+(3a2-4a1))=16(6a2-6a1)=a2-a1,
amiből 2a10, ami a1 pozitív volta miatt ellentmondás.
Tehát 16sA<(a1+a2)14sA, így két eset maradt:
1)
a1+a2=14sA=14(a1+a2+(2a2-3a1)+(3a2-4a1))=14(6a2-6a1).
Így 4a1+4a2=6a2-6a1, tehát 10a1=2a2, azaz a2=5a1. Ekkor a3=2a2-3a1=7a1, a4=3a2-4a1=11a1. Ezek valóban jók, ha a1 pozitív egész, hiszen sA=24a1, és a1+a2=6a1, a1+a3=8a1, a1+a4=12a1, a2+a3=12a1, amik valóban osztók.
2)
a1+a2=15sA=15(6a2-6a1),5a1+5a2=6a2-6a1,
a2=11a1, a3=19a1, a4=29a1. Így sA=60a1 és a1+a2=12a1, a1+a3=20a1, a1+a4=30a1, a2+a3=30a1, amik valóban osztók.
Tehát az olyan A halmazok a megfelelők, ahol A={a,5a,7a,11a} vagy A={a,11a,19a,29a} és a pozitív egész.

 
2. Legyen S a sík pontjainak egy véges, legalább kételemű halmaza. Feltesszük, hogy az S halmaz semelyik három pontja sincs egy egyenesen.
Egy szélmalomnak nevezett folyamat során kiindulunk egy  egyenesből, amely az S halmaznak pontosan egy P pontját tartalmazza. Az egyenes a P forgástengely körül az óramutató járásával megegyező irányban forog addig, amíg először nem találkozik egy másik, S halmazba tartozó ponttal. Ekkor ez a Q pont lesz az új forgástengely, és az egyenes a Q pont körül forog tovább az óramutató járásával megegyező irányban egészen addig, míg újra nem találkozik egy S halmazba tartozó ponttal. Ez a folyamat vég nélkül folytatódik.
Bizonyítsuk be, hogy megválaszthatjuk a PS pontot és a P-n átmenő  egyenest úgy, hogy az S halmaz minden pontja végtelen sokszor lesz a szélmalom forgástengelye.

 
Dankovics Attila megoldása. 1. lemma. a) A folyamatban megmarad az adott oldalon lévő pontok száma két olyan állapot közt, amikor csak egy pont van az egyenesen.
Bizonyítás. A régi forgástengely a forgó egyenesnek ugyanarra az oldalára kerül, mint amelyik oldalán az új forgástengely volt.

 
b) Az 1. lemma hasonlóan belátható két olyan állapotra, amikor két pont van az egyenesen.
 
2. lemma. Minden ponton megy át olyan egyenes aminek két oldalán ugyanannyi pont van.
 
Bizonyítás. Veszünk egy egyenest át a ponton, és kitüntetjük az egyik oldalát. Legyen a kitüntetett oldalon k-val több pont (feltehetjük, hogy k pozitív, illetve ha 0, akkor készen vagyunk). Megforgatjuk az egyenest 180 ponttal, ekkor a kitüntetett oldalon k-val kevesebb pont lesz. Mivel nincs 3 pont egy egyenesen, a két oldalon lévő pontok különbsége forgatás közben egyszerre legfeljebb 1-gyel változik. Mivel pozitívból negatívba megy, közben valamikor 0 lesz.
 
Megoldás. Páratlan sok pont esetén tetszőleges kiindulópontból megfelelő szélmalmot eredményez minden olyan egyenes, amelynek két oldalán ugyanannyi pont van. Ha a pontok száma páros, akkor (egy ilyen egyenest egészen kicsit elforgatva) válasszuk meg -et úgy, hogy az előbbi feltétel az első találkozáskor teljesüljön.
 
Bizonyítás. Az egyenes iránya körbe fog forogni, eközben az első lemma alapján a két oldalán lévő pontok számának különbsége végig 0 vagy 1. Egy teljes körbefordulás során egy tetszőleges P ponton biztosan átmegy akkor, amikor éppen olyan irányú, hogy a P-re illeszkedő ilyen irányú f egyenesnek ugyanannyi pont van mindkét oldalán. (Ilyen egyenes a 2. lemma szerint valóban létezik.)
Tegyük fel ugyanis, hogy az e egyenesünk ilyen irányú, de nem megy át P-n ‐ ugyanakkor tartalmazza a halmaz egy Q pontját. Az f-et nemnulla eltolás viszi e-be, melynek eredményeként eltávolodik P-től, és rákerül a Q. Így az e  P-t tartalmazó oldalán legalább kettővel több pont lenne, mint a másikon, ami ellentmondás.
Ezzel a feladatot megoldottuk.
 
3. Legyen f:RR egy olyan függvény, amelyre teljesül az
f(x+y)yf(x)+f(f(x))
feltétel minden x, y valós számra. Bizonyítsuk be, hogy minden x0 esetén teljesül f(x)=0.

 
Kalina Kende megoldása. Az f(x+y)yf(x)+f(f(x)) egyenlőtlenségből y=0 helyettesítéssel:
f(x)f(f(x)).(1)

Ha van olyan a, amelyre f(a)=0, akkor
f(b+a)bf(a)+f(f(a))=f(0).
Mivel a+b minden valós értéket felvesz, minden c-re teljesül:
f(c)f(0),(2)
speciálisan f(f(0))f(0). Innen (1) miatt f(0)=f(f(0)). Ezt felhasználva:
f(0)=f(f(0)-f(0))-f(0)2+f(f(0)).
Mivel így 0-f(0)2, ebből f(0)=0.
Legyen k<0,
0=f(k-k)-kf(k)+f(f(k)),ígykf(k)f(f(k)).

(2) alapján a jobb oldal kisebb vagy egyenlő, mint 0, így a bal oldal is. Mivel k<0, és (2) alapján f(k)0, így f(k)=0 lehet csak.
Tehát, ha találunk egy gyököt, az állítás igaz. Így a továbbiakban indirekt felteszem, hogy f(x)0 minden x-re. Alkalmazzuk a következő helyettesítést:
f(q)(q-r)f(r)+f(f(r)),f(q)qf(r)-rf(r)+f(f(r)).

(3) Ebből látszik, hogy ha van olyan r, amelyre f(r)>0, akkor f(q) mindig negatív, amennyiben q kisebb egy adott Q értéknél. Ha nincs ilyen r, akkor ugyanez bármilyen Q-ra igaz.
Legyen y=f(x)-x; ekkor:
0(f(x)-x)f(x),azazxf(x)f(x)2.

(4) Innen a függvény negatívakon felveheti a következő értékeket: pozitív valósak, abszolút értékben x-nél nagyobb vagy egyenlő (tehát x-nél kisebb vagy egyenlő) negatív valósak.
Legyen h a (3) szerinti Q-nál kisebb negatív valós szám. Ekkor f(h)h; és f(f(h))f(h). Viszont (1) miatt f(h)f(f(h)), így f(h) fixpont. Illetve egy másik, j<f(h)-ra f(j)=j<f(h) is fixpont.
Az eredeti egyenlőtlenséget a negatív a<b fixpontokból képzett a és b-a számokra felírva:
f(a+(b-a))(b-a)f(a)+f(f(a)),b(b-a)a+a,b-a(b-a)a.
Mivel a<b, azaz b-a>0, ebből 1a, ami ellentmondás. Tehát a megoldás első fele szerint következik a feladat állítása.

 
4. Legyen n>0 egy egész szám. Van egy kétkarú mérlegünk és n súlyunk, amelyek súlya 20, 21,...,2n-1. Ezt az n súlyt egymás után a mérlegre akarjuk helyezni oly módon, hogy a jobboldali serpenyő soha ne legyen nehezebb a baloldali serpenyőnél. Mindegyik lépésben kiválasztjuk az eddig a mérlegre nem tett súlyok valamelyikét, és a mérlegnek vagy a baloldali vagy a jobboldali serpenyőjébe helyezzük, egészen addig, amíg az összes súly fel nem kerül a mérlegre.
Határozzuk meg, hogy hányféleképpen lehet ezt megtenni.

 
Damásdi Gábor megoldása. N darab súlyt 135...(2n-1)-féleképpen lehet jól felrakni a mérlegre. Ezt indukcióval látjuk be: n=1 és n=2 könnyen ellenőrizhető. Tegyük fel, hogy valamilyen n-re 135...(2n-1)-féle jó felrakás van. Azt kell belátnunk, hogy n+1 súlyt 2n+1-szer annyi módon rakhatunk fel, mint n súlyt.
Vegyük az n súlynak egy tetszőleges felrakását. A következő módon csinálunk belőle egy felrakást n+1 súlyra: minden elem tömegét megkétszerezzük, majd valahova beszúrunk még egy lépést, amiben egy 1 tömegű súlyt helyezünk fel.
A kétszerezés miatt megkapjuk a 2,4,...,2n tömegű súlyokat, és beszúrjuk az 1 tömegűt, tehát ez tényleg n+1 súly felrakása. A kétszerezés nem rontja el a nagyságviszonyt. Mivel a kétszerezés után a tömegek párosak, az 1 tömegű súly csak akkor rontja el a felrakást, ha legelőre szúrjuk be és a jobb oldalra rakjuk. Tehát egy esetet kivéve, bármikor bármelyik oldalra felrakhatjuk az 1 tömegű súlyt, így 2n+1 darab felrakást készítettünk n+1 súlyra. Ezután elég belátni, hogy ezzel a módszerrel minden felrakás elérhető n+1 súlyra és egyik se érhető el kettő különböző n súlyos felrakásból.
Minden felrakás elérhető n+1 súlyra, mivel visszafelé is megadhatjuk a módszert: vegyünk egy felrakást n+1 súlyra. Vegyük ki azt a lépést, amiben az 1 tömegű súlyt rakjuk fel, és osszuk el a tömegeket 2-vel. Így egy felrakást kapunk n súlyra, amiből elérhető a kiinduló felrakás n+1 súlyra.
Ha különböző felrakásokból indulunk ki, a 2,4,...,2n tömegű súlyok más sorrendben lesznek az n+1 súlyos felrakásban, azaz minden felrakást csak egy módon érhetünk el.
Minden felrakásból készítettünk 2n+1 felrakást n+1 súlyra, tehát beláttuk az indukciót.

 
5. Jelölje Z az egész számok halmazát, N pedig a pozitív egész számok halmazát. Legyen f egy Z-t N-be képező függény. Tegyük fel, hogy bármilyen két m és n egész szám esetén az f(m)-f(n) különbség osztható f(m-n)-nel.
Bizonyítsuk be, hogy minden m, n egész számra teljesül az, hogy ha f(m)f(n), akkor f(n) osztható f(m)-mel.

 
Nagy Donát megoldása. (1) Az n helyébe 0-t írva f(m)f(m)-f(0), így f(m)f(0) minden m-re.
(2) m helyébe 0-t írva f(-n)f(0)-f(n), innen (1) miatt f(-n)f(n) minden n-re;
(3) és itt n helyébe -n-et írva f(n)f(-n), de mivel f(n) és f(-n) is pozitív egész, azért f(n)=f(-n) minden n-re.
A bizonyítandó állítás lényegében az, hogy f értékkészletének bármely két eleme közül egyik osztója a másiknak. Legyenek a és b tetszőleges egészek, ekkor m helyébe a-t, n helyébe b-t írva f(a-b)f(a)-f(b), illetve m helyébe a-t, n helyébe (a-b)-t írva f(a-(a-b))=f(b)f(a)-f(a-b), végül m helyébe (b-a)-t, n helyébe b-t írva f((b-a)-b)=f(-a)f(b-a)-f(-b). (3) felhasználásával ezek azt adják, hogy az f(a), f(b) és f(a-b) pozitív egészek közül bármely kettő különbsége osztja a harmadikat. Ha az x, y, z pozitív egészek közül bármely kettő különbsége osztja a harmadikat és például x az egyik legnagyobb közülük, akkor -x-z<y-z<yx, de így mivel x(y-z), azért y-z=0, y=z és ekkor y(z-x)-ből y=zx adódik, így ekkor x, y és z közül bárhogyan választunk kettőt, egyikük osztani fogja a másikat. Ezt az f(a), f(b), f(a-b) hármasból f(a)-t és f(b)-t választva alkalmazva adódik a feladat állítása, hiszen a és b tetszőleges egészek voltak.

 
6. Legyen ABC egy hegyesszögű háromszög, Γ a háromszög körülírt köre és  Γ egy érintőegyenese. Jelölje a, b, c azokat az egyeneseket, amelyeket úgy kapunk, hogy -et a BC, CA, illetve AB egyenesekre tükrözzük.
Bizonyítsuk be, hogy az a, b, c egyenesek által meghatározott háromszög körülírt köre érinti a Γ kört.

 
Nagy János megoldása. Legyenek az b, c és a egyenesek által meghatározott háromszög csúcsai rendre A', B' és C'; és legyen az A'B'C' háromszög körülírt köre Γ', ekkor azt kell igazolnunk, hogy Γ' és Γ körök érintik egymást.
A Γ kör és az A'B'C' háromszög, illetve Γ' kör között csak gondolati kapcsolat van eddig, kell valami, ami fizikaivá teszi. Ehhez vegyük észre, hogy az A'B'C' háromszög beírt körének I középpontja rajta van a Γ körön és ráadásul az IA, IB, IC egyenesek átmennek rendre az A', B' és C' pontokon.
 
 

Ezt az állításunkat nem fogjuk bebizonyítani, mert nincs is rá szükség, elég ha tudjuk intuitívan, hogy ez igaz. Legyenek az ABC háromszög szögei α, β, γ, amik tehát hegyesszögek.
Most a következőt fogjuk belátni: Legyen A'B'C' egy háromszög, melynek szögei
180-2α,180-2βés180-2γ,
ennek körülírt köre k', beírt körének középpontja I, és k egy olyan kör, ami átmegy az I ponton, és érinti a k' kört. A k kör és az IA', IB', IC' egyenesek második metszéspontja A, B és C. Ekkor az AB egyenesre tükrözve az A'B' egyenest, a BC egyenesre tükrözve a B'C' egyenest és a CA egyenesre tükrözve a C'A' egyenest, ugyanazt az egyenest kapjuk, ami ráadásul érinti a k kört.
Egyrészt belátjuk ezt az állítást, másrészről megmutatjuk, hogy ebből következik a feladat állítása:
Először is ebben a helyzetben az ABC háromszög szögei α, β és γ, mert a k körben a kerületi szögek tétele miatt a háromszög szögei megegyeznek az A'B'C' háromszög szögfelezőinek egymással bezárt szögeivel, amik éppen α, β és γ.
Most tekintsük a fix A'B' egyenes AB egyenesre való tükörképét.
Ha a k kör helyzetét közben változtatjuk, akkor könnyen látható, hogy az AB egyenes minden irányt fel fog venni k összes helyzetét tekintve, mert minden irányhoz tudunk találni olyan kört, amely átmegy I-n, és akkor ezt hasonlósággal át tudjuk vinni olyanba, ami érinti a k' kört.
Így tehát az AB egyenes és a tükörkép szöge is tetszőleges lehet, az egyéb diszkussziós meggondolásokat most mellőzzük.
 
 

Van tehát olyan helyzete a k körnek, amelyre az A, B, C és a közös tükörképek érintési pontja a k körrel; e négy pont által meghatározott négyszög hasonló az eredeti feladatban levő ABCP négyszöghöz. De ekkor a hasonlóság az eredeti feladat két körét az itteni k és k' körökbe viszi, amik érintik egymást, tehát ekkor készen lennénk.
Most tehát igazoljuk az állításunkat. Az, hogy a tükörképek érintik a k kört, szimmetrikus állítások, így elég közülük az egyiket igazolni, mi az A'B' egyenes tükörképével tesszük ezt.
Ehelyett azt látjuk be, hogy ha az AB egyenesre tükrözzük a k kört, akkor az érinti az A'B' egyenest valamilyen X pontban, ami természetesen ekvivalens átfogalmazás.
Azt kell észrevenni még, hogy ez az X pont rajta lesz az A'AT háromszög, illetve a B'BT háromszög körülírt körén is.
Tehát megmutatjuk, hogy az A'AT háromszög, illetve a B'BT háromszög körülírt köre az A'B' egyenesen metszi egymást, utána pedig belátjuk, hogy ez az X metszéspont rajta van a tükrözött körön, sőt érintési pont is egyben.
Először is lássuk be, hogy az A'AT háromszög, illetve a B'BT háromszög körülírt köre az A'B' egyenesen metszi egymást, tegyük fel hogy az első kör metszéspontja az A'B' egyenessel X1, a másodiké pedig X2; azt akarjuk belátni, hogy X1=X2.
Ehhez az kell, hogy
TX1A'+TX2B'=180,
de
TX1A'+TX2B'=TAA'+TBB'=IAT+180-IBT=180,
ahol végig a kerületi szögek tételét használtuk.
Legyen tehát X=X1=X2, belátjuk, hogy X rajta van az AB-re tükrözött k körön; ehhez azt kell igazolnunk, hogy
AXB=180-ATB=180-AIB=180-γ,
de
AXB=180-AXA'-BXB'=180-ATA'-BTB'==180-γ-ATA'-BTB'+γ=180-γ.
Felhasználtuk, hogy A'TB'C' húrnégyszög.
Ezzel megkaptuk, hogy X rajta van a tükrözött körön is, még az kell, hogy érintési pont is egyben.
Ehhez invertáljuk az ábrát a T pontból, ekkor a képábrán A, A' és X képei egy egyenesen lesznek, és B, B' és X képei is egy egyenesen lesznek az inverzió szabályai szerint.
Ezen kívül AB képe párhuzamos lesz A'B' képével, mert az eredeti ábrán az ABT kör érinti az A'B'T kört, így tehát a képábrán az XAB és XA'B' háromszögek hasonlóak, tehát körülírt körük érintik egymást.

 
 

Ezeknek a köröknek az ősképei az AXB kör, illetve az A'B' egyenes, mert A', X és B' egy egyenesen vannak az eredeti ábrán, ezért az inverzió szögtartása miatt az A'B' egyenes az eredeti ábrán valóban érinti az AXB körülírt körét, vagyis a tükrözött kört.
Ezzel bebizonyítottuk, hogy ha az AB egyenesre tükrözzük az A'B' egyenest, akkor a kép érinti a k kört, és ugyanígy a többi csúcspárra is, már csak azt kéne belátni, hogy ez az érintési pont mind a három alkalommal ugyanaz lesz.
Legyen az A, B csúcspárra ez az érintési pont E1, a B, C csúcspárra pedig E2, ekkor a szimmetria miatt elég belátni hogy E1=E2, és akkor mindhárom érintési pontnak meg kell egyeznie.
Tehát tudjuk, hogy XAB=BXB' az érintő szárú kerületi szögek tétele miatt, és akkor a bizonyítottak szerint E1AB=XAB=BXB'=BTB'.
Teljesen szimmetrikusan E2AB=E2CB=BTB', abból pedig akkor az E1 és E2 pontnak meg kell egyezni, vagy tükrösnek kell lennie az AB egyenesre; de ezt mindegyik Ei, Ej párra elmondhatjuk a szimmetria miatt és akkor ez már csak tényleg úgy lehet, hogy ha az E1, E2, E3 pontok megegyeznek: ha közülük semelyik kettő nem egyezne meg, akkor a felező merőlegeseik egy ponton mennének át, de ez az AB, AC, BC oldalakra nyilván nem teljesül. Ha pedig kettő megegyezik, a harmadik meg más, akkor két felező merőleges teljesen megegyezne, ami megint csak nem teljesülhet két oldalra.
Így tehát igazoltuk az állításunkat, és ‐ mint azt korábban megmutattuk ‐ ezzel bizonyítottuk az eredeti feladat állítását is.