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 hagyományoknak megfelelően ebben az évben is közöljük a nyári matematikai diákolimpia feladatainak a megoldásait; lényegében úgy, ahogyan a legilletékesebbek, a magyar csapat tagjai leírták. Közreműködésüket köszönjük és ezúton is gratulálunk eredményeikhez.
1. Jelölje az egész számok halmazát. Határozzuk meg az összes olyan függvényt, amelyre minden egész , esetén teljesül
Szabó Kristóf megoldása. Jelölje a függvényegyenletet: | | Minden függvényegyenletet érdemes behelyettesítések kipróbálásával elkezdeni. Esetünkben a egy olyan helyettesítési érték, amely a képletben szereplő kifejezéseket jelentősen leegyszerűsíti:
A -nél felhasználtuk az egyenletet, majd rendezéssel kaptuk a -et. Az és -es egyenlettel jelentősen leegyszerűsíthető az eredeti egyenlet:
Ebből minden pozitív egészre:
hasonlóan, ha negatív: | | Legyen és . (Mivel egészek voltak, így és is az.) Az előzőek alapján . Visszahelyettesítve az eredetibe (): | | (4) | Az , helyére -t helyettesítve: Ezt kivonva a (4)-ből kapjuk, hogy: Ebből következik, hogy , tehát vagy . Ha , akkor (4.1) miatt , tehát . Ha , akkor tetszőleges -re megoldás lesz. Ellenőrzés: | |
Ezzel megadtuk az összes lehetséges függvényt.
2. Az háromszögben a oldalon, pedig az oldalon fekszik. Legyenek és rendre az és szakaszok olyan pontjai, amelyekre párhuzamos -vel. Legyen a egyenes egy olyan pontja, amire a szakasz belsejében fekszik, és . Hasonlóan legyen a egyenes egy olyan pontja, amire a szakasz belsejében fekszik, és . Bizonyítsuk be, hogy a , , , pontok egy körön fekszenek.
Schrettner Jakab megoldása. Legyen az és egyenesek második metszéspontja az háromszög körülírt körével rendre és . Szögszámolással kapjuk, hogy | | felhasználva, hogy és is az körön vannak. Ebből következik, hogy , , , egy körre esnek. Hasonlóan kaphatjuk, hogy , , , is egy körre esnek. Mivel párhuzamos -vel, illetve a fentebb kapott húrnégyszögek miatt | | így , , , egy körre esnek. Továbbá
Azaz , , , egy körre esnek. Így is rajta van a , , , pontokat tartalmazó körön. Ugyanezen szögszámolást elvégezve a másik oldalon kapjuk, hogy , , , is egy körre esnek, tehát is rajta van a , , , pontokat tartalmazó körön. Azt kaptuk tehát, hogy a , , , , , pontok mind egy körre esnek, amiből a feladat állítása is következik.
3. Egy szociális hálózatnak tagja van, közülük némely párok barátai egymásnak. Ha barátja -nek, akkor is barátja -nak. A következő típusú esemény előfordulhat többször egymás után, egy időben mindig csak egy ilyen esemény történik:
Ha , , olyanok, hogy barátja -nek is és -nek is, de nem barátja -nek, akkor barátságot változtathatnak úgy, hogy és most már barátai egymásnak, és , valamint és barátsága viszont megszűnik. Az összes többi barátság változatlan marad.
Kezdetben olyan tag van, amelyek mindegyikének pontosan barátja van, és olyan tag, amelyek mindegyikének pontosan barátja van. Bizonyítsuk be, hogy létezik a fenti típusú eseményeknek egy olyan sorozata, amelyek végén minden tagnak legfeljebb egy másik tag a barátja.
Zsigri Bálint megoldása. Gondoljunk a problémára egy gráfként. Vegyük észre, hogy minden lépésben az élek száma eggyel csökken, és hogy bármely csúcs fokszámának a paritása állandó marad. Figyeljük meg továbbá a kiinduló gráf következő tulajdonságait. A gráfban nem lehet teljes gráf komponens, mert annak 1010 vagy 1011 csúcsúnak kéne lennie (hiszen minden csúcs fokszáma 1009 vagy 1010), vagyis csak 1010 csúcsú lehet: az 1010 darab 1009 fokú csúcs; viszont ekkor tetszőleges 1010 fokú csúcsra igaz, hogy mivel csak 1008 másik ilyen van, ezért össze van kötve 1009 fokúval is, ami ellentmondás. Az előzőek alapján szintén igaz, hogy a gráf minden komponensében van páratlan fokú csúcs. Tehát a kiinduló gráf olyan komponensekből áll, melyek mindegyike az alábbi három kategória egyikébe esik:
1. | Izolált pont (eredetileg 0 darab). |
2. | 2 csúcsú teljes gráf (eredetileg 0 darab). |
3. | Egyéb nem teljes gráf, mely tartalmaz páratlan fokú csúcsot. |
Ha van 3. típusú komponens, akkor nyilván tudunk lépni. Belátom, hogy ekkor olyat is tudunk lépni, amellyel továbbra is csak ilyen komponensek maradnak.
1. | Tegyük fel, hogy tudunk olyat lépni, hogy azzal a gráf adott komponense továbbra is összefüggő marad. | Ekkor ez a komponens továbbra is tartalmazni fog páratlan fokú csúcsot (mivel a csúcsok fokszámainak paritása állandó), és a többi komponens változatlan marad; tehát csak annyit kell belátni, hogy ez a komponens nem alakul teljes gráffá. Ehhez vizsgáljuk meg, hogyan keletkezhet teljes gráf. Ha egy izolált teljes gráf komponens keletkezik, akkor a keletkező komponens egyik csúcsának benne kellett lennie abban a három csúcsban, amelyre a lépést végrehajottuk.
| Ha csak az egyik csúcsa volt benne a keletkező teljes gráfnak a csúcshármasban, akkor az lehetett a cseresznye egyik vége, vagy a középső csúcs. |
| Ha a cseresznye egyik vége benne volt a keletkező teljes gráfban, de a másik tehát nem (a cseresznyének csak 1 csúcsa volt benne!), akkor a keletkező komponens nem lesz izolált teljes gráf, mivel a cseresznye másik vége egy éllel hozzá lesz kötve (ellentmondásra jutunk). |
| Ha a cseresznyének a közepe van benne a keletkező teljes gráfban, akkor a cseresznyének a két vége a keletkező teljes gráf semelyik másik csúcsával sincs összekötve (hiszen izolált lesz a teljes gráf), tehát ők ezen lépés után elszakadnak. Mivel az 1. pontban vagyunk, ezért ez jelen esetben ellentmondásra vezetne (nem maradna a komponens összefüggő). |
| Ha két csúcsa is benne van a csúcshármasnak a keletkező teljes gráfban, akkor azok közt eredetileg nem lehetett él, hiszen a lépés után muszáj köztük élnek lenni. Ekkor a cseresznye közepe nyilván nem lehetett benne a teljes gráfban, és nem is lehetett összekötve annak egyéb csúcsaival, tehát a lépés után ő elszakad tőle. Mivel az 1. pontban vagyunk, ezzel a lehetőséggel szintén nem kell törődnünk. |
Tehát ilyen esetben izolált teljes gráf komponens nem keletkezhet.
2. | Tegyük fel most, hogy csak olyat tudunk lépni, hogy attól egy komponens kettészakad. |
| Tételezzük fel, hogy van olyan 2 fokú csúcs, amely egy lehetséges lépésben a cseresznye közepe. | Ekkor ezt a lépést végrehajtva ő elszakad, és 1. típusú komponens lesz, valamint a volt komponensének maradékában továbbra is lesz páratlan fokú csúcs (hiszen minden csúcs fokszámának paritása állandó). A komponensének a maradéka így vagy nem lesz teljes gráf, és ezzel 3. típusú lesz, vagy
| 2 csúcsú teljes gráf lesz, vagyis 2. típusú. |
| Tegyük fel, hogy 3 csúcsú teljes gráf lesz. | Ekkor az eredeti komponens egy 4 csúcsú kör volt, ami ellentmond az indukciós feltevésnek, mert a 3 kategória egyikébe sem esik bele. Ezzel tehát nem kell törődnünk.
| Tegyük fel, hogy legalább 4 csúcsú teljes gráf lesz. | Ekkor a csúcs, mely elszakad, eredetileg egy-egy éllel volt hozzákötve egy teljes gráfhoz, melynek egy éle (értelemszerűen) hiányzott. Ez az izolált teljes gráfok keletkezési lehetőségeinek fentebb tárgyalt módjaiból következik, és abból, hogy a cseresznye közepe 2 fokú. Ha viszont ebben az esetben egy olyan cseresznyével lépnénk, aminek a közepe az eredeti cseresznyénk egyik vége, és az egyik vége az eredeti cseresznyénk közepe (ő a teljes gráf semelyik másik csúcsával nincs összekötve, kivéve azt az egyet, amellyel az új középső nincs összekötve), akkor a komponens nem szakadna ketté (maradna a cseresznyén kívül 2 összekötött csúcs, amik együtt mindenkivel össze vannak kötve; az egyik az eredeti cseresznye másik vége, a másik pedig akármelyik másik). Mivel a 2. részben vagyunk, ez ellentmondás, és nem történhet meg. Tehát a tulajdonság az esetben valóban megmarad.
| Most azt tegyük fel, hogy minden cseresznye, amivel lehet lépni legalább 3 fokú középső csúccsal rendelkezik. | Legyen egy tetszőleges ilyen cseresznye középső csúcsa , két vége pedig és , továbbá az -nak egy -től és -től különböző szomszédja. Mivel a cseresznyével lépve (ahol a középső csúcs) a komponens kettészakad, ezért és , illetve és közt nem futhat él (hiszen -nak és -nek, illetve -nak és -nek különböző komponensbe kell kerülnie), és minden köztük futó út átmegy -n. Tehát a és cseresznyékkel is léphetünk. Ha ezek közül az egyikkel lépünk, akkor és különböző komponensekbe kerülnek, így bármely másik szomszédja és közt csak -n keresztül vezethet út. Ugyanebből a lépésből ismert, hogy és közt is csak -n keresztül mehet út. Ebből általánosságban tudjuk, hogy (aki tetszőleges cseresznye-közép volt!) bármely két csúcsa közt csak -n keresztül vezethet út. Vagyis -t elhagyva a gráfból minden szomszédja külön komponensbe kerül. Tekintsünk egy tetszőleges ilyen komponenst. Ismert, hogy egy gráfban a fokszámok összege mindig páros, vagyis páros sok páratlan fokú csúcs van benne. A kiválasztott komponensünkbe viszont megy még kívülről egy él (-ból), ami egy csúcs fokának a paritását megváltoztatja, vagyis páratlan sok páratlan fokú csúcsnak kell lennie egy ilyen leendő komponensben, tehát lennie kell páratlan fokú csúcsnak. Mivel a kettészakadás után mindkét komponensben benne lesz egy-egy teljes ilyen komponens (legalább 3 ág van!), ezért mindkettőben lesz páratlan fokú csúcs. Így mindkét komponensre igaz, hogy vagy 2. típusú, vagy csak annyit kell róla belátni, hogy nem izolált teljes gráf. Tegyük fel indirekt módon, hogy mégis teljes gráf keletkezik.
| Ha az módon keletkezik a teljes gráf, akkor ezen cseresznye helyett azzal lépve, amelynek a közepe az eredeti közepe, egyik vége az eredeti egyik vége, és a másik vége a keletkező teljes gráf egyik csúcsa, a komponens nem szakadna ketté; tehát nem a 2. részben lennénk. |
| Ha az módon keletkezik a teljes gráf, akkor az eredeti cseresznye helyett azzal lépve, amelynek a közepe az eredeti egyik vége, egyik vége az eredeti közepe, a másik vége pedig a keletkező teljes gráfban van, a komponens nem szakadna ketté, és ekkor sem a 2. részben vagyunk. |
Tehát egyik keletkező komponens nem lehet teljes gráf, vagyis 2. vagy 3. típusú. Beláttuk tehát, hogy ha tudunk lépni, akkor tudunk úgy lépni, hogy minden komponens beleessen a fent felsorolt 3 kategória egyikébe, viszont csak akkor nem tudunk lépni, ha csak 1. és 2. típusú komponensek maradtak. Mivel minden lépésben az élek száma eggyel csökken, és kezdetben csak véges sok él volt, ezért csak véges sokat tudunk így lépni, vagyis előbb-utóbb a fent leírt állapotba jutunk, ami a feladat által leírt állapot. Tehát a feladat által meghatározott állapotba biztosan el tudunk jutni. A második nap feladatainak megoldását a novemberi számban közöljük. |