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 háromszög beírt körének középpontját -vel, a , , szögek szögfelezőinek metszéspontját a szemközti oldalakkal pedig rendre -vel. Bizonyítsuk be, hogy | | (USA)
Megoldás. Legyenek az háromszög oldalai a szokásos jelöléssel és .
Segédtétel: Ismert, hogy
(Ennek bizonyítása két szögfelező tétel segítségével: , így ahonnan valóban A számtani és mértani közepek közötti egyenlőtlenséget használva, és az összefüggést felismerve kapjuk, hogy | | és egyenlőség csak szabályos háromszögnél áll fenn. Másfelől az és számokra teljesül a háromszög-egyenlőtlenség, így . Ezt beszorozva és rendezve: | | Mindkét oldalhoz hozzáadva -t, majd szorzattá alakítva kapjuk, hogy | | azaz | |
Ezzel a bizonyítandó két egyenlőtlenséget beláttuk.
Matolcsi Máté
2. Legyen egész szám és , , , az összes olyan természetes szám, amely kisebb -nél és relatív prím -hez. Tegyük fel, hogy | | Bizonyítsuk be, hogy ekkor prímszám, vagy -nek egész kitevős hatványa. (Románia) Megoldás. Legyen . Mivel , ezért . Mivel minden pozitív egész -re , ezért , továbbá nyilván .
I. Legyen először páratlan. Ekkor . (Ugyanis és esetén , de páratlan, így , ezért . Így viszont és ekkor minden -nél kisebb pozitív egész relatív prím -hez, azaz -nek nincs nála kisebb valódi osztója; így prím, ahogy a feladat állítja.
II. Legyen most páros, és írjuk fel alakban, ahol és páratlan. a) Ha , akkor -hatvány, ahogy állítottuk; ekkor a feltétel nyilván teljesül, hiszen az -k éppen az -nél kisebb páratlan számok és . b) Ha volna, akkor miatt és , ez pedig lehetetlen. c) Legyen végül . Megmutatjuk, hogy ekkor és szerepel az -k között. Tegyük fel ugyanis, hogy és . Ekkor miatt . De páratlan, így , azaz . Hasonlóan . Nyilván nem szerepel az -k között, hiszen páros; így . De ekkor is szerepel az -k között (az -k rendre ). Ez viszont ellentmondás, mert . Beláttuk tehát, hogy prím vagy -hatvány, a bizonyítást befejeztük.
Szendrői Balázs
3. Legyen . Határozzuk meg azt a legkisebb egész számot, amelyre igaz az, hogy minden elemű részhalmaza tartalmaz olyan számot, amelyek páronként relatív prímek. (Kína)
Megoldás. Válasszuk ki az halmazból a , a , az és a 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 -ből kiválasztott elemek száma a szita-formula segítségével kiszámolva . Ezért a keresett egész legalább . Bebizonyítjuk, hogy esetén már teljesül a feltétel. Ehhez vizsgáljuk meg, hogy legfeljebb hány elem lehet -nek egy olyan részhalmazában, amelyben nincs olyan szám, amelyek páronként relatív prímek. A fent megadott elemű halmaz kiválasztásakor elhagytuk a prímek és az 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: | |
Az eredeti feltételnek nem megfelelő bármely halmazban is a prímek és az közül legfeljebb lehet, különben lenne 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 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 -ből ahhoz, hogy a feltétel ne teljesüljön. A halmazok:
Tehát, ha kiválasztunk -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 szám a 217. Ujváry-Menyhárt Zoltán
4. Legyen a összefüggő gráf éleinek száma . Bizonyítsuk be, hogy meg lehet az éleket számozni az 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 .
[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ő csúcs között legfeljebb egy él halad. A gráfot összefüggőnek nevezzük, ha bármely két különböző csúcshoz található csúcsoknak egy olyan sorozata, hogy minden 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 (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 -ből -be, -ből -ba, -ből -be, végül -ből -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 -t érintünk és elhagyunk legalább egyszer. Tegyük fel, hogy utazásunk alatt sorra számozzuk az érintett éleket az számokkal ‐ 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 db élt számoztunk meg a db él közül. Az utazásnál még egy dologra kell ügyelnünk: Ha valamelyik csúcsot először érintjük utazásunk során (ez biztosan bekövetkezik minden -re valamikor), akkor -t másik élén keresztül hagyjuk el, mint amilyenen keresztül megközelítettük; ez megtehető, mert legalább másodfokú. Mivel az -ből kiinduló élek egyikét sem érintettük azelőtt, ezért a számozási algoritmus szerint ebben a lépésben -nek élére 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 -ből kiinduló egyik élre (utazásunk első élére) az -et írjuk, ‐ -ből kiindul olyan él, amelyre szomszédos számokat írunk. Mivel és pozitív egészek relatív prímek egymáshoz, ha vagy , ezért a megoldás elején megfogalmazott követelményünk teljesül, vagyis ‐ a fennmaradó db élt tetszőlegesen megszámozva az számokkal ‐ a feladat állítását beláttuk. Harcos Gergely
5. Legyen az háromszög belső pontja. Bizonyítsuk be, hogy a , , szögek közül legalább egy kisebb, vagy egyenlő, mint . (Franciaország)
Megoldás. Használjuk az ábra jelöléseit.
Vegyük észre, hogy | |
Tegyük fel, hogy a feladat állítása nem igaz, tehát és is nagyobb, mint . Ha például és is kisebb, mint , így máris ellentmondásra jutottunk. Ha pedig és mindegyike kisebb -nál, akkor . Ugyanakkor a számtani és a mértani közepek közti egyenlőtlenség szerint | | A Jensen-egyenlőtlenséget felhasználva (hisz a függvény a intervallumon konkáv) | | De mivel , így | | vagyis | | Ezzel ellentmondásra jutottunk, tehát bizonyítottuk a feladat állítását. Kőszegi Botond
6. Valós számok egy sorozatát korlátosnak nevezzük, ha létezik olyan konstans, hogy minden -ra. Minden rögzített valós számhoz konstruáljunk olyan korlátos, végtelen sorozatot, amelyre teljesül bármely két különböző, nemnegatív egészre. (Hollandia)
I. megoldás. Tetszőleges esetén, ha diadikus alakja | | akkor legyen ahol a feladatban rögzített valós szám. Legyen most , továbbá és kettes számrendszerbeli alakja | |
Feltehető, hogy , és ekkor . Tegyük fel továbbá, hogy az a természetes szám, amelyre és diadikus alakja az utolsó db jegyben megegyezik, de -edik jegyében ‐ hátulról olvasva ‐ már különbözik: esetén legyen . Ekkor és miatt
Ezt -gyel egybevetve: | | ami azt jelenti, hogy az sorozat esetén továbbá korlátos volta miatt is korlátos: | | Ezzel a feladatot megoldottuk.
II. megoldás. Konstrukciót adunk az esetre ‐ ez nyilván megfelelő esetére is. Alapötletünk a következő: Tegyük fel, hogy olyan (irracionális) szám, amelynek minden közelítő törtjére az eltérés ahol valamilyen rögzített konstans. Ekkor tekintjük az sorozatot, ahol a szám törtrészét jelöli. Világos, hogy korlátos: továbbá esetén ( feltehető ) | | ill. a jelöléssel és egészek, tehát (2) szerint | | vagyis az sorozat megfelelő. Az is látszik, hogy az | | tehát az sorozat is megfelelő. Ezek szerint csak a -t kielégítő -t és -t kell találnunk, sőt minél kisebb az , annál jobb a sorozatunk korlátja. -re talán és adja a legegyszerűbb példát: mindig fennáll. Ha ugyanis lenne olyan közelítő tört, amelyre akkor azaz négyzetre emelés és rendezés után | | lenne, amiből következnék. nyilván nem állhat fenn esetén, ezért , tehát | | vagyis hiszen nemnegatív egész. Mivel irracionális, ezért ellentmondást jelent, ami -at igazolja. Ezzel sikerült megadnunk olyan () sorozatot, amelyre | | teljesül, ha . Harcos Gergely
|