Cím: 1990. A XXXI. Nemzetközi Matematikai Diákolimpia feladatainak megoldása
Szerző(k):  Balogh József ,  Csirik János ,  Harcos Gergely ,  Kondacs Attila ,  Lakos Gyula ,  Pataki János 
Füzet: 1990/november, 337 - 344. 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 ett versenyzők és Pataki János készítették.

 

1. Egy adott kör AB, CD húrjai a kör belsejében lévő E pontban metszik egymást. Legyen M az EB szakasz egy belső pontja. A D, E, M pontokon átmenő körhöz E-ben húzott érintő messe a BC, ill. AC egyeneseket rendre az F, ill. a G pontban. Ha AMAB=t, fejezzük ki az EGEF hányadost t segítségével.
 

Megoldás. Azt a pontot, ahol MD másodszor metszi a kört, jelöljük X-szel. Továbbá legyen ADC∢=γ, CDX∢=α, XDB∢=β. Mivel szintén az AC ívhez tartozik, ABC∢=γ. Az FG egyenes a DEM háromszög körülírt körének E-beli érintője, e kis körben az FEM szög az EM húrhoz tartozó érintő szárú kerületi szög, így FEM∢=EDM∢=α. Ennek csúcsszögére: GEA∢=α. Ezentúl csak az ABCD körülírt körére fogunk hivatkozni ,,kör'' néven. E kör sugarát 12-nek választva, és tetszőleges L1, L2, L3 köri ponthármasra az általános szinusztételt felírva:
L1L3=(sinL1L2L3∢)⋅2R=sinL1L2L3∢.(*)
Az AEG háromszögben a szinusztételt felírva:
EGsinGAE∢=AEsinAGE∢.(**)
Itt két észrevételt teszünk: mivel GAE∢+EAC∢=180∘, ezért sinGAE∢=sinEAC∢. Másrészt CB feletti szögek kerületi szögek lévén α+β=CDB∢=CAB∢ és CAB∢ az AEG háromszög külső szöge, így α+β=CAB∢=AGE∢+AEG∢, tehát AEG∢=α szerint AGE∢=β=XDB∢.
A (*) és (**) állításokból:
EG/CB=AE/XB.(1)

Vegyük észre, hogy az EFB háromszögben az E csúcsnál levő szög α, a B-nél levő γ, ezért az F csúcsnál levő szög 180∘-α-γ, sinEFB∢=sin(α+γ)=AX. Az EFB háromszögben a szinusztétellel: EFsinγ=EBsin(α+γ), így (*) szerint:
EF/AC=EB/AX.(2)

(1)-et (2)-vel elosztva:
EGEF=AE⋅CB⋅AXEB⋅AC⋅XB.(3)

Lemma: Egy ACBD konvex húrnégy szög AB és CD átlóinak metszéspontja E. Ekkor:
CB⋅AE⋅BD=AC⋅EB⋅AD.

 
 

Bizonyítás: Az ADE háromszögben a szinusztételből:
AE/sinADE∢=AD/sinAED∢,
azaz (*) szerint
AE/AC=AD/sinAED∢.(L1)

Az EBC háromszögben hasonlóan
EB/sinBCE∢=CB/sinCEB∢=CB/sinAED∢,EB/BD=CB/sinAED∢.(L2)



Az (L2) egyenletet az (L1) egyenlettel elosztva és rendezve a bizonyítandó állítást kapjuk.
Lemmánkat az ACBD és AXBD négyszögekre alkalmazva:
CB⋅AE⋅BD=AC⋅EB⋅AD,XB⋅AM⋅BD=AX⋅MB⋅AD.
A második egyenletet az elsővel elosztva:
AMMB=AE⋅CB⋅AXXB⋅EB⋅AC,
amelyet (3)-mal összevetve:
EGEF=AMMB=AMAB-AM=t1-t.

Megjegyzés. A feladat elolvasása és az ábra felrajzolása után mindjárt az a benyomásom támadt, hogy itt olyan sok szép egyenlő szög van, hogy elképzelhetetlen, hogy a megoldást ne lehetne valahogyan ,,kiszenvedni''. Sajnos, elegáns megoldást nem találván, tényleg ezt kellett tennem. Így versenydolgozatomban a szinusztételt 8 háromszögre alkalmaztam, majd ezek ,,cseles'' összeszorzásával rengeteg tag kiesett és a bizonyítandó állítást kaptam. Az itt közölt megoldásbeli lemmát Pataki János javaslatára használom fel, ez a megoldást jóval áttekinthetőbbé teszi (azért a háttérben ugyanazok a szinusztételek vannak).
 

Kondacs Attila
 

2. Legyen n≥3, és tekintsünk egy E halmazt, amely egy kör kerületén lévő 2n-1 darab különböző pontból áll. Tegyük fel, hogy ezen pontok közül pontosan k darabot feketére színezünk. Egy ilyen színezést ,,jó''-nak nevezünk, ha található két olyan fekete pont, hogy az általuk meghatározott két körív belseje pontosan n darab E-beli pontot tartalmaz. Határozzuk meg a legkisebb olyan k értéket, amelyre igaz, hogy E bármely k pontját színezzük is feketére, a színezés ,,jó''.
 

Megoldás. Kétségkívül ez a feladat volt az első versenynap legkönnyebb feladata, főleg azok számára, akik nem szeretik a geometriát. Ugyanis a megoldás folyamán csupa ,,természetes'' ötletet kell csak felhasználni, tulajdonképpen józan ész elegendő hozzá.
Legyenek a pontok nevei rendre A1, A2, ..., A2n-1. (Ha valamilyen Ai-t említünk, amelyre i≥2n, vagy i≤0, akkor az i modulo (2n-1) értendő.)
Könnyen kialakulhat az a sejtésünk, hogy n-től függően n-1 vagy n a megfelelő k.
Próbáljunk ,,rossz'' színezést találni. Vizsgáljuk a következő sorozatot
An-2;A2(n-2);A3(n-2);...;Ai(n-2),(*)
amelyre teljesüljön, hogy A(i+1)(n-2) már előfordul a sorozatban. Ez az A(i+1)(n-2) pont csak az An-2 lehet, hisz minden ponttól két pont van n-2 távolságnyira, s a többi pontnál ezek a szomszédok. Így
(i+1)(n-2)≡n-2(mod(2n-1)),
vagyis
(i+1)(n-2)=n-2+a(2n-1),
(ahol a megfelelő egész szám), így
i(n-2)=a(2n-1).(1)
Ha i=2n-1, akkor a sorozatunk az összes pontot tartalmazza. Közülük n darabot kiválasztva lesz köztük szomszédos (An-2 és Ai(n-2) szomszédosnak tekintendő), hiszen különben Aj(n-2) kiválasztása esetén A(j+1)(n-2) nem választható ki, s az egyértelmű hozzárendelés miatt n pontot kiválasztva n pontot zárunk ki, ami összesen már több, mint 2n-1. Nyilván n-1 pont kiválasztható, ilyen p1. az A2(n-2);A4(n-2);...;A(2n-2)(n-2). Tehát ha i=2n-1, akkor k=n.
Nézzük meg azt, hogy milyen n-re lehetséges i≠2n-1. Ekkor n-2-nek és 2n-1-nek van 1-nél nagyobb közös osztója, ami csak a (2n-1)-2⋅(n-2)=3 lehet, éspedig abban az esetben, ha n=3e+2 alakú. Vagyis i=2n-13 lehetséges még. Ekkor a (*) sorozatban éppen a 3-mal osztható sorszámú pontok találhatóak. A sorszámokhoz 1-et, ill. 2-t adva kaphatjuk az alábbi sorozatokat:
A1(n-2)+1;A2(n-2)+1;...;A2n-13(n-2)+1,(**)A1(n-2)+2;A2(n-2)+2;...;A2n-13(n-2)+2.(***)
A három sorozat tartalmazza az összes pontot. Az előzőekhez hasonlóan igazolható, hogy ha egy sorozat 2n-13 elemet tartalmaz, akkor legfeljebb n-23 elem színezhető ki úgy, hogy a színezés rossz legyen. Ez mindhárom esetben megtehető, így adódik, hogy n-2 pontot még ki lehet színezni rosszul, n-1-et azonban már nem.
Tehát: ha n=3e+2 alakú, akkor k=n-1, különben k=n.
 

Balog József
 

3. Határozzuk meg az összes olyan n>1 egész számot, amelyre 2n+1n2 is egész szám.
Megoldás. n=3 nyilván megoldás, hiszen 23+1=9 osztható 32=9-cel. Megmutatjuk, hogy más megoldás nem létezik.
Írjuk ehhez az n-et 3k⋅d alakba (k≥0, 3 és d relatív prímek). Ekkor
2n+1=23kd+1=(2d+1)∏i=0k-1(22⋅3id-23id+1).(*)
Mivel minden páratlan t egészre 22t-2t+1 osztható 3-mal, de nem osztható 9-cel, ezért (1) jobb oldalán a k-tényezős szorzat 3-nak pontosan a k-adik hatványával osztható.
Ha most a fenti alakú szám megoldás, azaz n2=(3kd)2 osztója 2n+1-nek, akkor a ,,hiányzó'' 3-as tényezőket az (1)-beli szorzat első tényezőjének kell tartalmaznia:
3k|2d+1,
ami csak a k=0, vagy 1 esetekben lehetséges, hiszen (d,3)=1 miatt 9∤2d+1.
Megmutatjuk, hogy d értéke csak 1 lehet. Tegyük fel, hogy d>1 és legyen a d legkisebb prímosztója p, ami legalább 5, másfelől (p-1,d)=1.
A feltétel miatt
p|2n+1,(2)
a kis Fermat-tételből pedig
p|2p-1-1
következik. Így a
22n≡1(modp)
és
2p-1≡1(modp)
kongruenciákból
2m≡1(modp)(3)
következik, ahol m=(2n,p-1).
Mivel 2n|2⋅3d és (p-1,d)=1, ezért szükségképpen m|6, azaz (3) szerint a p prímszám az 1, 3, 7, 63 számok valamelyikének 3-nál nagyobb prímtényezője, ami csak úgy lehetséges, ha p=7. Ez viszont lehetetlen, ugyanis (2) alapján ekkor 7|2n+1, ami egyetlen pozitív egész n kitevővel sem teljesül. A d tehát valóban nem lehet 1-nél nagyobb.
A feladat feltétele így csak azokra az n=3kd számokra teljesülhet, amelyekre k≤1 és d=1. Ha k=0, akkor n=1, ha pedig k=1, akkor n=3.
Pataki János
 

4. Jelölje Q+ a pozitív racionális számok halmazát. Adjunk példát olyan F:Q+→Q+ függvényre, amelyre
f(x⋅f(y))=f(x)y
teljesül minden x, y∈Q+ esetén.
 

Megoldás. Definiáljuk az f függvényt a következőképpen: Vegyük tetszőleges x∈Q+ számnak a prímfelbontását, ahol a prímeket a szokásosan értelmezzük, de nem csak nemnegatív, hanem egész hatványon fordulhatnak elő a prímfelbontásban. Vegyük sorra a prímeket (minden x esetében ugyanolyan sorrendben): p1, p2, p3, .... Ekkor f(x) legyen az a szám, amelyet x prímfelbontásából kapunk úgy, hogy p2n helyébe p2n-1-et, p2n-1 helyébe p2n-1-et írunk. Mivel mind a prímfelbontás, mind a behelyettesítési művelet egyértelmű, ezért f(x) is. (Persze csak adott prímfelsorolás mellett) Bebizonyítjuk, hogy f teljesíti a kívánt feltételeket:
I. f(x)∈Q+ nyilvánvaló.
II. Mivel f multiplikatív, és a kritérium nem érzékeny a multiplikativitásra, ezért elég f(f(y))=y-1-et igazolni, és ezt is csak prímekre. Az f definíciója szerint
y=p2neseténf(f(y))=f(p2n-1)=p2n-1=y-1,y=p2n-1eseténf(f(y))=f(p2n-1)=p2n-1-1=y-1.
Ezzel beláttuk az f(x⋅f(y))=f(x)y kritérium teljesülését is, azaz az így kapott f függvény példa ilyen függvényre.
 

Megjegyzés. Hammel-bázissal R+-ra is általánosítható a feladat, illetve minden ilyen f függvény jellemezhetővé válik. (A versenyen beadott, R+-ra is általánosított megoldásom is ezzel dolgozik, míg az itt leírt megoldásom alapötletét a versenyen csak megjegyzésben közöltem.)
 

Lakos Gyula
 

5. Egy n0>1 egész számból kiindulva két játékos, A és B felváltva neveznek meg n1, n2, n3, ... egész számokat, az alábbi szabályokat betartva.
Ha n2k már meg van nevezve, A tetszése szerint választ egy n2k+1 egész számot, amire
n2k≤n2k+1≤n2k2
teljesül. Ha már n2k+1 meg van nevezve, B tetszése szerint választ egy n2k+2 egész számot, amire
n2k+1n2k+2
legalább 1 kitevőjű prímhatvány. Az A játékos nyer, ha 1990-et nevezi meg, B játékos nyer, ha 1-et nevezi meg.
Mely n0 értékekre teljesül:
a) A-nak van nyerő stratégiája,
b) B-nek van nyerő stratégiája,
c) egyik játékos sem tudja kikényszeríteni a győzelmet?
 

Megoldás. Rögtön észrevehetjük, hogy B-nek mindig csökkentenie kell az utoljára elhangzott számot, A-nak pedig növelnie (legalábbis nem csökkentenie). Az is látszik, hogy B csak akkor nyerhet, ha A előtte prímhatványt mondott. Mivel A mindig egy [n2k,n2k2] típusú intervallumból választhat számot, ezért ─ úgy érezzük ─ B-nek elég kevés esetben van esélye a nyerésre, feltéve persze, hogy A valamilyen ésszerű stratégiával játszik.
Célszerű tehát először az a) kérdéssel foglalkoznunk. Ha n0≤1990<n02, akkor A triviálisan nyer az n1=1990 számmal, ezért 45≤n0≤1990 esetén A-nak van nyerési stratégiája.
Az 1990<n0 esetben A nem alkalmazhatja ezt a módszert, de ha tud olyan n1 számot mondani, amelyre B csak 45≤n2≤1990 számmal válaszolhat, akkor ismét A nyer, hiszen ekkor n0 szerepét n2 veszi át. Legyen például n1=47⋅53=2491 ‐ A választhatja ezt a számot 1990<n0≤2491 esetén ‐, ezzel n2=47 vagy 53.
Ezzel beláttuk, hogy 45≤n0≤2491 esetén A tud nyerni, hasonlóan fogjuk igazolni k szerinti teljes indukcióval, hogy 45≤n0≤2k-1⋅2491 esetén (k pozitív egész) is A-nak van nyerési stratégiája.
k=1-re már beláttuk az állítást, tegyük fel ezért, hogy valamilyen k≥1-re igaz az állítás, azt kell megmutatnunk, hogy
2k-1⋅2491<n0≤2k⋅2491
esetén A-nak van nyerési stratégiája.
Válassza ehhez A az n1=2k⋅2491=2k⋅47⋅53 számot, nyilván n0≤n1<n02. Ezek után B csak egy n2=n1/pα=(2k⋅47⋅53)/pα alakú egészet választhat, ahol pα prímhatvány. Erre 47<n2≤n12=2k-1⋅2491, ami azt jelenti induktív feltevésünk szerint, hogy A-nak van nyerési stratégiája, az állítás (k+1)-re is fennáll.
Eddigi eredményeinket összefoglalva kapjuk, hogy a 45≤n0 esetben A-nak van nyerési stratégiája.
Próbáljuk meg a fennmaradó n0<45 eseteket is erre az esetre visszavezetni. A-nak olyan n1 számot kell mondania, amelyre B csak egy 45≤n2 számot választhat. Tekintsük ehhez az n1=32⋅5⋅11=495 számot ‐ A választhatja ezt a 23≤n0≤44 esetben, mert ekkor n0≤n1≤n02 ‐, ezzel n2-re
n2≥min(32⋅5,32⋅11,5⋅11)=32⋅5=45,
vagyis az előzőek alapján A-nak van nyerési stratégiája.
Hátra van az n0≤22 eset vizsgálata; A-nak most már elegendő olyan n1 számot mondania, amelyre n2≥23. Legyen ehhez n1=2⋅3⋅5⋅7=210, ezzel n2≥2⋅3⋅5=30. Mivel a 15≤n0≤22 esetben n0≤n1≤n02 is teljesül, ezért ilyenkor is A-nak van nyerési stratégiája.
Tovább ,,lépegetünk'' lefelé ‐ mindig ugyanazzal a redukáló szándékkal: 11≤n0≤14 esetén A száma legyen n1=3⋅5⋅7=105; nyilván n0≤n1≤n02, és n2≥3⋅5=15, vagyis innen A nyerni tud ‐ az eddig bizonyítottak miatt.
Végül legyen n1=22⋅3⋅5=60 ha 8≤n0≤10; ekkor n0≤n1≤n02 és n2≥min(22⋅3,22⋅5,3⋅5)=22⋅3=12, ami azt jelenti, hogy ekkor is A-nak van nyerési stratégiája.
Ezzel beláttuk, hogy 8≤n0 esetén A-nak van nyerési stratégiája.
Ezzel a módszerrel nem tudjuk tovább csökkenteni n0 olyan lehetséges értékeit, amelyekből kiindulva A el tudja érni a győzelmet. Azt tapasztaljuk ugyanis, hogy n0<8 esetén A nem tud olyan n1 számot mondani, amelyre B csak egy n2≥8-cal válaszolhatna. Ez a tény azt sejteti velünk, hogy n0<8 esetén B legalább egy döntetlent ki tud kényszeríteni. (Valójában az előbbi észrevétel igazolja is sejtésünket, hiszen ha B nem nyer, akkor B még mindig ki tud kényszeríteni egy végtelen
n0<8,n1<64,n2<8,n3<64,n4<8,n5<64,...
számsorozatot, ami azt jelenti, hogy A sem nyerhet, mert nem nevezheti meg az 1990-et. A későbbiekben azonban úgyis pontosabban megvizsgáljuk a döntetlen lehetőségeit, ezért egyelőre a sejtés elegendő számunkra.)
Foglalkozzunk most a b) kérdéssel.
Ha n0=2, akkor n0≤n1≤n02 miatt A csak prímhatványt választhat (n1=2,3,4), vagyis B mondhatja az n2=1 számot, amivel megnyeri a játékot.
Ha n0=3, akkor n1=3, 4, 5, 6, 7, 8, 9. Ha n1 prímhatvány, akkor n2=1-gyel B nyer, egyébként n1=6=2⋅3. Ekkor B választhatja az n2=2 számot, és ekkor ‐ mint az előbb igazoltuk ‐ B-nek van nyerési stratégiája. (n0 szerepét n2 veszi át).
Ha n0=4, akkor B az előbbiekhez hasonlóan el tudja érni a győzelmet, amennyiben n1 prímhatvány, vagy n1≤32. Különben pedig n1=10, 12, 14, 15; és ezeket az eseteket rendre visszavezethetjük az előzőekre az n2=2, 3, 2, 3 választással, ugyanis n2≤3 esetén B-nek van nyerési stratégiája.
Végül n0=5 esetén n0≤n1≤n02 miatt n1 prímhatvány, vagy n1≤42 (amire már láttuk, hogy B-nek van nyerési stratégiája), vagy pedig n1=18, 20, 21, 22, 24, és ezeket az n2=2, 22, 3, 2, 3 választással rendre visszavezethetjük a már megvizsgált n0≤4 esetre (n0 szerepét n2 veszi át).
Összességében tehát kimondhatjuk, hogy 2≤n0≤5 esetén B-nek van nyerési stratégiája.
Meg kell még vizsgálnunk az n0=6,7 esetet. Mivel a B-nek győzelmet jelentő n0 kezdőértékek lehetséges értékeit nem tudjuk a szokásos módszerünkkel tovább növelni, ezért igen valószínűnek látszik, hogy n0=6,7 esetén egyik játékos sem tudja kikényszeríteni a győzelmet. Ehhez csak azt kell igazolnunk, hogy mind A, mind B tud úgy játszani, hogy a másik ne nyerhessen.
Legyen tehát n0=6 vagy 7, és A válassza az n1=30=2⋅3⋅5 számot, amelyre nyilván n0<n1<n02. B ezután csak n2=2⋅5=10-et, vagy n2=3⋅5=15-öt, vagy n2=2⋅3=6-ot választhat.
Az n2=10,15 esetben ‐ mint már láttuk ‐ A-nak van nyerési stratégiája, az n2=6 eset pedig A szempontjából ekvivalens az n0=6 kezdéssel (tehát újra jöhet n0=30, stb.) így beláttuk, hogy ha A ügyesen játszik, akkor B nem nyerhet.
Ugyanez áll viszont B-re is. Ha ugyanis n0=6 vagy 7, akkor 6≤n1≤49, és ha végignézzük a 6, 7, ..., 49 számokat, azt találjuk, hogy B mindig tud olyan n2 számot mondani, amelyre n2≤6. Ha n2≤5, akkor a fentiek miatt nyerési stratégiája van B-nek (esetleg n2=1), ha pedig n2=6, akkor ugyanolyan helyzetet kapunk, mint amilyennel kezdtük a játékot (amikor n0=6, 7).
Ezzel a feladatot megoldottuk, eredményeinket a következőképpen foglalhatjuk össze:
a) A-nak van nyerési stratégiája, ha 8≤n0,
b) B-nek van nyerési stratégiája, ha 2≤n0≤5, végül
c) egyik játékos sem tudja kikényszeríteni a győzelmet, ha n0=6,7.
Harcos Gergely
 

6. Bizonyítsuk be, hogy létezik olyan konvex 1990-szög, amelyik rendelkezik az alábbi két tulajdonsággal:
a) A sokszög minden szöge egyenlő.
b) Az oldalak hosszai az 12, 22, 32, ..., 19892, 19902 számok valamilyen sorrendben.
Jelölje ε a 995-ik komplex egységgyökök közül az elsőt. Tekintsük a következő 995 tagú összeget:
S=0⋅ε0+199⋅ε199+398⋅ε398+597⋅ε597+796⋅ε796+(1)+1⋅ε5+200⋅ε204+399⋅ε403+598⋅ε602+797⋅ε801++2⋅ε10+201⋅ε209+400⋅ε408+599⋅ε607+798⋅ε806++...+198⋅ε990+397⋅ε194+596⋅ε393+795⋅ε592+994⋅ε791+
(Minden tag ε-os szorzandója a felette levőének ε5-szerese. Felhasználjuk, hogy ε995=1. Az együtthatók a 995-ik egységgyököket megszorozzák a [0; 994] intervallum egészeivel. Az (1)-et a nem nulla (1-ε199)-el szorozva:
(1-ε199)S=0⋅ε0-0⋅ε199+199⋅ε199-199⋅ε398+398⋅ε398-⋅394⋅ε597+(2)+597⋅ε597-597⋅ε796+796⋅ε796-796⋅ε995+...==-796⋅ε0+199⋅ε199+199⋅ε398+199⋅ε597+199⋅ε796+...==199(ε0+ε1+ε2+ε3+...+ε994︸S1)-995(ε0+ε5+ε10+ε15+...+ε990)︸S2.



Mivel S1=S2=0, ezért (1-ε199)S=0, amiből S=0, innen 995(997S1+2S)=0. Így a 995-ik egységgyökök megszámozhatóak a 995⋅997, 995⋅999, ..., 995⋅2985 számokkal úgy, hogy minden egységgyököt a rá írt számmal megszorozva, majd az így kapott vektorokat összeadva nullvektort kapunk. A 995(995+2k) hosszúságú vektort egy vele egyirányú (995+i)2, és egy vele ellentétes irányú i2 hosszúságú vektorral helyettesítve az összeg változatlan marad, hiszen (995+k)2-k2=995(995+2k). Tehát az 1990-edik egységgyököket megszámoztuk az 12, 22, 32, ..., 19902 számokkal úgy, hogy mindegyiket a ráírt számmal szorozva, majd ezeket összeadva az összeg a nullvektor lesz. Másrészt azonban ezeket a súlyozott egységgyököket növekvő argumentum szerint az ,,orr-farok'' módszerrel egymás után rakva éppen egy, a feladatban kért 1990-szöget kapunk.
 

Csirik János