Cím: A 41. Nemzetközi Matematikai Diákolimpia feladatainak megoldása
Füzet: 2000/október, 386 - 393. oldal  PDF file
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 idén is közöljük a nyári matematikai diákolimpia feladatainak a megoldását ú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 szerk.


 
1. A Γ1 és Γ2 körök az M és N pontokban metszik egymást.
Legyen a Γ1 és Γ2 köröknek az a közös érintője, amelyre teljesül, hogy M közelebb van -hez, mint N. Érintse  Γ1-et az A és Γ2-t a B pontban. Legyen az M-en átmenő, -lel párhuzamos egyenes másik metszéspontja a Γ1 körrel C, a Γ2 körrel pedig D.
A CA és DB egyenesek metszéspontja legyen E; az AN és CD egyenesek metszéspontja legyen P; a BN és CD egyeneseké pedig legyen Q.
Bizonyítsuk be, hogy EP=EQ.

 
Megoldás. Tekintsük az ábrát, jelölje F az AB és MN egyenesek metszéspontját. Mivel F rajta van az MN hatványvonalon, az F pontból a Γ1 és Γ2 körökhöz húzott érintőszakaszok hossza egyenlő. Ezek az érintőszakaszok az FA, illetve FB, így FA=FB.
1. ábra

Továbbá a párhuzamos szelők tétele szerint (PQAB):
MPMQ=FAFB=1,vagyisMP=MQ.

Másrészt, ABCD miatt EAB=ECD, valamint a kerületi és érintőszárú kerületi szögek egyenlőségéből ECD=BAM. Következésképpen EAB=BAM, és hasonlóan kapjuk, hogy EBA=ABM.
Ezekből viszont az következik, hogy az AMBE négyszög deltoid. Emiatt EMAB, azaz EMPQ. És ezzel készen vagyunk, ugyanis az EMP és EMQ derékszögű háromszögek EM befogója közös, és a másik befogójuk is egyenlő (MP=MQ). Tehát egybevágó a két háromszög, amiből EP=EQ.
 Harangi Viktor (Fazekas M. Főv. Gyak. Gimn., 10., o.t.)

 
2. Legyenek a, b, c olyan pozitív valós számok, amelyekre abc=1 teljesül. Bizonyítsuk be, hogy
(a-1+1b)(b-1+1c)(c-1+1a)1.

 
Megoldás. Ha a 3 szorzótényező közül egy vagy három negatív, akkor a szorzat negatív, vagyis kisebb 1-nél. Ha valamelyik tényező 0, akkor a szorzat is 0, szintén kisebb 1-nél. Pontosan két tényező nem lehet negatív, mert ha például a-1+1b<0 és b-1+1c<0 lenne, akkor az összegük
0>a-1+1b+b-1+1c=(b-2+1b)+a+1c=(b-1)2b+a+1c>0,
mert a, b, c>0, ez nem lehet.
Tehát az az eset marad, amikor mindhárom szorzótényező pozitív.
(a-1+1b)(b-1+1c)=ab-a+ac-b+1-1c+1-1b+1bc==1c-a+ac-b+1-1c+1-1b+a=ac-b+2-1b=ac-(b-1)2bac,
ugyanígy a másik 2-2 tényezőre. Mindhárom tényező pozitív, tehát
(a-1+1b)(b-1+1c)(c-11a)==(a-1+1b)(b-1+1c)(b-1+1c)(c-1+1a)(c-1+1a)(a-1+1b)acbacb=1,
ezt akartuk bizonyítani.
 Győri Nikolett (Fazekas M. Főv. Gyak. Gimn., 12. o.t.)

 
3. Legyen n2 pozitív egész szám. A kiinduló állásban n bolha ül egy vízszintes egyenesen, nem mind ugyanabban a pontban.
Egy λ pozitív valós számra definiáljunk egy lépést a következőképpen:
*válasszunk ki két bolhát, amelyek az A és B pontokban ülnek, ahol A balra van B-től;
*ugorjon az A-n lévő bolha az egyenesnek abba a C pontjába, ami jobbra van B-től, és amelyre BC/AB=λ teljesül.

Határozzuk meg az összes olyan λ értéket, amelyre teljesül, hogy akárhogyan választva az M pontot az egyenesen, és akárhogyan választva az n bolha kiindulási pozícióját, létezik lépéseknek egy olyan véges sorozata, amelyek végrehajtása után az összes bolha M-től jobbra helyezkedik el.

 
Megoldás. Az egyszerűség kedvéért nevezzük a bolhákat pontoknak. Először azt mutatjuk meg, hogy λ1n-1-re az állítás mindig igaz. Azt mutatjuk meg, hogy akármilyen messzire eljuthatnak a pontok, ha mindig a legbalra esővel átugorjuk a legjobbra esőt. Ebben az esetben egy mohó algoritmus eljuttatja a pontokat M-en túlra. Az első n-1 lépésben minden pont különböző helyre kerül, ezt tekinthetjük a továbbiakban kiindulóhelyzetnek. Jelölje itt a szomszédos pontok közötti távolságot rendre d1, d2, ..., dn-1. Egy ugrás után az új távolságok: d2, d3, ..., dn-1, (d1+d2+...+dn-1)λ. Mivel
(d1+d2+...+dn-1)λd1+d2+...+dn-1n-1min(d1,...,dn-1),
azért a legkisebb távolság változatlan marad. Jelölje ezt d. A legjobbra fekvő pont így minden lépésben legalább d-vel jobbra kerül. Mivel d>0, azért egy idő után akármilyen messzire eljut. Ezután n-1 lépésben a többi pont is M-en túlra jut, és ezt akartuk bizonyítani.
Most megmutatjuk, hogy ha λ<1n-1, akkor semelyik kiindulóhelyzetből sem lehet akármilyen messzire eljutni. Minden ponthoz rendeljünk hozzá ugyanis egy számot úgy, hogy az egyenest a számegyenesnek tekintjük. Legyen sk a k-adik lépés után a pontoknak megfelelő számok összege, wk pedig a számok legnagyobbika. Nyilván sknwk. Ha bebizonyítanánk, hogy wk korlátos, akkor készen lennénk, mert így egy pont sem juthatna át egy bizonyos M-en (a korláton) túlra. Ugorja át A a (k+1)-edik lépésben B-t és ezzel kerüljön C-be. Az értelemszerű jelölésekkel ebből:
sk+1=sk+c-a,c-b=λ(b-a),
ezt átrendezve λ(c-a)=(1+λ)(c-b). Tehát sk+1=sk+1+λλ(c-b).
Most igazoljuk, hogy
sk+1-sk=1+λλ(c-b)1+λλ(wk+1-wk).
bwk, tehát ha cwk+1, akkor ez valóban igaz. Ha pedig c<wk+1, akkor wk+1=wk, hiszen a legjobbra eső pont nem változhatott másra, mint c-re. Ekkor az egyenlőtlenség nyilvánvaló.
Tehát sk+1-sk1+λλ(wk+1-wk). Vagyis 1+λλwk-sk1+λλwk+1-sk+1.
Mivel λ<1n-1, azért 1+λ>nλ, amiből 1+λλ-n>0. Legyen μ=1+λλ-n. Ekkor
1+λλwk-sk=μwk+(nwk-sk)μwk,
Ezek szerint wk1+λλw1-s1μ, tehát wk korlátos, készen vagyunk.
Így a megoldás: λ1n-1.
 Pálvölgyi Dömötör (Fazekas M. Főv. Gyak. Gimn., 12. o.t.)

 
4. Egy bűvésznek száz kártyája van, amelyek 1-től 100-ig vannak számozva. Mindegyiket beleteszi három doboz ‐ egy piros doboz, egy fehér doboz és egy kék doboz ‐ valamelyikébe, olymódon, hogy mindegyik dobozban van legalább egy kártya.
A közönség egy tagja kiválaszt kettőt a három doboz közül, és mindegyikből kivesz egy kártyát, majd kihirdeti a kivett kártyákon lévő két szám összegét. Ennek az összegnek az ismeretében a bűvész meg tudja mondani, hogy melyik az a doboz, amiből nem vettek ki kártyát.
Hányféleképpen lehet a kártyákat a dobozokban úgy elhelyezni, hogy ez a mutatvány mindig sikerüljön? (Két elhelyezést különbözőnek tekintünk, ha van legalább egy kártya, ami másik dobozba kerül.)

 
Megoldás. Legyen a három doboz A, B és C.
A={a1<a2<...<ak},B={b1<b2<...<bl},C={c1<c2<...<cm},(k+l+m=100).
Vegyük a következő összegeket:
{a1+b1<a1+b2<...<a1+bl<a2+bl<...<ak+bl}{a1+c1<a1+c2<...<a1+cm<a2+cm<...<ak+cm}{b1+c1<b1+c2<...<b1+cm<b2+cm<...<bl+cm}
(az egyenlőtlenségek az eredeti egyenlőtlenségekből következnek).
Mivel két csoportban nem lehet ugyanolyan összeg, azért van k+l-1+k+m-1+l+m-1=2(k+l+m)-3=197 különböző számunk. Az 1‐100 számokból éppen ennyi, 197 különböző kéttagú összeg készíthető (1+2=3, ...99+100=199), ezért az összes szám szerepel. Ezután esetvizsgálattal nézzük meg a lehetőségeket:
Kezdjük feltölteni a dobozokat. Vegyük észre, hogy mivel a 3 összeg létrejön, az 1 és a 2 kártya különböző dobozokba kerül. Ezt a két kártyát összesen hatféleképpen rendezhetjük el. Tegyük fel, hogy az 1 kártya az A, a 2 pedig a B dobozba került. A 3 kártya ezután nem kerülhet az A dobozba, ellenkező esetben ugyanis a 4 összeg nem jöhet létre. A 3 kártya tehát vagy a B dobozba került ‐ ahová a 2 ‐ vagy pedig az eddigi üres C dobozba. Azt állítjuk, hogy a további kártyák elhelyezése mindkét esetben egyértelmű.
1. eset (a 3 kártya a B dobozba kerül):
 
2. ábra

* a C doboz nem üres, így legyen a legkisebb C-beli kártya k. Ekkor k+1 csak az A-ba kerülhet, hiszen különben 2+k=(k+1)+1, a bűvész nem tud dönteni.
Ám ekkor (k+1)+2=k+3, a bűvész most sem tud dönteni, hacsak k+1 kártya már egyáltalán nincsen. Így ,,nem létezhet'' k+1, tehát k=100. Ekkor az A és C dobozban egy-egy kártya van, az 1, illetve a 100, a többiek a B dobozba kerülnek. Ez az elrendezés pedig nyilván megfelelő, így tehát hat esetet kaptunk.
2. eset (a 3 kártya a C dobozba kerül):
 
3. ábra

*2+3=4+1, 4A
5+1=4+2 tehát 5C, és 5+2=4+3, tehát 5A. Így 5B. Hasonlóan
6+1=4+3, így 6B, továbbá 6+2=5+3, azért 6A. Így csak 6C lehetséges.
Az első sort elhagyva ezt ,,eljátszva'' a második sorral kapjuk, hogy a számok 3-as maradék szerint vannak rendezve, és ez az elrendezés is tényleg jó lesz. Ez tehát további hat eset.
Így összesen 12 olyan elrendezés van, amikor mindig sikerülhet a mutatvány.
 Vizer Máté (Fazekas M. Főv. Gyak. Gimn., 12. o.t.)

 
5. Döntsük el, hogy létezik-e olyan n pozitív egész szám, amelyre teljesül, hogy n pontosan 2000 különböző prímszámmal osztható, és 2n+1 osztható n-nel.
 
Megoldás. Belátjuk, hogy minden pozitív egész k-hoz található olyan pozitív egész n úgy, hogy (2n+1) osztható n-nel, és n-nek pontosan k darab prímosztója van. 
(Így k=2000-re is létezik ilyen n.)
k szerinti teljes indukcióval bizonyítjuk az állítást. k=1-re igaz: 929+1.
k=2-re: 9192919+1.
Tegyük fel, hogy k-ra igaz (k2):
p12p2p3...pk2p12p2p3...pk+1,p1=3<p2=19<p3<...<pk.

Segédtétel. Ha p>3 prím, akkor (2p+1)-nek van p-nél nagyobb prímosztója.
Bizonyítás. Legyen a q a (2p+1)-nek egy p-nél nem nagyobb prímosztója. Ekkor q>2 és
2p-1(modq).Négyzetre emelve22p1(modq).
A kis Fermat-tétel szerint 2q-11(modq). Innen az euklideszi algoritmus alkalmazásával kapjuk, hogy 2(2p,q-1)1(modq). pq-1, mert q-1<p, így (2p,q-1)=2
22=41(modq),tehátq=3.

Másrészt 92p+1, mert egyébként 22p1(mod9) és 261(mod9) miatt 2(6,2p)1(mod9) az euklideszi algoritmus miatt, ami 221(mod9), és ez ellentmondás.
Ha tehát (2p+1)-nek nincs p-nél nagyobb prímosztója, akkor 2p+13, ami ellentmondás. Ezzel a segédtételt beláttuk.
Legyen ezután pk+1 a segédtétel szerinti prím, tehát pk+1>pk, és pk+12pk+1.
2pk-1(modpk+1),és így2p12p2p3...pkpk+1(-1)p12p2p3...pk-1pk+1=-1(modpk+1),azazpk+12p12p2p3...pkpk+1+1.
Másrészt az indukciós feltevés miatt p12p2...pk2p12p2...pk+1, tehát
2p12p2...pk-1(modp12p2...pk).2p12p2...pkpk+1(-1)pk+1=-1(modp12p2...pk).p12p2...pkpk+12p12p2...pkpk+1+1,
mert p12p2...pk és pk+1 relatív prímek. Így k+1-re n=p12p2...pkpk+1 megfelelő, amivel az indukciós bizonyítást befejeztük.
 Zábrádi Gergely (Győr, Révai M. Gimn., 12. o.t.)

 
6. Legyenek AH1, BH2, CH3 az ABC hegyesszögű háromszög magasságai. Az ABC háromszög beírt köre a BC, CA, AB oldalakat rendre a T1, T2, T3 pontokban érinti. Legyenek az 1, 2, illetve 3 egyenesek a H2H3, H3H1, illetve H1H2 egyenesek tükörképei a T2T3, T3T1, illetve T1T2 egyenesekre.
Bizonyítsuk be, hogy 1, 2, 3 egy olyan háromszöget határoznak meg, amelynek csúcsai az ABC háromszög beírt körén vannak.

 
Megoldás. Legyen 1i<j3 esetén ij=Qk, ahol {i,j,k}={1,2,3}. Belátjuk, hogy pl. Q1Q2 egyenese és AB egyenese párhuzamos. Ez éppen azt jelenti, hogy 3AB.
Irányított szögekkel fogunk számolni. CAB=α, ABC=β, BCA=γ. H1H2-t BC-be* (-α) szögű forgatás viszi (H2H1C=CAB, mert H1H2AB négyszög húrnégyszög: H1 és H2 rajta van az AB szakasz Thálesz-körén.)
4. ábra

T1T2-t  (-π-γ2) szögű forgatás viszi BC-be (a CT1T2 háromszög egyenlő szárú), így H1H2-t T1T2-be (-α)-(-π-γ2) szögű forgatás viszi. H1H2-t 3-ba ennek kétszerese, -2α-(-π+γ)=π-2α-γ szögű forgatás viszi. Így 3-at BC-be -(π-2α-γ)+(-α)=-π+α+γ=-β szögű forgatás viszi, amivel állításunkat igazoltuk.
A QiTi (i=1, 2, 3) egyenesek a W1W2W3 háromszöget határozzák meg.
Ezután a következőket látjuk be:
*(i)A W1W2W3 háromszög talpponti háromszöge a Q1Q2Q3 háromszög.
*(ii)A W1W2W3 háromszög középvonalai a T1T2T3 háromszöget adják.
(i) Egyszerűen adódik, hogy pl.: H1H2B=BH2H3=π2-β, ezért T2 távolsága H2H1-től és H2H3-tól megegyezik. T2 távolsága H2H1-től és 3-tól, illetve H2H3-tól és 1-től is ugyanakkora, azaz T2 egyenlő távolságra van Q2Q1 és Q2Q3-tól, így Q2T2 a Q1Q2Q3 külső szögfelezője. Hasonló áll Q3T3 és Q1T1 esetén is. Emiatt (i) valóban fennáll.
(ii) Belátjuk, hogy pl. T1T2 egyenese párhuzamos W1W2 egyenesével, azaz Q3T3-mal. (i) miatt Q3T3 a Q2Q3Q1 szög külső szögfelezője, így mivel a Q1Q2Q3 háromszög és az ABC háromszög egyállású és Q2Q3Q1=BCA, Q3T3-at Q3Q2-be (-π-γ2) szögű forgatás viszi. De láttuk, hogy T1T2-t BC-be is (-π-γ2) szögű forgatás viszi. Tehát mivel BC és Q3Q2 párhuzamosak, T1T2 is párhuzamos Q3T3-mal.
Így a Q1, Q2, Q3, H1, H2, H3 pontok rajta vannak a W1W2W3 háromszög Feuerbach-körén, azaz egy körön vannak. Mivel a H1, H2, H3 pontok éppen az ABC háromszög beírt körét határozzák meg, a bizonyítással készen vagyunk.
 Gyenes Zoltán (Apáczai Cs. J. Gimn., 12. o.t.)

*Itt és a továbbiakban a szakaszok által meghatározott egyenesek forgatásáról van szó. 
 A szerk.