Cím: 1999. évi Kürschák József Matematikai Tanulóverseny feladatainak megoldása
Szerző(k):  Károlyi Gyula 
Füzet: 2000/február, 66 - 71. oldal  PDF file
Témakör(ök): Egyéb (KöMaL pontverseny is)

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.

 
1. Adjuk össze az 1, 2, ..., n természetes számok pozitív páros osztóinak számát, majd végezzük el ugyanezt a páratlan osztókkal is. Mutassuk meg, hogy a két összeg eltérése nem nagyobb n-nél.
 
Megoldás. Jelölje a szóban forgó összegek közül az elsőt D1(n), a másodikat pedig D2(n).
D1(n) meghatározásánál minden, az n-nél nem nagyobb pozitív páros számot annyiszor kell figyelembe vennünk, ahány többszöröse van az 1, 2, ..., n számok között. Ezért D1(n)=2jnsn(2j), ahol sn(k) jelöli a k pozitív egész 1 és n közé eső többszöröseinek számát: sn(k)=n/k. Hasonlóképpen D2(n)=2j-1nsn(2j-1). Világos, hogy k<l esetén sn(k)sn(l), így a D1(n) összeg minden egyes sn(2j) tagját felülről becsülhetjük a D2(n) összeg megfelelő sn(2j-1) tagjával. Következésképpen D1(n)D2(n). Hasonlóképpen, az első tag sn(1)=n kivételével, a D2(n) összeg minden egyes sn(2j-1) tagja (j2) megbecsülhető a D1(n) összeg megfelelő sn(2(j-1)) tagjával, ezért D2(n)n+D1(n). A két egyenlőtlenség összevetéséből a feladat állítása azonnal leolvasható.
 

Megjegyzések. 1. A feladatot Pósa Lajos bocsátotta a versenybizottság rendelkezésére.
2. A fenti bizonyítást finomíthatjuk olyan módon, hogy az egyes összegek első néhány tagjára alkalmazzuk az sn(k)=n/k képletet, és csak a fennmaradó tagokat becsüljük a másik összeg megfelelő tagjaival. Így a D1(n)D2(n) egyenlőtlenség helyett például n2 esetén az erősebb D1(n)-n2D2(n)-n becslést alkalmazhatjuk, ahonnan n/2D2(n)-D1(n)n következik. Általában tetszőleges k pozitív egész számra felírható n2k+1 esetén a
j=1kn2j-1-j=1kn2jD2(n)-D1(n)j=1k+1n2j-1-j=1kn2j
egyenlőtlenség, amelyből kiindulva az ln(k+1)<1+12+...+1k<1+lnk becslésre támaszkodva nem nehéz megmutatni, hogy a (D2(n)-D1(n))/n sorozat határértéke ln2.
Terpai Tamás dolgozatában azt is megmutatta, hogy a D2(n)-D1(n) különbség nln2-től való eltérése n nagyságrendű. (Erre vonatkozóan lásd még az 1999. decemberi számunk A. 225. számú feladatát.)
 
2. Legyen adott a síkon egy háromszög. Szerkesszük meg a háromszög belsejében azt a P pontot, amelyikre igaz, hogy azt a háromszög oldalegyeneseire vetítve, a vetületi pontok alkotta háromszög súlypontja éppen P.
 
I. megoldás. A háromszög csúcsait jelölje A, B és C, a P pont vetületei a BC, CA, AB oldalakra pedig legyenek rendre X, Y és Z. P pontosan akkor súlypontja az XYZ háromszögnek, ha a PX, PY, PZ egyenesek rendre felezik az YZ, ZX, XY szakaszokat.
Vizsgáljuk meg, mit jelent az, hogy a PZ egyenes felezi az XY szakaszt. Ha a PZ és XY egyenesek metszéspontját Z'-vel, az X és Y pontok AB egyenesre eső vetületeit pedig XAB-vel és YAB-vel jelöljük, úgy YZ'=Z'X akkor és csak akkor teljesül, ha YABZ=ZXAB, vagyis ha
YPsin(YPZ')=XPsin(XPZ').
Tegyük fel az egyszerűség kedvéért, hogy Z az AB szakasz belső pontja. Ekkor az 1. ábráról, az AZPY és BXPZ húrnégyszögeket figyelembe véve, leolvasható, hogy
YPZ'=180-YPZ=YAZ=α,
és
XPZ'=180-XPZ=XBZ=β.
A 2. ábra mutatja, hogy ez akkor is igaz, ha a Z pont esetleg egybeesik az AB szakasz valamelyik végpontjával, vagy azon kívül helyezkedik el.
A szinusztétel alapján tehát a PZ egyenes pontosan akkor felezi az XY szakaszt, ha
1=YZ'Z'X=YPsinαXPsinβ=YPXP:ACBC,
vagyis ha YPXP=ACBC. Azon P pontok, amelyekre ez az összefüggés teljesül, egy C-n áthaladó eC egyenesre illeszkednek, amelyet megszerkeszthetünk úgy, hogy az AC és BC egyenesekkel, azoknak a háromszöget tartalmazó oldalán, azoktól AC, illetve BC távolságban párhuzamosokat húzunk, és ezek metszéspontját összekötjük a C ponttal.
Hasonlóképpen, a PX (PY) egyenes pontosan akkor felezi az YZ (XZ) szakaszt, ha ZPYP=ABAC (XPZP=BCAB). Világos, hogy a három feltétel közül bármely kettő teljesülése maga után vonja a harmadik teljesülését is.
Ha P az XYZ háromszög súlypontja, akkor szükségképpen illeszkedik az eC egyenesre, és arra az eA egyenesre is, amelyet úgy szerkeszthetünk meg, hogy az AB és AC egyenesekkel párhuzamosokat húzunk, azoknak a háromszöget tartalmazó oldalán, tőlük AB, illetve AC távolságban, és ezen párhuzamosok metszéspontját az A csúccsal összekötjük. Az eA és eC egyenesek az ABC háromszög belsejében metszik egymást. A keresett P pont nem lehet más, mint ez a metszéspont, és ez valóban jó is.
 
II. megoldás. (Terpai Tamás gondolata alapján.) Az előző megoldás jelöléseit megtartva megállapithatjuk, hogy P pontosan akkor súlypontja az XYZ háromszögnek, ha PX+PY+PZ=0. Forgassuk el ezeket a vektorokat P körül az óramutató járásával ellentétes irányban 90-kal. Az így nyert PX1, PY1, PZ1 vektorok rendre párhuzamosak és egyirányúak a háromszög BC, CA és AB oldalvektoraival. Mivel az AB, BC, CA vektorok közül semelyik kettő nem párhuzamos, továbbá BC+CA+AB=0, a PX1+PY1+PZ1=0 összefüggés pontosan akkor áll fenn, ha van olyan λ pozitív szám, amelyre PX1=λBC, PY1=λCA és PZ1=λAB. A P pont tehát pontosan akkor súlypontja az XYZ háromszögnek, ha
PXBC=PYCA=PZAB,
ahonnan a megoldás az előzővel megegyező módon fejezhető be.
 
III. megoldás. Az XYZ háromszöget fogjuk megszerkeszteni. Ezután P már igen egyszerűen megszerkeszthető az XYZ háromszög súlypontjaként, vagy az AB, BC egyenesekre az Z, illetve X pontban emelt merőlegesek metszéspontjaként. A szerkesztést két lépésben végezzük: először egy, a keresett háromszöghöz hasonló, azzal megegyező állású háromszöget szerkesztünk, majd alkalmas hasonlósági transzformációval azt a keresett XYZ háromszögbe visszük.
Vegyünk fel egy tetszőleges Q pontot a háromszög belsejében, és indítsunk a Q pontból az AB, BC, CA oldalegyenesek irányába, azokra rendre merőleges sAB, sBC, sCA félegyeneseket. Ezek rendre megegyező irányúak a PZ, PX, PY vektorokkal. Olyan X*Y*Z* háromszöget keresünk, amelynek súlypontja Q és amelyben a QX*, QY*, QZ* vektorok rendre párhuzamosak a PX, PY, PZ vektorokkal. Ez csak úgy lehet, ha X*, Y*, Z* rendre az sBC, sCA, sAB félegyenesekre esnek. Tegyük fel, hogy X*-ot már kijelöltük az sBC félegyenesen.
Mivel tetszőleges háromszög súlyvonalai harmadolják egymást, nem nehéz megmutatni, hogy az Y*, Z* pontok úgy szerkeszthetők meg, hogy az X* pontot Q-ra tükrözzük, majd a tükörképen keresztül az sAB, sCA félegyenesekkel párhuzamosokat húzunk. Ezek metszik ki az sCA, sAB félegyenesekből az Y*, Z* pontokat. Világos, hogy bármely megoldás hasonló a keresett XYZ háromszöghöz, sőt azzal egyállású is. Válasszuk ki azt a megoldást, ahol X* a BC egyenesre esik. Az ABC háromszög valamelyik oldalára két hegyesszög illeszkedik. Ha feltesszük, hogy a BC oldal ilyen, akkor X* a BC szakasz belső pontja. Megmutatjuk, hogy pontosan egy olyan XYZ háromszög van, amely X*Y*Z*-gal egyállású és X, Y, Z csúcsai rendre a BC, CA, AB egyenesekre esnek. Van olyan X* középpontú, pozitív arányú nagyítás, amely az X*Y*Z* háromszöget olyan X*Y**Z** háromszögbe viszi, ahol Y** az AC szakaszra vagy pedig Z** az AB szakaszra esik, és ez igen egyszerűen meg is található, ha megkeressük az X*Y*, illetve X*Z* félegyeneseknek az ABC háromszög kerületével alkotott metszéspontjait. Tegyük fel az egyszerűség kedvéért, hogy Y** az AB szakaszra esik. Ekkor az XYZ háromszöget meg kell kapnunk az X*Y**Z** háromszögből egy C középpontú, pozitív arányú nagyítással. Egyetlen ilyen nagyítás létezik: a Z pont megszerkeszthető mind a CZ** félegyenes AB egyenessel alkotott metszéspontja. Világos, hogy a kapott XYZ háromszög megfelelő lesz.
 
IV. megoldás. (Árvay Eszter ötlete.) Egy, az XYZ háromszöggel egyállású háromszög megszerkesztését a következő gondolatra támaszkodva is elvégezhetjük. Tegyük fel, hogy P az XYZ háromszög súlypontja, és tükrözzük P-t az XYZ háromszög oldalfelező pontjaira (4. ábra).
Az így keletkező XZ''YX''ZY'' hatszög felbontható 6 egybevágó háromszögre (XPZ'', Z''PY, YPX'', X''PZ, ZPY'', Y''PX) amelyek hasonlók az ABC háromszöghöz. Ugyanis, az előző megoldásban leírt módon látható, hogy például XZ''P=Z''PY=Z'PY=CAB. Az ABC háromszög 6 egybevágó példányát alkalmas módon egymáshoz illesztve tehát az XZ''YX''ZY'' hatszöggel egyállású hatszöget szerkeszthetünk. Innen a megoldás a III. megoldáséval megegyező módon fejezhető be.

 
Megjegyzések. 1. Harangi Viktor észrevette, hogy a keresett P pont rajta van az ABC háromszög súlyvonalainak az azonos csúcsból induló szögfelezőkre vonatkozó tükörképein, az ún. szimmediánsokon. Ezek egy pontban metszik egymást, amelyet a háromszög szimmediáns-pontjának nevezhetünk, ez tehát a szerkesztendő P pont. Ugyanezzel a ponttal találkozhatunk Lemoine- vagy Grebe-pont néven is.
2. Nem nehéz meggondolni (de némi diszkussziót igényel), hogy a háromszög határán vagy azon kívül soha nem létezik olyan pont, amely rendelkezne a kívánt tulajdonsággal.
3. Terpai Tamás azt is megvizsgálta, milyen esetben lesz P a vetületi pontok által alkotott háromszög valamely más nevezetes pontja (magasságpont, beírt kör középpontja, körülírt kör középpontja). Legnehezebb azonban kétségkívül a feladatban kitűzött eset.

 
3. Legyen adott 2k-nál több különböző egész szám, ahol k tetszőleges természetes számot jelöl. Bizonyítandó, hogy kiválasztható közülük k+2 úgy, hogy valahányszor valamilyen m pozitív egészre és x1<x2<...<xm, y1<y2<...<ym kiválasztott számokra
x1+x2+...+xm=y1+y2+...+ym
teljesül, úgy szükségképpen xi=yi minden 1im esetén.

 
I. megoldás. Az állítás nyilván igaz k=0 esetén. A bizonyítást teljes indukcióval fogjuk végezni. Legyen tehát k1, és tegyük fel, hogy k helyett (k-1)-et írva az állítás már igazolást nyert.
Jelöljön a1, a2, ..., a (>2k) különböző egész számokat. Meg kell mutatnunk, hogy kiválasztható közülük k+2 a feladatban megadott követelménynek megfelelően. Ezt pontosan akkor lehet megtenni, ha a 0=a1-a1, a2-a1, ..., a-a1 számok közül kiválasztható k+2 a megfelelő módon. Feltehetjük tehát a továbbiakban, hogy a számok között szerepel a 0. Továbbá, ha az a1, a2, ..., a számok mindegyike osztható egy q pozitív egész számmal, akkor elegendő az állítást a1, ..., a helyett az a1q, ..., aq számokra igazolni. Feltehetjük tehát, hogy a számok relatív prímek. Számaink között tehát szerepel páros és páratlan szám is. Vagy a páros vagy a páratlan számok száma nagyobb, mint 2k-1.
Tegyük fel először, hogy több, mint 2k-1 páratlan számunk van. Ezekből az indukciós feltevés alapján kiválasztható k+1 a követelménynek megfelelően. Jelölje ezeket b1, ..., bk+1, és legyen c valamelyik páros szám az a1, ..., a számok közül.
Tegyük fel, hogy a b1, ..., bk+1, c számok között van x1<x2<...<xm és y1<y2<...<ym úgy, hogy x1+x2+...+xm=y1+y2+...+ym teljesül. A c szám az egyenlőség mindkét oldalán legfeljebb egyszer fordulhat elő. Ha az x1+x2+...+xm ugyanolyan maradékot ad 2-vel osztva, mint m, akkor szükségképpen az xi és yi számok is mind páratlanok, és az x1=y1, ..., xm=ym egyenlőségek következnek az indukciós feltevésben a b1, b2, ..., bk+1 számokra kirótt feltételből. Ellenkező esetben a c szám az egyenlőség mindkét oldalán szerepel, azt mindkét oldalról elhagyva meggyőződhetünk arról, hogy a fennmaradó számok páronként egyenlők.
Hasonló módon okoskodhatunk akkor is, ha az a1, ..., a számok között a páros számokból van több, mint 2k-1.
 
II. megoldás. Feltehetjük, hogy a szóban forgó számok mindegyike pozitív, ezt ugyanis elérhetjük, ha mindegyik számot megnöveljük ugyanazzal az elegendően nagy pozitív egész számmal. Ha az újonnan kapott számokra teljesül az állítás, akkor az eredeti számokra is teljesülnie kell. Írjuk fel most a számokat kettes számrendszerben, és tekintsük azt a legkisebb helyiértéket, ahol valamely két szám különbözik. Jelölje ezt a helyet i1. Az összes szám megegyezik tehát az utolsó i1-1 helyen, az i1-edik helyen azonban bizonyos számokban 0 áll, a többiben pedig 1. Legyen b1 egyike azon számoknak, amelyekből kevesebb van; ha ugyanannyi van a két különböző típusból, akkor egy olyat válasszunk ki, amelynek (hátulról számítva) az i1-edik jegye 1.
Tekintsük a továbbiakban csak azokat a számokat, amelyek különböznek b1-től az i1-edik helyen. b1 kiválasztása miatt ezek száma nagyobb, mint 2k-1, és utolsó i1 jegyük rendre megegyezik. Jelölje i2 azt a legkisebb helyiértéket, ahol valamelyik két szám eltér, i2>i1. Különböztessük meg a számokat aszerint, hogy az i2-edik helyen milyen számjegy áll bennük, és válasszuk b2-t azok közül, amelyek kevesebben vannak, a másik csoport számmal (amelyekből több, mint 2k-2 van) pedig folytassuk ezt az eljárást. Ily módon olyan i1<i2<...<ik+1 helyiértékeket és b1, b2, ..., bk+1 számokat találunk, amelyekre igaz minden j=1, 2, ..., k esetén, hogy bj, bj+1, ..., bk+1 utolsó ij-1 jegye megegyezik, de bj ij-edik jegye különbözik bj+1, ..., bk+1 ij-edik jegyétől. Sőt, egy bk+2 szám is található, amelynek utolsó ik+1-1 jegye bk+1-ével megegyezik, de az ik+1-edik helyen a két szám eltér egymástól.
Tegyük fel most, hogy a b1, b2, ..., bk+2 számok között van x1<x2<...<xm és y1<y2<...<ym úgy, hogy x1+x2+...+xm=y1+y2+...+ym=S teljesül.
Az x1, x2, ..., xm, y1, y2, ..., ym számok utolsó i1-1 jegyéből álló szám mind megegyező, jelöljük ezt u1-gyel. Az S-mu1 szám utolsó i1-1 jegye tehát 0, és az i1-edik jegyet megvizsgálva eldönthető, hogy az x1, ..., xm (és ugyanígy az y1, ..., ym) számok között szerepel-e a b1. Ha nem, akkor áttérünk az utolsó i2 hely vizsgálatára. Ha igen, akkor mindkét oldalról töröljük a b1 összeadandót, és úgy térünk át az utolsó i2 jegy vizsgálatára. Ilyen módon a b1, b2, ..., bk+1 számokról sorra eldönthetjük, hogy szerepelnek-e az összegben: ha igen, akkor mind a két oldalon szerepelniük kell. Ezeket sorra elhagyva az egyenlőség mindkét oldaláról végül vagy a 0=0 egyenlőséghez jutunk, vagy mindkét oldalon egy-egy szám marad, amely kizárólag bk+2-vel lehet egyenlő.
 
Megjegyzések. 1. Mindkét bizonyítás egy algoritmust is szolgáltat a keresett k+2 szám kiválasztására, méghozzá lényegében ugyanazt az algoritmust.
2. Kézenfekvő kérdés, hogy 2k helyettesíthető-e valamely, annál kisebb számmal. Terpai Tamás észrevette, hogy van olyan pozitív c konstans, hogy c2kk3/2 mellett az állítás már nem igaz.
Ha ugyanis az első n számból ki lehet választani k+2 számot a kívánt feltétel mellett, akkor szükségképpen =k+22 esetén a számokból alkotott (k+2)42π2kk -tagú összeg mind különböző, márpedig ezek egyike sem lehet nagyobb, mint nnk2.

Károlyi Gyula