Cím: 1991. A XXXII. Nemzetközi Matematikai Diákolimpia feladatainak megoldása
Füzet: 1991/november, 337 - 343. 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 feladatok alábbi megoldásait az olimpián részt vett versenyzők készítették.

 
1. Jelöljük az ABC háromszög beírt körének középpontját I-vel, a CBA, ABC, BCA szögek szögfelezőinek metszéspontját a szemközti oldalakkal pedig rendre A',B',C'-vel. Bizonyítsuk be, hogy
14<AIBICIAA'BB'CC'827.
(USA)

 

Megoldás. Legyenek az ABC háromszög oldalai a szokásos jelöléssel a,b, és c.
 
 

Segédtétel: Ismert, hogy
AIAA'=b+ca+b+c,BIBB'=a+ca+b+césCICC'=a+ba+b+c.
(Ennek bizonyítása két szögfelező tétel segítségével: BA'=acb+c , így
AIIA'=ABBA'=cacb+c=b+ca,
ahonnan valóban
AIAA'=b+ca+b+c).

A számtani és mértani közepek közötti egyenlőtlenséget használva, és az AIAA'+BIBB'+CICC'=2 összefüggést felismerve kapjuk, hogy
AIAA'BIBB'CICC'(AIAA'+BIBB'+CICC'3)3=827,
és egyenlőség csak szabályos háromszögnél áll fenn. Másfelől az a,b ésc számokra teljesül a háromszög-egyenlőtlenség, így (a+b-c)(a+c-b)(b+c-a)+4abc>0.
Ezt beszorozva és rendezve:
a2b+a2c+b2a+b2c+c2a+c2b+2abc>a3+b3+c3.
Mindkét oldalhoz hozzáadva 3(a2b+a2c+b2a+b2c+c2a+c2b)+6abc-t, majd szorzattá alakítva kapjuk, hogy
4(a+b)(b+c)(a+c)>(a+b+c)3,
azaz
AIBICIAA'BB'CC'=(a+b)(b+c)(a+c)(a+b+c)3>14.

Ezzel a bizonyítandó két egyenlőtlenséget beláttuk.
 
Matolcsi Máté

 

2. Legyen n>6 egész szám és a1, a2, ..., ak az összes olyan természetes szám, amely kisebb n-nél és relatív prím n-hez. Tegyük fel, hogy
a2-a1=a3-a2=...=ak-ak-1>0.
Bizonyítsuk be, hogy ekkor n prímszám, vagy 2-nek egész kitevős hatványa.

(Románia)
 

Megoldás. Legyen a2-a1=a3-a2=...=ak-ak-1=d. Mivel d>0, ezért a1<a2<...<ak. Mivel minden pozitív egész n-re (n-1,n)=1, ezért ak=n-1, továbbá nyilván a1=1.
 
I. Legyen először n páratlan. Ekkor (n-2,n)=1. (Ugyanis x|n és x|n-2 esetén x|2, de n páratlan, így x=1, ezért ak-1=n-2. Így viszont d=1 és ekkor minden n-nél kisebb pozitív egész relatív prím n-hez, azaz n-nek nincs nála kisebb valódi osztója; így n prím, ahogy a feladat állítja.
 
II. Legyen most n páros, és írjuk fel n=2αn1 alakban, ahol α1 és n1 páratlan.
a) Ha n1=1, akkor n2-hatvány, ahogy állítottuk; ekkor a feltétel nyilván teljesül, hiszen az ai-k éppen az n-nél kisebb páratlan számok és d=2.
b) Ha n1=3 volna, akkor n>6 miatt a1=1,a2=5,a3=7 és a2-a1a3-a2, ez pedig lehetetlen.
c) Legyen végül n15. Megmutatjuk, hogy ekkor n1-2 és n1-4 szerepel az ai-k között. Tegyük fel ugyanis, hogy x|2αn1 és x|n1-2. Ekkor x|2αn1=2α(n1-2)+2α+1 miatt x|2α+1. De x páratlan, így x=1, azaz (n1-2,2αn1)=1. Hasonlóan (n1-4,2αn1)=1. Nyilván n1-3 nem szerepel az ai-k között, hiszen páros; így d=2. De ekkor n1 is szerepel az ai-k között (az ai-k rendre 1,3,5,...,n1-2,n1,...). Ez viszont ellentmondás, mert (n1,n)=n1>1.
Beláttuk tehát, hogy n prím vagy 2-hatvány, a bizonyítást befejeztük.
 
Szendrői Balázs

 

3. Legyen S={1,2,3,...,280}. Határozzuk meg azt a legkisebb n egész számot, amelyre igaz az, hogy S minden n elemű részhalmaza tartalmaz 5 olyan számot, amelyek páronként relatív prímek.
(Kína)

 
Megoldás. Válasszuk ki az S halmazból a 2, a 3, az 5 és a 7 többszöröseit. Ezek közül akárhogyan választunk ki 5 számot, lesz kettő, amelyek ugyanannak a prímnek a többszörösei, tehát nem relatív prímek. Az S-ből kiválasztott elemek száma a szita-formula segítségével kiszámolva 216. Ezért a keresett n egész legalább 217.
Bebizonyítjuk, hogy n=217 esetén már teljesül a feltétel. Ehhez vizsgáljuk meg, hogy legfeljebb hány elem lehet S-nek egy olyan részhalmazában, amelyben nincs 5 olyan szám, amelyek páronként relatív prímek. A fent megadott 216 elemű halmaz kiválasztásakor elhagytuk a prímek és az 1 közül négy kivételével az összeset, a prímnégyzetek közül is négy kivételével az összeset, és ezeken kívül még hat darab két prím szorzataként felírható számot:
111311231117131711191319

Az eredeti feltételnek nem megfelelő bármely halmazban is a prímek és az 1 közül legfeljebb 4 lehet, különben lenne 5 szám, amelyek páronként relatív prímek, így ezek közül legalább annyit el kell hagyni, mint az előző példában. Ugyanez igaz a prímnégyzetekre is. Már csak az kell, hogy ezeken kívül még legalább 6 elemet el kell hagyni. Alább megadok 6 db 5 elemű diszjunkt halmazt, amelyek S részhalmazai, prímet és prímnégyzetet nem tartalmaznak, és mindegyikben páronként relatív prímek vannak, tehát mindegyik halmaznak legalább egy elemét el kell hagyni az S-ből ahhoz, hogy a feltétel ne teljesüljön.
A halmazok:
{23;33;523;719;1113}{26;317;53;713;1123}{24;34;519;723;1117}{27;323;529;711;1319}{25;35;513;717;1119}{28;319;511;729;1317}

Tehát, ha kiválasztunk S-ből egy 217 elemű halmazt, akkor az vagy tartalmaz egyet az előbbi 6 halmazból, vagy tartalmaz 5 prímet, vagy található benne 5 prímnégyzet. Ekkor van benne 5 szám, amelyek páronként relatív prímek. Tehát a keresett n szám a 217.
Ujváry-Menyhárt Zoltán

 

4. Legyen a G összefüggő gráf éleinek száma k. Bizonyítsuk be, hogy meg lehet az éleket számozni az 1,2,3,...,k számokkal úgy, hogy minden olyan csúcs esetén, amelyből legalább két él indul ki, az illető csúcsból kiinduló összes élhez rendelt számok legnagyobb közös osztója 1.
 
[Gráfnak nevezzük csúcsnak nevezett pontok egy halmazát, ahol a két különböző csúcsból álló párok némelyikét élek kötik össze. Bármely két különböző u,v csúcs között legfeljebb egy él halad. A G gráfot összefüggőnek nevezzük, ha bármely két különböző x,y csúcshoz található csúcsoknak egy olyan x=v0,v1,...,vm=y sorozata, hogy minden ui,vi+1(0i<m) csúcspárt él köt össze.]
(USA)

Megoldás. Úgy fogjuk megszámozni az éleket, hogy már két olyan él is tartozzék minden legalább másodfokú csúcshoz, amelyekre egymáshoz relatív prím számokat írtunk; ez nyilván elegendő a feladatbeli állítás bizonyítására.
Legyenek a gráf legalább másodfokú csúcsai A1,A2,...,An (ha ilyen csúcs nincsen, akkor triviális az állítás). Mivel a gráf összefüggő, ezért bármely csúcsból bármely csúcsba vezet út a gráfban. Menjünk el A1-ből A2-be, A2-ből A3-ba, ...,An-1-ből An-be, végül An-ből A1-be a gráf egy-egy tetszőleges élsorozatán keresztül! Így egy olyan utazást teszünk a gráfban, amelynek során minden Ai-t (i=1,2,...,n) érintünk és elhagyunk legalább egyszer. Tegyük fel, hogy utazásunk alatt sorra számozzuk az érintett éleket az 1,2,...,l számokkal (1lk) ‐ azzal a kikötéssel, hogy ha egy élre
a) már írtunk számot, akkor arra új számot már nem írunk.
b) még nem írtunk számot (tehát az utazás során először érintjük), akkor 1-gyel nagyobb számot írunk rá, mint amilyet utoljára használtunk.
Ezek szerint mindig csak az "új'' ‐ addig még nem érintett ‐ élekre kell számot írnunk, és összesen l db élt számoztunk meg a k db él közül.
Az utazásnál még egy dologra kell ügyelnünk:
Ha valamelyik Ai csúcsot (i=2,3,...,n) először érintjük utazásunk során (ez biztosan bekövetkezik minden i-re valamikor), akkor Ai-t másik élén keresztül hagyjuk el, mint amilyenen keresztül megközelítettük; ez megtehető, mert Ai legalább másodfokú. Mivel az Ai-ből kiinduló élek egyikét sem érintettük azelőtt, ezért a számozási algoritmus szerint ebben a lépésben Ai-nek 2 élére 2 szomszédos számot kell írnunk.
 
 

Ha utazásunkat és a számozást az előírt módon végezzük, akkor teljesül, hogy
‐ az A1-ből kiinduló egyik élre (utazásunk első élére) az 1-et írjuk,
Ai-ből (i=1,2,3,...,n) kiindul 2 olyan él, amelyre szomszédos számokat írunk.
Mivel x és y pozitív egészek relatív prímek egymáshoz, ha x=1 vagy y-x=1, ezért a megoldás elején megfogalmazott követelményünk teljesül, vagyis ‐ a fennmaradó k-l db élt tetszőlegesen megszámozva az l+1,l+2,...,k számokkal ‐ a feladat állítását beláttuk.
Harcos Gergely

 

5. Legyen P az ABC háromszög belső pontja. Bizonyítsuk be, hogy a PAB, PBC, PCA szögek közül legalább egy kisebb, vagy egyenlő, mint 30.
(Franciaország)

Megoldás. Használjuk az ábra jelöléseit.
 
 

Vegyük észre, hogy
sinα1sinβ1sinγ1sinα2sinβ2sinγ2=d2e1d3e2d1e3d3e1d1e2d2e3=1.

Tegyük fel, hogy a feladat állítása nem igaz, tehát α1,β1,és γ1 is nagyobb, mint 30. Ha például α150,βés γ is kisebb, mint 30, így máris ellentmondásra jutottunk. Ha pedig α,βésγ mindegyike kisebb 150-nál, akkor sinαsinβsinγ>18. Ugyanakkor a számtani és a mértani közepek közti egyenlőtlenség szerint
sinα2sinβ2sinγ2(sinα2+sinβ2+sinγ23)3.
A Jensen-egyenlőtlenséget felhasználva (hisz a sin függvény a [0,π] intervallumon konkáv)
sinα2+sinβ2+sinγ23sinα2+β2+γ23.
De mivel 0<α2+β2+γ2<90,3sinα2+β2+γ23<32, így
sinα2sinβ2sinγ2<(323)3=18,
vagyis
sinα1sinβ1sinγ1sinα2sinβ2sinγ2>1.
Ezzel ellentmondásra jutottunk, tehát bizonyítottuk a feladat állítását.
Kőszegi Botond

 

6. Valós számok egy x0,x1,x2,... sorozatát korlátosnak nevezzük, ha létezik olyan C konstans, hogy |xi|C minden i0-ra.
Minden rögzített a>1 valós számhoz konstruáljunk olyan korlátos, végtelen x0,x1,x2,... sorozatot, amelyre
|xi-xj||i-j|a1
teljesül bármely két különböző, nemnegatív i,j egészre.
(Hollandia)

 
I. megoldás. Tetszőleges kN esetén, ha k diadikus alakja
k=anan-1...a0¯2=s=0nas2s(ai=0vagy1;i=0,...,n),
akkor legyen
yk=s=0nas2-as,
ahol a>1 a feladatban rögzített valós szám. Legyen most i,jN,ij, továbbá iésj kettes számrendszerbeli alakja
i=bnbn-1...b0¯2ésj=cmcm-1...c0¯2

Feltehető, hogy i>j, és ekkor nm. Tegyük fel továbbá, hogy r az a természetes szám, amelyre iésj diadikus alakja az utolsó r db jegyben megegyezik, de (r+1)-edik jegyében ‐ hátulról olvasva ‐ már különbözik:
r=min{s|bscs,1sn},
(m<sn esetén legyen cs=0). Ekkor
|i-j|=i-j2r,(1)
és a>1 miatt
|yi-yj|=|s=0nbs2-as-s=0mcs2-as|=|s=rnbs2-as-s=rncs2-as|2-ar-2-a(r+1)-2-a(r+2)-...-2-an>2-ar(1-s=12-as)==2-ar(1-2-a11-2-a)=2-ar(1-12a-1)=2-ar2a-22a-1.

Ezt (1)-gyel egybevetve:
|yi-yj||i-j|a>2-ar2a-22a-1(2r)a=2a-22a-1,
ami azt jelenti, hogy az
xk=2a-12a-2yk(k=0,1,...)
sorozat i,jN;ij esetén
|xi-xj||i-j|a>1,
továbbá (yk) korlátos volta miatt (xk) is korlátos:
0xk=2a-12a-2yk<2a-12a-2s=02-as=2a2a-2.
Ezzel a feladatot megoldottuk.
 
II. megoldás. Konstrukciót adunk az a=1 esetre ‐ ez nyilván megfelelő a>1 esetére is.
Alapötletünk a következő: Tegyük fel, hogy γ olyan (irracionális) szám, amelynek minden pq(p,qZ;q>0) közelítő törtjére az eltérés
|γ-pq|1αq2,(2)
ahol α>0 valamilyen rögzített konstans. Ekkor tekintjük az
xk=α{γk}(k=0,1,...)
sorozatot, ahol {t}=t-[t] a t szám törtrészét jelöli. Világos, hogy (xk) korlátos:
0<xk<α,
továbbá i,jN;ij esetén (i>j feltehető )
|xi-xj||i-j|=α|{γi}-{γj}||i-j|=
=α|(γi-γj)-([γi]-[γj])||i-j|,
ill. a q=i-j(>0),p=[γi]-[γj] jelöléssel p és q egészek, tehát (2) szerint
|xi-xj||i-j|=α|qγ-p|q=αq2|γ-pq|1,
vagyis az (xk) sorozat megfelelő.
Az is látszik, hogy az
x'k=xk-α2(k=0,1,...)sorozatra|x'k|<α2,továbbá
|x'i-x'j||i-j|=|xi-xj||i-j|1,
tehát az x'k sorozat is megfelelő.
Ezek szerint csak a (2)-t kielégítő γ-t és α-t kell találnunk, sőt minél kisebb az α, annál jobb a sorozatunk korlátja.
(2)-re talán γ=2 és α=3 adja a legegyszerűbb példát:
|2-pq|>13q2(3)
mindig fennáll. Ha ugyanis lenne olyan pq közelítő tört, amelyre
|2-pq|13q2,(4)
akkor
2q-13qp2q+13q,
azaz négyzetre emelés és rendezés után
-223+(13q)2p2-2q2223+(13q)2
lenne, amiből
|p2-2q2|223+(13q)2
következnék. (4) nyilván nem állhat fenn q=1 esetén, ezért q2, tehát
|p2-2q2|223+(132)2=22+1123<1.
vagyis
p2-2q2=0,
hiszen |p2-2q2| nemnegatív egész.
Mivel 2 irracionális, ezért p2-2q2=0 ellentmondást jelent, ami (3)-at igazolja.
Ezzel sikerült megadnunk olyan (xk) sorozatot, amelyre
|xk|<32,és|xi-xj||i-j|1
teljesül, ha i,jN;ij.
Harcos Gergely