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.
1. Minden egész számra definiáljuk az sorozatot a következőképpen. Minden -ra legyen | | Határozzuk meg az összes olyan a0 értéket, amihez van olyan A szám, amire an=A teljesül végtelen sok n-re.
Gáspár Attila megoldása.
1. állítás: Ha a0≡0(mod3), akkor a sorozat tartalmazza a 3-at.
Bizonyítsunk a0 szerinti teljes indukcióval. Ha a0=3, akkor az állítás triviális. Ha a0=6, akkor a1=9, és a2=3, ezért az állítás igaz. A továbbiakban feltételezhetjük, hogy a0≥9. Látható, hogy az a0,a0+3,a0+6,... számtani sorozatban van az első négyzetszám a sorozatból. A sorozat összes eleme 3-mal osztható, ezért ez a négyzetszám x2=(3k)2 alakú. Végtelen sok 3-mal osztható négyzetszám van, ezért a sorozat tartalmaz négyzetszámot. A (3(k-1))2=(x-3)2 nem szerepel a sorozatban, ezért a0>(x-3)2=x2-6x+9=x(x-6)+9>x+9>x. Az x2 szerepel a sorozatban, ezért az x is szerepel. x<a0, ezért az indukciós feltevés miatt az állítás igaz. Látható, hogy ha a0=3, akkor a1=6, a2=9 és a3=3. Ha 3∣a0, akkor az 1. állítás miatt a 3 végtelen sokszor szerepel a sorozatban.
2. állítás: Ha a0≡1(mod3), akkor a sorozat tartalmaz 3k+2 alakú számot.
Bizonyítsunk a0 szerinti teljes indukcióval. Ha a0=1, akkor a1=4, és a2=2. Ebből látható, hogy az állítás a0=4 esetén is igaz. A továbbiakban feltételezhetjük, hogy a0≥7. Látható, hogy az a0,a0+3,a0+6,... számtani sorozatban van az első négyzetszám a sorozatból. Ilyen biztosan van, mert végtelen sok 3k+1 alakú négyzetszám van. Legyen ez a négyzetszám x2. Az x2 szerepel a sorozatban, ezért az x is szerepel. Ha x=3k+2 alakú, akkor az állítás igaz. Ha x=3k+1 alakú, akkor a (3k-1)2=(x-2)2 nem szerepel a sorozatban, ezért a0>(x-2)2=x2-4x+4=x(x-4)+4>x+4>x. Az indukciós feltevés miatt az állítás igaz.
3. állítás: Ha a0≡2(mod3), akkor a sorozat szigorúan monoton növekvő.
Egy négyzetszám nem lehet 3k+2 alakú. Így az a0,a0+3,a0+6,... sorozat nem tartalmaz négyzetszámot. Ekkor a1=a0+3, a2=a0+6, ..., an=a0+3n. Ezzel az állítást igazoltuk. Látható, hogy ha a0 nem osztható 3-mal, akkor a 2. és 3. állítás miatt a sorozat egy idő után szigorúan monoton növekvő. Így nincs olyan A, amit végtelen sokszor tartalmaz. Tehát pontosan akkor van olyan A, amit végtelen sokszor tartalmaz a sorozat, ha 3∣a0.
2. Legyen R a valós számok halmaza. Határozzuk meg az összes olyan f:R→R függvényt, amire minden valós x, y szám esetén teljesül | f(f(x)f(y))+f(x+y)=f(xy). |
Matolcsi Dávid megoldása. Ha f(0)=0, akkor y=0-nál ezt kapjuk: | f(f(x)f(0))+f(x+0)=f(0⋅x). | Ebben az esetben f(x)=0 minden x-re. Ez valóban megoldása a függvényegyenletnek. Most nézzük azt az esetet, amikor f(0)≠0. Ha x=0 és y=0, akkor | f(f(0)2)+f(0)=f(0),f(f(0)2)=0. |
Tegyük fel, hogy f(c)=0 és c≠1. Ha y=1+1x-1, akkor (x-1)(y-1)=1, azaz x+y=xy, ezért f(x+y)=f(xy), így f(f(x)f(y))=0. Legyen x=c és y=1+1c-1. Ekkor f(f(c)f(1+1c-1))=0. Mivel f(c)=0, f(0)=0, ez viszont ellentmond az elején kikötött feltételnek. Azt kaptuk, hogy f(c)=0 esetén c=1, így f(0)2=1, ezért f(1)=f(f(0)2)=0, továbbá f(0)=1 vagy f(0)=-1. Világos, hogy f(x) akkor és csak akkor megoldása a függvényegyenletnek, ha -f(x) is megoldása (mindkét oldal előjele megfordul). Ezért az általánosság sérelme nélkül feltehetjük, hogy f(0)=-1. Helyettesítsünk most az egyenletbe y=1-et:
f(f(x)f(1))+f(x+1)=f(1⋅x),f(0)+f(x+1)=f(x),f(x+1)=f(x)+1.
Ebből következik, hogy n egészekre f(x+n)=f(x)+n. Megmutatjuk, hogy f(x) injektív. Tegyük fel, hogy nem az, vagyis létezik olyan A≠B, hogy f(A)=f(B). Legyen n egy A-nál nagyobb egész, és legyen A-n=a és B-n=b, ahol tudjuk, hogy a negatív. Ha f(A)=f(B), akkor f(a)=f(b). Az x2-bx+a-1=0 másodfokú egyenlet diszkriminánsa b2-4(a-1), ami pozitív (mivel a-1 negatív), ezért az egyenletnek két gyöke van, r és s. A Viéte-formulákból tudjuk, hogy r+s=b és rs=a-1; így x=r és y=s választással f(f(r)f(s))+f(b)=f(a-1)=f(a)-1. Az egyenletből kivonható f(a)=f(b): f(f(r)f(s))=-1, f(f(r)f(s)+1)=0, amiből f(r)f(s)+1=1, azaz f(r)f(s)=0. Feltehető, hogy s=1, ekkor a=1⋅r+1 és b=r+1, tehát a=b, ezzel ellentmondásra jutottunk; a függvény valóban injektív. Legyen y=1-x. Ekkor f(f(x)f(1-x))+f(1)=f(x(1-x)), Az injektivitás miatt f(x)f(1-x)=x-x2. Legyen most y=-x. Ekkor f(f(x)f(-x))+f(0)=f(-x2), f(f(x)f(-x))=f(1-x2). Az injektivitás miatt f(x)f(-x)=1-x2, ezért f(x)f(1-x)-f(x)f(-x)=x-x2-(1-x2)=x-1. Másrészt | f(x)f(1-x)-f(x)f(-x)=f(x)(f(1-x)-f(-x))=f(x). | Így f(x)=x-1 minden x-re. Ez valóban jó megoldás: (x-1)(y-1)-1+x+y-1=xy-1. Ez volt a megoldás, amikor f(0)=-1, és ennek az ellentettje, f(x)=1-x a megoldás, amikor f(0)=-1. Tehát a függvényegyenletnek három megoldása van: f(x)=0, f(x)=x-1 és f(x)=1-x.
3. Egy vadász és egy láthatatlan nyúl egy játékot játszik az euklideszi síkon. A nyúl A0 kiindulópontja és a vadász B0 kiindulópontja egybeesnek. A játék (n-1)-edik menete után a nyúl az An-1 pontban, a vadász a Bn-1 pontban van. A játék n-edik menetében a következő három dolog történik, ebben a sorrendben:
(i) | A nyúl láthatatlan módon egy olyan An pontba megy, amire An-1 és An távolsága pontosan 1. |
(ii) | Egy nyomkövető eszköz megad egy Pn pontot a vadásznak. Az eszköz által a vadásznak nyújtott információ mindössze annyi, hogy Pn és An távolsága legfeljebb 1. |
(iii) | A vadász látható módon egy olyan Bn pontba megy, amire Bn-1 és Bn távolsága pontosan 1. |
Igaz-e, bárhogyan mozogjon is a nyúl, és bármilyen pontokat jelezzen is a nyomkövető eszköz, hogy a vadász mindig meg tudja úgy választani a mozgását, hogy 109 menet után a távolság közte és a nyúl között legfeljebb 100 legyen?
Kovács Benedek megoldása. A feladat állítása nem igaz: belátjuk, hogy a vadász akármilyen stratégiája esetén a nyomkövető jelezheti P1,P2,...,P109 pontok olyan sorozatát, hogy a nyúlnak létezzen olyan, a szabályok szerinti A0A1A2...A109 lehetséges mozgássorozata, amire B109A109>100. Vagyis ha a nyúl maga jelölheti ki a nyomkövető jelzéseit a számára legkedvezőbb módon, akkor a vadász nem tudja garantálni, hogy 100-on belül kerüljön a nyúlhoz. Legyen di=AiBi. A nyúl célja az, hogy d109>100 legyen. Nyilván az is elég számára, ha valamilyen i<109-re di>100, hiszen ha ekkor a nyúl a további lépésekben már mindig a vadásszal ellentétes irányban lép, akkor lépésével a vadásztól való távolságát 1-gyel növeli, a vadász pedig a saját lépésében legfeljebb 1-gyel csökkentheti, vagyis egy fordulón belül a távolság nem csökken, így a 109-edik forduló után is 100-nál nagyobb lesz.
Lemma. Ha az i. fordulóban di<100, a vadász nem tudja garantálni, hogy di+2002≤di2+12 legyen.
Bizonyítás. A nyúl tehát 200 forduló alatt szeretné a vadásztól vett távolságának négyzetét 12-nél többel megnövelni. A vadásznak az i-edik forduló kezdetekor a nyúl mozgásáról rendelkezésére álló információt a P1,P2,...,Pi-1 pontok jelentik. Ezen pontok alapján a nyúlnak akár több lehetséges helye is lehet, de most tegyük fel még azt is, hogy a nyúl konkrétan elárulja a helyzetét, az Ai pontot. A korábbi információk így feleslegessé válnak. Jelöljük ℓ-lel az AiBi egyenest (Ai=Bi esetén tetszőleges egyenest Ai-n keresztül). Mérjük fel az ábra szerint az l egyenesre az Ai pontból, Bi-vel ellentétes irányban 39999 egységet, így kapva a Z pontot. A Z pontban merőlegest állítva ℓ-re, ezen a merőlegesen vegyük fel a C1 és C2 pontokat Z-től 1 távolságra. Ekkor a Pitagorasz-tétel miatt AiC1=AiC2=39999+1=200 lesz.
A nyúl számára a következő 200 fordulóban az lesz a stratégia, hogy egyenesen elmegy a C1 célpontba (ezt megteheti, hiszen AiC1=200). Mivel a teljes AiC1 szakasz 1 távolságon belül van az ℓ egyenestől, a nyúl minden fordulóban kijelölheti helyzetének az ℓ-re vett merőleges vetületét, mint a nyomkövető által adandó jelzést. Természetesen ugyanezeket a jelzéseket megadhatná a nyúl akkor is, ha nem a C1, hanem a C2 pontba menne el hasonló módon, hiszen a két útvonal ℓ-re nézve szimmetrikus. A vadász így a 200 forduló alatt kapott jelzésekből nem fogja tudni, hogy a C1 vagy a C2 pont felé tart-e a nyúl. Nézzük azt a Bi+200 pontot, ahova a vadász ezalatt eljutott. Ez a pont biztosan a Bi középpontú, 200 sugarú körön belül van, legyen ennek az ℓ-lel való (a nyúl irányába eső) metszéspontja M. Osszuk fel ezt a kört két részre az ℓ egyenes (C1C2 felezőmerőlegese) mentén. Az egyik (az ábra szerint felső) részben lévő pontok a C1 célponthoz, a másik (alsó) részben lévők C2-höz vannak közelebb. A felső rész összes pontjára igaz, hogy legalább olyan távol vannak C2-től, mint M, mert mind vízszintesen, mind függőlegesen legalább olyan távol vannak tőle (ha az ábra szerint, vagyis az ℓ egyenessel párhuzamosnak vesszük a vízszintes irányt). Ugyanígy az alsó rész összes pontja legalább olyan távol van C1-től, mint M. Így a két lehetséges célpont közül a távolabbi mindenképpen legalább olyan messze lesz a vadásztól, mint az MC1=MC2 távolság. Számítsuk ki ezt a távolságot. BiAi=di, így AiM=200-di. Így MZ=AiZ-AiM=39999-200+di, és a Pitagorasz-tétel alapján | MC1=MZ2+C1Z2=(39999-200+di)2+1. |
Azt kell belátnunk, hogy ez a távolság nagyobb, mint di2+12:
(39999-200+di)2+1>di2+12,(39999-200+di)2+1>di2+12,di2+2(39999-200)di+80000-40039999>di2+12,2(39999-200)di-40039999+80000>12,2(39999-200)di+400(200-39999)>12,(400-2di)(200-39999)>12,(200-di)(200-39999)>14.
Mivel di≤100, azaz 200-di≥100, elég belátni, hogy
200-39999>1400,80000-40039999>1,79999>40039999.
Négyzetre emelve: Ez pedig igaz, mert | 799992-1=80000⋅79998=160000⋅39999=39999⋅4002. |
Ekvivalens lépésekkel dolgoztunk, így a vadász számára rosszabbik távolság legalább MC1>di2+12, így a lemmát beláttuk.
A lemmából már következik a bizonyítandó állítás: a játék elején d02=0, és a lemma szerint (teljes indukcióval) a vadász számára legrosszabb esetben d200n2>12n, amíg a távolság el nem éri a 100-at. Ez az elérés pedig legkésőbb n=2⋅1002=20000-re bekövetkezik, azaz 200⋅20000=4⋅106 fordulón belül. Vagyis d4⋅1062>10000, azaz d4⋅106>100. A nyúl ezzel elérte a célját, hiszen 4⋅106≤109. A második nap feladatainak megoldását a novemberi számban közöljük. |