Cím: Az 50. Nemzetközi Matematikai Diákolimpia feladatainak megoldásai
Füzet: 2009/október, 387 - 393. 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. Legyen n pozitív egész szám és legyenek a1,...,ak (k≥2) olyan páronként különböző egész számok az {1,...,n} halmazból, hogy az i=1,...,k-1 értékek mindegyikére teljesül az, hogy n osztója ai(ai+1-1)-nek. Bizonyítsuk be, hogy n nem osztója ak(a1-1)-nek.
 

Nagy Dániel megoldása. n∣ai(ai+1-1) azt jelenti, hogy
ai≡aiai+1(modn).(1)
Ezt felhasználva:
a1ak≡a1a2ak≡a1a2a3ak≡...≡a1a2...ak-1ak(modn).
Az (1) alapján újra kapjuk, hogy
a1a2...ak-1ak≡a1a2...ak-1≡a1a2...ak-2≡...≡a1a2≡a1(modn).
A fentiekből következik, hogy
a1ak≡a1(modn).(2)
A bizonyítandó állítás szerint n∤ak(a1-1). Felhasználva (2)-t:
ak(a1-1)=a1ak-ak≡a1-ak(modn).
Mivel 0<|a1-ak|<n, tehát az n-nel való osztási maradék 0-nál nagyobb, így n∤ak(a1-1).
 
2. Legyen az ABC háromszög körülírt körének középpontja O. Legyen P, illetve Q a CA, illetve AB oldal belső pontja. Legyenek K, L, illetve M a BP, CQ, illetve PQ szakaszok felezőpontjai, és legyen Γ a K, L, M pontokon áthaladó kör. Tegyük fel, hogy a PQ egyenes érintője a Γ körnek. Bizonyítsuk be, hogy OP=OQ.
 

Szűcs Gergely megoldása. Mivel KLM∢ és KMQ∢ egy ívhez tartozó kerületi, illetve érintőszárú kerületi szögek, így KLM∢=KMQ∢. Nyilván MK∥QB, mivel MK a QBP háromszögben középvonal, így PQA∢=KMQ∢, mert váltószögek. Tehát PQA∢=KMQ∢, és hasonlóan APQ∢=MKL∢, így APQ▵∼MKL▵.
 
 

Ebből MKML=APAQ, de
MKML=QB2PC2=QBPC,
tehát
QBPC=APAQ,
amiből QA⋅QB=PA⋅PC, vagyis a P és Q pontoknak a körülírt körre vonatkozó hatványa megegyezik (lásd KöMaL 2009/4. szám, hátsó belső borító), amiből már OP=OQ következik.
 
3. Tegyük fel, hogy s1,s2,s3,... pozitív egész számoknak olyan szigorúan növekvő sorozata, amelyre az
ss1,ss2,ss3,...ésss1+1,ss2+1,ss3+1,...
részsorozatok mindegyike számtani sorozat. Bizonyítsuk be, hogy s1,s2,s3,... maga is számtani sorozat.
 

Tomon István megoldása. Tekintsük a ti=si+1-si (i=1,2,...) különbségeket, és legyen j egy olyan pozitív egész, amelyre tj=min{t1,t2...} (mivel t1,t2,... pozitív egészek, létezik ilyen j). Legyen a=sj és b=sj+1, ekkor b>a a sorozat szigorú monotonitása miatt, és legyen d az ss1,ss2,... számtani sorozat differenciája. Ekkor ssj és ssj+1 ezen sorozat két egymást követő eleme, így sb-sa=d. Mivel si szigorúan monoton nő, sa<sa+1<...<sb, vagyis az sa+1-sa, sa+2-sa+1, ..., sb-sb-1 különbségek mind pozitívak, összegük sb-sa=d, s mivel b-a darab különbség létezik, a legnagyobb legalább db-a. Legyen ekkor x egy olyan pozitív egész, amelyre a≤x<b és a legnagyobb különbség sx+1-sx≥db-a. Egyenlőség csak akkor állhat fenn, ha minden különbség db-a.
Ezután nézzük az ssx és ssx+1 között lévő elemeket. Az egyszerűség kedvéért legyen sx=e, sx+1=f, ekkor sf-se=ssx+1-ssx=d, s ha nézzük az se+1-se, se+2-se+1, ..., sf-sf-1 különbségeket, akkor az f-e darab pozitív különbség, melyek összege sf-se=d. Legyen y egy olyan pozitív egész, amelyre e≤y<f és sy+1-sy a legkisebb különbség a felsoroltak között. Ekkor
sy+1-sy≤df-e=dsx+1-sx≤ddb-a=b-a,
és egyenlőség csak akkor állhat fenn, ha mindegyik különbség egyenlő, azaz se+1-se=se+2-se+1=...=sf-sf-1. Ám szükséges, hogy egyenlőség álljon fenn mindenhol, különben sy+1-sy<b-a, ami ellentmond annak, hogy b-a a legkisebb előforduló különbség az si sorozat két szomszédos eleme között. Ha egyenlőség áll fenn, az azt jelenti, hogy az sa,sa+1,...,sb sorozat egy db-a differenciájú számtani sorozatot alkot és se,se+1,...,sf is számtani sorozatot alkot, aminek b-a a differenciája.
Ezek után megmutatjuk, hogy (b-a)2=d, vagyis b-a=db-a. Az előbbiek alapján ehhez elég igazolni, hogy
sa+1-sa=se+1-se,(1)
mivel db-a=sa+1-sa és b-a=se+1-se. (1)-hez pedig elég belátni, hogy a feladatban megadott ss1+1,ss2+1,... számtani sorozat differenciája is d, mivel ekkor
|se+1-sa+1|=d⋅|(e+1)-(a+1)|=d⋅|e-a|=|se-sa|,
ami (1)-gyel ekvivalens.
Tegyük fel indirekt módon, hogy az ss1+1,ss2+1,... számtani sorozat differenciája c≠d. Nézzünk két esetet.
1. Ha c>d, akkor tetszőleges m pozitív egész esetén
ssm+1=ss1+1+(sm-s1)⋅c
és
ssm+1=ss1+(sm+1-s1)⋅d≤ss1+(d+sm-s1)⋅d=ss1+d2+(sm-s1)⋅d,
ahol az egyenlőtlenség miatt teljesül, hogy valamely r∈N+ esetén sr≤m<sm (mivel az si sorozat tetszőlegesen nagy értéket felvehet), s ekkor ssr≤sm<sm+1≤ssr+1 a szigorú monotonitás miatt, ahol ssr és ssr+1 differenciája d. Mivel si akármilyen határon túl nő, ∃m, hogy sm-s1>d2c-d, és ekkor
ssm+1-ssm+1≥ss1+1+(sm-s1)⋅c-(ss1+(sm-s1)d+d2)>>(sm-s1)⋅(c-d)-d2>0,
vagyis ssm+1>sm+1, ami ellentmondás, mivel sm+1≤sm+1.
2. Hasonlóan a c<d esetben:
ssm+1=ss1+1+(sm-s1)césssm=ss1+(sm-s1)d>(sm-s1)d.
Ekkor ha (sm-s1)>ss1+1d-c, akkor ssm-ssm+1>(sm-s1)(d-c)-ss1+1>0, vagyis ssm>ssm+1, ami ellentmondás a szigorú monotonitás miatt.
Tehát bebizonyítottuk, hogy c=d, így megkaptuk, hogy d=(b-a)2.
Ezután megmutatjuk, hogy i=1,2,... esetén si+1-si=b-a, azaz az s1,s2,... sorozat is egy számtani sorozat. Mivel a minimális különbség két szomszédos elem között b-a, így si+1-si≥b-a. Tegyük fel, hogy valamely r-re sr+1-sr>b-a. Ekkor ssr+1-ssr=d és az ssr+1-ssr,...,ssr+1-ssr+1-1 különbségek összege d, és sr+1-sr darab van, így lesz köztük egy, amelyik legfeljebb
dsr+1-sr<db-a=b-a,
vagyis az egyik különbség kisebb (b-a)-nál, ami ellentmondás.
Tehát minden különbség b-a, vagyis s1,s2,... számtani sorozatot alkot, s ezzel a feladat állítását bizonyítottuk.
 
4. Legyen az ABC háromszögben AB=AC. A CAB∢, illetve ABC∢ szögek szögfelezői a BC, illetve CA oldalakat rendre a D, illetve E pontokban metszik. Legyen K az ADC háromszög beírt körének a középpontja. Tegyük fel, hogy BEK∢=45∘. Határozzuk meg a CAB szög összes lehetséges értékét.
 

Kornis Kristóf megoldása. Legyen D' a D pont tükörképe a C-ből induló szögfelezőre. Ha O az ABC beírt körének középpontja, ODC∢=90∘⇒ODK∢=45∘, hiszen DK felezi az ODC szöget. Viszont O és K is rajta van a C-ből induló szögfelezőn, így OD'K∢=45∘ és D', E  OK egy oldalán vannak, tehát BEK∢=45∘ miatt O, E, D' és K egy körön fekszenek. Emiatt KED'∢=KOD'∢.
Viszont KOD'∢=KOD∢, és ha BAC∢=α, akkor

EBC∢=90∘-α22,ECB∢=90∘-α2⇒⇒KED'∢=BED∢-45∘=180∘-90∘-α22-(90∘-α2)-45∘,KOD∢=90∘-(90∘-α22).



Mivel
KED'∢=KOD∢,45∘-90∘-α2-α2=90∘-90∘-α22,
45∘=α2⇒α=90∘.
 
 

A fenti számolással probléma lehet, ha D'=E, ugyanis ekkor nem beszélhetünk a KED'∢-ről. Ha D'=E, akkor CD=CE, és ekkor ha az alap a, a szár b hosszú,
CD=a2,CE=a⋅ba+b,a2=a⋅ba+b⇒a2+ab=2ab⇒a=b,
a háromszög szabályos. Ha viszont a háromszög szabályos, OECD deltoid, érintőnégyszög, így az ACD háromszög beírt köre érinti BE-t is, tehát
BEK∢=BEC∢2,  de  BEC∢=90∘,
vagyis a BEK∢ ebben az esetben is 45∘ lesz.
Összefoglalva két megoldást kaptunk: CAB∢=90∘, vagy CAB∢=60∘.
 
5. Határozzuk meg az összes olyan f függvényt, ami a pozitív egész számok halmazát a pozitív egész számok halmazába képezi, és amire teljesül az, hogy teszőleges pozitív egész a és b értékekre van olyan nem-elfajuló háromszög, amelynek oldalhosszai a, f(b) és f(b+f(a)-1). (Egy háromszög nem-elfajuló, ha csúcsai nincsenek egy egyenesen.)
 

Nagy János megoldása. Először helyettesítsünk be (a=1)-et. Ekkor az 1, f(b), f(b+f(1)-1) számokra igazak a háromszög-egyenlőtlenségek, de mivel egészek, ez csak úgy lehet, ha f(b)=f(b+f(1)-1) minden b∈N+-ra.
Indirekt tegyük fel, hogy f(1)≠1. Ekkor minden pozitív egész c-re
a+c(f(1)-1),f(b)ésf(b+f(a+c(f(1)-1))-1)
egy háromszög oldalai, de f(b+f(1)-1)=f(b) ismételt alkalmazásával a+c(f(1)-1), f(b), f(b+f(a)-1) is egy háromszög oldalai. Ekkor c-t megválaszthatjuk úgy, hogy a háromszög-egyenlőtlenség ne teljesüljön, tehát kaptuk, hogy f(1)=1.
Helyettesítsünk be b=1-et, ekkor a, 1 és f(f(a)) egy háromszög oldalai. Ez az egyenlőtlenségek miatt csak úgy lehet, hogy f(f(a))=a, minden a∈N+-ra.
Most látjuk, hogy a függvény minden értéket fölvesz (f(f(a))=a) és kölcsönösen egyértelmű is, hiszen ha f(a)=f(b), akkor f(f(a))=f(f(b)), vagyis a=b. Most igazoljuk, hogy f(2)=2. A kölcsönös egyértelműség miatt f(2)>1. Indirekten tegyük fel, hogy f(2)=x>2. Helyettesítsünk be a=2-t; ekkor
2+f(b)>f(b+x-1),def(b+x-1)+2>f(b),
és a kölcsönös egyértelműség miatt nem egyenlőek, tehát |f(b+x-1)-f(b)|=1.
Most vegyük az f(x), f(x+(x-1)), ..., f(x+c(x-1)), ... sorozatot, ennek bármely két szomszédos tagja között a különbség 1. Tudjuk, hogy f(x)=2. Ennek a sorozatnak az elemei csak úgy léphetnének ki a [0,x] intervallumból, ha létezne egy c≥0 úgy, hogy f(x+c(x-1))=x (mivel egyesével változnak). Ekkor
f(f(x+c(x-1)))=f(x)=2=x+c(x-1),
de x>2, így ez nem lehet.
Tehát az f(x), f(x+(x-1)), ... sorozat elemei a [0,x] intervallumban vannak, ezért lesz olyan érték, amit kétszer is felvesznek, ez pedig a kölcsönös egyértelműség miatt nem lehet.
Így látható, hogy f(1)=1, f(2)=2. Indukcióval belátjuk, hogy minden (x>0)-ra f(x)=x. A kezdőlépésekkel megvagyunk; tegyük fel, hogy minden i<x-re f(i)=i. Mivel x>2, azért 2 és x-2 is pozitív egész számok. Behelyettesítve:
2,f(x-1),f(x-1+f(2)-1)
egy háromszög oldalai, amiből f(x)<f(x-1)+2=x+1, tehát f(x)≤x. Az f(x)<x a kölcsönösen egyértelműség miatt nem lehet. Így azt kaptuk, hogy f(x)=x, amivel az indukciós lépést befejeztük.
Végezetül az f(x)=x függvény valóban teljesíti a feladat feltételeit, mert a, b és a+b-1 mindig egy el nem fajuló háromszög oldalai. Az egyetlen jó függvény az f(x)=x.
 
6. Legyenek a1,a2,...,an páronként különböző pozitív egész számok és legyen M egy olyan, pozitív egész számokból álló, n-1 elemű halmaz, ami nem tartalmazza az s=a1+a2+...+an számot. Egy szöcske a valós számegyenesen ugrál a 0 pontból kiindulva úgy, hogy n ugrást hajt végre jobbfelé, melyek hossza a1,a2,...,an valamilyen sorrendben. Bizonyítsuk be, hogy a szöcske meg tudja választani az ugrások sorrendjét úgy, hogy ne ugorjon az M halmaz egyik elemére se.
 

Éles András megoldása. A szöcske csak az O és S közötti szakaszokra léphet (és S-re biztos rálép). Megmutatjuk, hogy ha útjában legfeljebb n-1 mező van, amire nem szabad lépnie, akkor végig tud menni az úton.
Feltehetjük, hogy a1<a2<...<an. Teljes indukcióval bizonyítunk n-re, n=1 triviális. Ha n=2, akkor a1∉M, vagy a2∉M, így a1, a1+a2, vagy a2, a1+a2 jó lesz. Legyen M legkisebb eleme d, ekkor n>2-re három eset állhat fönn:
I. d<an, an∉M. Legyen a szöcske első lépése an, ekkor átugorja d-t, így az útjában legfeljebb n-2 eleme marad n-nek, és n-1 különböző lépése. Az indukciós feltétel értelmében innen a szöcske már be tudja fejezni az útját (indukció: n-1).
II. d<an, an∈M. Tekintsük az alábbi 2n-1 darab páronként különböző számot:
a1<a2<...<an-1<an<a1+an<a2+an<...<an-1+an.
Mivel |M|≤n-1 és an∈M, azért a számok közül kiválasztható egy olyan (ai,ai+an) pár, hogy semelyik sincs M-ben (különben |M|≥n lenne). Legyen ai és an a szöcske első két lépése, ekkor átugorja az M-beli d-t és d<an-et, így hátralévő útjában már csak legfeljebb n-3 tiltott mező van, és (n-2)-t ugrik még, innen már be tudja fejezni az útját (indukciós feltétel, (n-2)-re).
III. d≥an. Hagyjuk el a d-t az M-ből, és legyen an a szöcske első lépése, ami legális. További útjában (d-t nem számolva) n-1 ugrás és legfeljebb n-2 tiltott mező szerepel, így végig tud menni az úton (indukciós feltétel (n-1)-re) úgy, hogy d kivételével nem érinti M-et.
Ha d-t sem érinti, akkor a teljes útvonal jó, így készen vagyunk.
Ha d-t érinti, akkor d∈M miatt d≠S, így a szöcske fog még lépni d-ről, tegyük fel, hogy (d+ai)-be lép. Ekkor d+ai∉M és utána sem lép rá M-beli elemre. (d+ai)-ig pedig legalább két ugrása van, mivel d≥an és an a legelső lépés, így ai≠an.
Rendezzük a teljes útvonalon csak a d+ai előtti ugrásokat olyan sorrendbe, hogy an legyen az utolsó ugrás. Ekkor az utolsó szám, amire a szöcske d+ai előtt ugrott:
d+ai-an=d-(an-ai)<d,
tehát d+ai előtt az átrendezett útvonalon már nincs tiltott pont, mert d-nél kisebb mindegyik.
Így ez az átrendezett útvonal egyetlen tiltott mezőt sem tartalmaz, az állítást igazoltuk.