Cím: A 60. Nemzetközi Matematikai Diákolimpia feladatainak megoldása II.
Szerző(k):  Haiman Milán ,  Matolcsi Dávid ,  Nagy Nándor 
Füzet: 2019/november, 450 - 455. oldal  PDF file

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.

 
Második nap*

 

 
4. Határozzuk meg az összes olyan, pozitív egészekből álló (k,n) számpárt, amire
k!=(2n-1)(2n-2)(2n-4)(2n-2n-1).

 
Matolcsi Dávid megoldása. Legyen
T=(2n-1)(2n-2)(2n-4)...(2n-2n-1).
T-ben a 2 kitevője 0+1+2+...+(n-1)=n(n-1)2. A k!-ban a 2 kitevője
i=1[k2i]i=1k2i=k.
Tehát, ha k!=T, akkor n(n-1)2k.
Nyilván T<(2n)n=2n2, és
k!>j=[k2]kj>(k2)k2(n2-n4)n2-n4.
Így, ha T=k!, akkor
2n2>(n2-n4)n2-n4.
Az n24 gyök vonása szigorúan monoton növekvő függvény, így
24>(n2-n4)n-1n.
Itt n11-re
(n2-n4)n-1n>271011,és27101611>1,51016>1.
Ezek alapján 2710>1611, tehát 271011>16=24. Vagyis n11-re nem teljesülhet az egyenlőség, azaz n10.
Az n=1-re T=1, ekkor k=1 jó megoldás; n=2-re pedig T=6, így k=3 is jó megoldás.
Az n=3-ra T=168, erről könnyen ellenőrizhető, hogy nem írható fel k! alakban.
Az n=4-re T=1514128, ez sem írható föl k! alakban.
Ha n5, akkor T osztható 2n-2n-5=312n-5-nel, tehát osztható 31-gyel.
Így, ha T=k!, akkor k31. Ekkor viszont k!>1616=264, ezért 2n2>T miatt n>8, azaz n9, így T osztható 2n-2n-7-nel, ami osztható 127-tel. Ha viszont k! osztható 127-tel, akkor k127, így k!>6060>2300 szerint n>17. Ez azonban lehetetlen, mert már beláttuk, hogy n10.
Tehát csak két megoldása van a feladatban szereplő egyenlőségnek: n=1 és k=1, illetve n=2 és k=3.
 
5. Bath Bankja érméket bocsát ki, melyeknek egyik oldalán H, másik oldalán T betű látható. Harrynek n ilyen érméje van, amelyek előtte balról jobbra, egy sorban vannak elrendezve. Harry ismételten végrehajtja a következő műveletet: ha pontosan k>0 olyan érme van, amin H van felül, akkor megfordítja a balról k-adik érmét; máskülönben minden érmén T van felül, és ekkor Harry megáll. Például n=3 esetén a THT sorozatból indulva THTHHTHTTTTT a lépések sorozata, ami három lépés után megáll.
(a) Bizonyítsuk be, hogy bármi legyen is a kiindulási sorozat, Harry véges sok lépés után megáll.
(b) Minden C kiindulási sorozatra jelölje L(C) azt a lépésszámot, ahány lépés után Harry megáll. Például L(THT)=3 és L(TTT)=0. Határozzuk meg L(C) átlagos értékét, amint C végigfut a 2n lehetséges kiinduló sorozaton.

 
Nagy Nándor megoldása. (a) Tekintsük azt a mutatót, amely mindig éppen a k-adik érmére mutat. Mivel minden fordítás során k értéke pontosan eggyel változik meg, ezért a fordítás után a mutató H és T esetén rendre balra, illetve jobbra lép egyet.
Hogyha a mutatótól jobbra már nincsen H érme, akkor pontosan k lépésen belül fejeződik be az eljárás, hiszen ekkor az első k érme mind H oldalával van felül.
Minden más helyzetben k véges sok lépésben megdönti saját korábbi rekordját. Ennek igazolásához haladjunk végig a rekordokon. Abban az esetben, ha a mutató helyén T van, akkor egyből jobbra lép, k értéke 1-gyel nő, azaz megdöntötte a rekordot. Egyébként pedig egészen addig lép balra, amíg H oldalú érmékre mutat, de lesz tőle balra T oldalú is, hiszen az eltérő esetet már megvizsgáltuk. Ennél az érménél megfordul a mutató mozgása, és az imént T-re fordított elemeken is jobbra fog lépni a mutató, vagyis ismét megdönti a rekordját.
Tehát véges sok lépés alatt elő fog fordulni, hogy az első k érme H oldalával van felül, hiszen a rekord legfeljebb n lehet.
(b) Létezik bijekció az n érméből álló összes állapot és az n+1 érméből álló H-ra végződő összes állapot között, amelyre az egyes állapotok irányított gráfja izomorf lesz: A bijekcióhoz fordítsunk minden érmét a túloldalára, ezután az egész sorozatot tükrözzük (eleje és vége helyet cserél) és a sorozat végére tegyünk még egy H érmét.
Az n=3 esethez tartozó állapotok:
 
  I.TTTTTHTHTTHHHTTHTHHHTHHH12345678II.HHHHTHHHHTHHTTHHHHTHTHTHHTTHTTTH12345678  
 

 

Az n=3 esethez tartozó irányított gráf

Ha az I. esetben k darab H érme volt, akkor a II. esetben n-k+1 lesz, így a mutató pozíciója az I. esetben a k., míg a II.-ban az n-k+1. helyen van. Mivel az érméket megfordítottuk, tükröztük és a végére tettünk még egy (H) érmét, így az I. esetbeli k. érme a II. esetben éppen az n-k+1., és a másik oldala van felül. Tehát a mutató éppen az ellenkező irányba mozog a II. esetben, mint az I. esetben, és a II. esetbeli új állapot éppen az I. esetbeli új állapot bijekció szerinti megfeleltetése. Az n szerinti teljes indukcióval igazoljuk, hogy L(C) várható értéke n(n+1)4. Kiinduló lépésként tekintsük az n=1 esetet, ahol valóban 12 a lépésszám várható értéke. Az indukciós lépés során n-ről (n+1)-re lépünk, és két esetet különböztetünk meg:
Ha a sorozat utolsó érméje T (az esetek fele), akkor a mutató pontosan ugyanúgy viselkedik, mint n érme esetén.
Különben pedig idáig (az utolsó érméig) el kell jutnia egyszer a mutatónak, ami csakis akkor lehet, ha már az összes érme H oldalát mutatja. Minden egyes ilyen lépéssorozatnak a bijekció miatt megfeleltethető egy lépéssorozat az előző esetből, vagyis a mutató a végig H állapotig várható értékben n(n+1)4 lépést fog tenni. Persze még el kell érni a végig T állapotot, ami további n+1 lépést igényel.

Mivel a két eset egyformán valószínű, így az L(C) várható értéke a két szám átlaga:
n(n+1)4+n(n+1)4+(n+1)2=(n+2)(n+1)4,
tehát működik az indukciós lépés.
 
6. A hegyesszögű ABC háromszög, amiben ABAC, beírt körének a középpontja I. Az ABC háromszög ω beírt köre a BC, CA, AB oldalakat rendre a D, E, F pontokban érinti. A D-ből EF-re bocsátott merőleges egyenes és az ω kör második metszéspontja R. Az AR egyenes és az ω kör második metszésponta P. A PCE és a PBF háromszögek körülírt köreinek második metszéspontja Q.
Bizonyítsuk be, hogy a DI és PQ egyenesek az AI-ra A-ban állított merőleges egyenesen metszik egymást.

 
Haiman Milán megoldása. Legyen S az A csúcshoz tartozó külső szögfelező metszéspontja ID-vel. Megmutatjuk, hogy PS, (PCE) és (PBF) áthaladnak egy P-től különböző ponton. E pont lesz majd Q, ahonnan következik, hogy P, Q és S az állításnak megfelelően valóban kollineárisak.
A PS egyenes és a (PCE), (PBF) körök P-től különböző közös pontjának megmutatásához alkalmazzunk a beírt körre vonatkozó inverziót. Így a D, E, F, R, P pontok helyben maradnak. Az A, B, C, S pontok inverz képét jelölje rendre A', B', C'S'. Innen már elég megmutatni, hogy (PS'I), (PC'E) és (PB'F) egy P-től különböző pontban találkoznak. Ez azzal ekvivalens, hogy a három kör koaxiális, ami pedig ekvivalens azzal, hogy a középpontjaik kollineárisak.
A három középpont kollineáris elhelyezkedését komplex számok segítségével bizonyítjuk, ahol a beírt kört tekintjük egységkörnek. Legyenek a, d, e, f, p, r, b, c, s az A, D, E, F, P, R, B', C', S' pontoknak megfelelő komplex számok. Az érintők metszéspontjára vonatkozó összefüggés miatt
a=2efe+f.
Ebből a¯=2e+f. Mivel DREF, dr+ef=0. Így r=-efd. Ekkor mivel A rajta van a PR húr egyenesén, a+pra¯=p+r. Ebből p értékére a
p=r-ara¯-1=-efd-2efe+f-efd2e+f-1=ef(2d+e+f)2ef+de+df
kifejezés adódik.
Következő lépésként számítsuk ki a (PB'F) kör középpontját. Legyen a középpont jB. A körülírt körre vonatkozó összefüggés alapján
jB=|ppp¯1fff¯1bbb¯1||pp¯1ff¯1bb¯1|.

Először a számlálóban álló determinánst számítjuk ki. Tudjuk, hogy pp¯=ff¯=1, mivel P és F rajta vannak az egységkörön. Másrészt b=d+f2, mivel B'DF szakasz felezőpontja. Ezért b¯=d+f2df. A jB számlálója így
|p11f11d+f2(d+f)24df1|=p+(d+f)2f4df+d+f2-f-(d+f)2p4df-d+f2==(p-f)(1-(d+f)24df).
A jB nevezője pedig
|p1p1f1f1d+f2d+f2df1|=pf+(d+f)f2df+d+f2p-(d+f)p2df-fp-d+f2f==(f-p)(d+f2df+d+f2pf-p+fpf).
Így jB értéke
(d+f)24df-1d+f2df+d+f2pf-p+fpf=p(d-f)22(pd+pf+d2+df-2dp-2df)==p(d-f)22(d-f)(d-p)=p(d-f)2(d-p).
Ugyanígy a (PC'E) kör jC középpontja p(d-e)2(d-p). Ezután számítsuk ki a (PS'I) kör középpontját. Vegyük észre, hogy s a beírt kör D pontjából húzott átmérőre A'-ból állított merőleges talppontja. Ezért
s=12(e+f2+d+(-d)-d(-d)(e+f2)¯)=12(e+f2+d2e+f2ef)==(e+f)(ef+d2)4ef.
Vegyük észre továbbá, hogy
s¯=e+f4(1ef+1d2)=sd2.
A körülírt körre vonatkozó formulát (PS'I)-re alkalmazva kapjuk, hogy
|ppp¯1sss¯1001||pp¯1ss¯1001|=pss¯-pp¯sps¯-p¯s=ps2d2-spsd2-sp=p(ps-d2)p2-d2.


Azt kell megmutatnunk, hogy p(d-e)2(d-p), p(d-f)2(d-p) és p(ps-d2)p2-d2 kollineárisak. Alkalmazzunk p2(d-p) arányú nagyítást, akkor ekvivalens módon azt kell belátnunk, hogy d-e, d-f és 2(ps-d2)p+d kollineárisak. Kiszámítva
ps=ef(2d+e+f)2ef+de+dfe+f4d2+efef=(2d+e+f)(e+f)(d2+ef)4(2ef+de+df)
értékét,
2(d2-ps)=24(2ef+de+df)d2-(2d+e+f)(e+f)(d2+ef)4(2ef+de+df)==4d3(e+f)+8d2ef-2d3(e+f)-d2(e+f)22(2ef+de+df)++-2def(e+f)-ef(e+f)22(2ef+de+df)==2d3(e+f)+d2(-e2+6ef-f2)-2def(e+f)-ef(e+f)22(2ef+de+df)==(2d-e-f)(d2(e+f)+4def+ef(e+f))2(2ef+de+df).
Figyelembe véve, hogy
p+d=2def+e2f+ef2+2def+d2e+d2f2ef+de+df=d2(e+f)+4def+ef(e+f)2(2ef+de+df),
adódik, hogy
2(d2-ps)p+d=2d-e-f2=12((d-e)+(d-f)).
Vagyis (PS'I) középpontja a (PB'F) és (PC'E) középpontjai által meghatározott szakasz felezőpontja. A három középpont tehát kollineáris, az állítást beláttuk.  

*Az első nap feladatainak megoldását az októberi számban közöltük.