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. Legyen páratlan prímszám, és tekintsük a síkon azokat a pontokat, amelyeknek mindkét koordinátája a , , , , számok valamelyike. Mutassuk meg, hogy ezen rácspontok közül kiválasztható darab, amelyek közül semelyik három nem esik egy egyenesre.
Megoldás. Bebizonyítjuk, hogy azok az pontok, amelyeknél az (legkisebb nemnegatív) maradéka -vel történő osztásnál (), kielégítik a követelményt. Az értelmezés szerint alkalmas egésszel. Tegyük fel, hogy az és az szakaszok meredeksége egyenlő volna: | | A törteket eltávolítva, az értelmezést felhasználva és átrendezve: | | továbbrendezve és alakítva | | A bal oldali szorzatnak kellene tehát oszthatónak lennie -vel. Ez azonban nem lehetséges, mert egy szorzat csak úgy lehet osztható egy prímszámmal, ha valamelyik tényezője osztható vele, itt pedig mindegyik tényező 0-tól különböző és abszolút értékük -nél kisebb. Nem lehet tehát a két meredekség egyenlő.
Megjegyzések. 1. Az helyett bármilyen egész együtthatós vagy egész helyeken egész értéket felvevő, másodfokú polinom megfelel. Érdekes, hogy a feladattal foglalkozó versenyzők többnyire az polinomot választották. 2. Többen használtak olyan pontatlan állításokat, mint különbség maradéka egyenlő a maradékok különbségével, vagy szorzat maradéka egyenlő a tényezők maradékainak szorzatával, amelyek csak kiegészítésekkel érvényesek. 3. Egy versenyző azokat az pontokat adta meg, amelyekre (mod ) (), maga is megjegyezve, hogy így csak pontot kap. 4. A kérdésnek kiterjedt irodalma van. A feladat állítása igaznak látszik prímszám helyett minden pozitív egész számra, sőt próbálgatások során -ig és számos nagyobb páros -re pontot is sikerült találni úgy, hogy ne legyen közülük 3 egy egyenesen. Sikerült bebizonyítani, hogy tetszés szerinti pozitív értékhez pont is kiválasztható, ha elég nagy. A problémával kapcsolatban R. K. Guy és P. A. Kelly több érdekes sejtést fogalmazott meg. Így többek közt azt sejtik, hogy csak az 1. ábrán látható 3 esetben helyezhető el pont egy oldalhosszú négyzetben úgy, hogy rendelkezzék a négyzet összes szimmetriájával; azt sejtik továbbá, hogy nagy -re legfeljebb pont helyezhető el a követelménynek megfelelően, ahol . R. K. Guy: Unsolved problems in number theory, 2. kiad. Springer, 1996. XVI + 285 old., közelebbről 242‐244. old.
1. ábra
2. Az háromszög körülírt körének középpontja . A beírt kör az oldalakat az , , pontokban érinti, középpontja . Az háromszög magasságpontja . Igazoljuk, hogy az , , pontok egy egyenesen vannak.
I. megoldás. Tekintsük az , és pontok merőleges vetületeit az háromszög oldalaira. Elegendő azt megmutatni, hogy az ezek közti szakaszok aránya két különböző oldalon megegyező. Határozzuk meg ezt az arányt pl. a oldalon. -fel jelölve az háromszög köré írt kör -t nem tartalmazó ívének felezőpontját, ezen átmegy az -ból a oldalra emelt merőleges is és az -ból induló szögfelező is. Jelöljük a köztük levő szöget -val (2. ábra). Az érintési sugár szintén merőleges a oldalra.
2. ábra , és merőleges vetületét a oldalon jelöljük , és -vel. Az háromszög egyenlő szárú, ezért -en van, tehát párhuzamos -fel, és így . Az -ból -re és -ből -re emelt merőleges szakaszok az , illetőleg szakasszal egyenlők, tehát hosszuk , illetőleg , ahol a háromszög köré írt kör sugara, a beírt köré. Így | | Ez az arány azonban csak a két kör adataitól függ, a oldaltól nem, így ugyanez az arány adódik a másik két oldalon levő vetületek közti szakaszokra is. Ezzel a feladat állítása bizonyítást nyert.
II. megoldás. A megoldáshoz felhasználunk a háromszögekre vonatkozó néhány összefüggést, amelyeket a megoldás végén bizonyítunk. Jelöljük az háromszög csúcsaiból húzott magasságok talppontját rendre , , -vel (3. ábra).
3. ábra a) Egy háromszög magasságai felezik a talpponti háromszög szögeit, így a magasságpont a talpponti háromszögbe írt kör középpontja, esetünkben az -be írté. b) Ismeretes, hogy a háromszög (esetünkben az háromszög) köré írt körnek a csúcsokhoz mutató sugarai merőlegesek a talpponti háromszög oldalaira. Esetünkben , , érintési sugár is, tehát merőleges rendre a , , oldalra is, tehát az és az háromszög oldalai párhuzamosak. c) A két háromszög hasonló helyzetű is, s így rájuk vonatkozóan megfelelő pontpárok összekötő egyenesei is párhuzamosak. d) Az háromszög köré írt kör az háromszög ún. Feuerbach-köre, ez átmegy az oldalak felezőpontjain is, és középpontja az szakasz felezőpontja. Az háromszögre vonatkozóan és megfelelői az -re vonatkozóan és , így összekötő egyeneseik párhuzamosak. A két egyenesnek azonban közös pontja, így , és egy egyenesen van, és ezt kellett bizonyítani.
Bebizonyítjuk a felhasznált összefüggéseket.
4. ábra a) Jelöljük az háromszög egymás utáni csúcsaiból húzott magasságainak talppontját , , -vel (4. ábra). Az és az négyszög húrnégyszög, így és , tehát szögfelező.
5. ábra b) Az háromszög köré írt középpontú körben az mint középponti szög az kétszerese (5. ábra). Szögfelezője merőleges -re, és nagyságú szöget zár be vele. A pontból húzott magasság talppontjából állítsunk merőlegest -ra, messe ez a oldal egyenesét a pontban. Ekkor mint merőleges szárú szög ugyancsak nagyságú, tehát húrnégyszög, benne a oldal -ből derékszögben látszik, tehát -ból is, vagyis a -ből húzott magasság talppontja, . c) Azt kell belátnunk, hogy ha az és az háromszög megfelelő oldalai párhuzamosak, akkor , és egy ponton megy keresztül, vagy párhuzamosak (6. ábra).
6. ábra Ha pl. és metszi egymást egy pontban, akkor és hasonló háromszögek, így . Másrészt . Ekkor azonban a és a háromszög is hasonló, mert egy szögük és az azt közrefogó oldalak aránya egyenlő. Ebből viszont következik, hogy , és is egy egyenesen van. d) A Feuerbach-körre vonatkozó állítások igazolására jelöljük a , , oldalak felezőpontjait rendre , , -vel (7. ábra(.
7. ábra Az csúcs tükörképe az középvonalra a magasságtalppont. mint középvonal -val egyenlő és párhuzamos, a tükrözés folytán pedig -val egyenlő. Így szimmetrikus trapéz (lehet hurkolt, esetleg egyenlő szárú háromszög). Így kör írható köré, amelynek középpontja az szakasz felezőmerőlegesén van, az pedig felezi az és az magasságpont közti szakaszt. A kör átmegy mind a három oldal felezőpontján, így a gondolatot a másik két oldalra megismételve, ugyanaz a kör adódik, sőt, azt is kapjuk, hogy a kör középpontja az szakasz felezőpontja. Az oldafelezőpontok és a magasságtalppontok közül bármelyik 3 különböző már meghatározza a kört.
3. Bizonyítsuk be, hogy tetszőleges síkba rajzolható gráf élei kiszínezhetők három színnel úgy, hogy a gráfban ne legyen egyszínű kör.
Megoldás. A feladat állítását hurokél és többszörös él nélküli gráfokra, ún. egyszerű gráfokra bizonyítjuk. (Hurokél minden színezésnél egyszínű körhöz vezetne, és egy négy éllel összekötött pontpár esetén már szintén keletkeznék kör.) Szükségünk lesz a síkra rajzolható gráfok két ismert tulajdonságára (ezek bizonyításával kapcsolatban lásd megjegyzéseinket):
* | 1) Síkra rajzolható gráfban nem lehet teljes ötszög, azaz öt olyan pont, amelyek közül bármely kettőt él köt össze. |
* | 2) Tetszőleges síkra rajzolható gráf tartalmaz legfeljebb 5-ödfokú pontot, azaz olyan pontot, amelyből legfeljebb 5 él indul ki. | Az állítást a pontok száma szerinti indukcióval bizonyítjuk. 1, 2 és 3 pontú gráfokra az állítás triviális. Tegyük fel, hogy az állítás igaz csúcsú gráfokra, és tekintsünk egy tetszőleges csúcsú síkra rajzolható gráfot. Ennek létezik legfeljebb 5-ödfokú pontja, legyen egy ilyen pont. A pont foka szerint három esetet különböztetünk meg.
I. eset: legfeljebb 3-adfokú. Hagyjuk el -t a belőle induló élekkel együtt. A megmaradó gráf továbbra is síkra rajzolható, és az indukciós feltétel szerint jól színezhető, azaz nem lesz benne egyszínű kör. Ezután egy jó színezéséhez a -ből induló éleket színezzük különbözőre. Egyszínű kör -ben nincs, és a -n átmenő körök is tartalmaznak két -ből induló, különböző színű élt, a kapott színezés tehát jó. II. eset: 4-edfokú. Legyenek a -vel összekötött pontok , , és . Ezek között van kettő ‐ mondjuk és ‐, amelyek között nincs él, mert -vel együtt nem alkothatnak teljes ötszöget. Hagyjuk el a pontot a belőle kiinduló élekkel együtt, és húzzuk be az élt (Ez lehetséges, pl. az eredeti , élekhez elég közel, (ld. 8. ábra).
8. ábra A keletkező gráfot színezzük jól. Tegyük fel, hogy az él az -es színt kapta. Ezután színezzük -ben az , éleket az -es színnel, -t és -t pedig a -es és a -as színnel. A jó színezése miatt egyszínű kör csak -n keresztül haladhatna, és csak a -ből kiinduló két egyszínű élen, -n és -n keresztül. Akkor azonban is tartalmazna -es színű kört az élen keresztül. III. eset: ötödfokú. Legyenek a -ből kiinduló élek a körüljárás sorrendjében , , , és . Ha az , , , és élek valamelyike nem szerepelne -ben, akkor húzzuk be. (Ez lehetséges, mert például ha nem szerepel, akkor az és pontokat összeköthetjük az és élekhez elég közel.) Ha ezt a bővített gráfot jól színezzük, az az eredeti gráfnak is egy jó színezését adja. A továbbiakban feltehetjük tehát, hogy az , , , és élek szerepelnek a gráfban. Ezután megmutatjuk, hogy a és a belőle induló élek elhagyása után az ötszögnek meghúzható két, egy csúcsból induló átlója. Ha egyik átló sem szerepel -ben, akkor behúzhatjuk -t és -t az és , illetve és élekhez elég közel. Az új élek csak a és élt metszik, így a keletkező gráf síkra rajzolható. Ha például a él szerepel -ben, akkor a háromszög elválasztja -t -től és -től, így -ben nem szerepelhet sem az , sem az él. Húzzuk meg ezeket az előbbi módon, majd hagyjuk el -t a belőle induló élekkel együtt, így most is síkra rajzolható gráfot kapunk. Az indukciós feltevés szerint jól színezhető (9. ábra).
9. ábra Színezzük jól a gráfot. Ha a színezésben és ugyanolyan, mondjuk -es színű, akkor -nek a -ben is szereplő élei színét megtartva színezzük az , és éleket -es színnel, a és éleket -es, illetve -as színnel (10. ábra).
10. ábra Ha az így kapott gráfban van egyszínű kör, akkor az ismét csak -es színű lehet, -n keresztül halad az és , az és vagy pedig a és éleken keresztül. Ezekben az esetekben viszont is tartalmaz egyszínű kört az , az , illetve a és éleken keresztül. A továbbiakban ezért feltesszük, hogy és színe különböző: -es, illetve -es. Hagyjuk el az és átlókat, és vizsgáljuk meg, hogy az ötszög csúcspárjai milyen színű utakkal köthetők össze. Ha létezik két olyan csúcspár: , és , , amelyek közül és nem köthető össze -es, és pár pedig nem köthető össze -es színnel, akkor színezzük ki -et és -t -es színnel, -t és -t -es színnel, a -ből kiinduló ötödik élt pedig -as színnel (11. ábra).
11. ábra Ezzel a gráf egy jó színezését kapjuk. Mivel az él -es színű volt, és nem köthető össze -es színnel; hasonlóképpen és nem köthető össze -es színnel. Ha a , , csúcsok közül valamelyik kettő nem köthető össze -es színnel, akkor azt a kettőt , -nek, , -t pedig , -nak választva, az előbbiek szerint -nek egy jó színezését nyerjük. Ha viszont , és összeköthető -es színnel, akkor nem köthető össze -vel és -vel -es színű úton, mert akkor és is összeköthető lenne -es színnel. Hasonlóképpen feltehetjük, hogy a , és csúcsok összeköthetők -es színnel, míg az csúcs nem köthető össze a és csúcsokkal -es színű úton sem (12. ábra).
12. ábra Az csúcs tehát nem köthető össze a , és csúcsokkal sem -es, sem -es színű úton. Ebből következik, hogy az és élek színe -as, és az , , csúcsok között csak ezek az élek alkotnak -as színű utat. Színezzük át -t -esre, -t pedig -esre. Ezzel a változtatással nem keletkezhet egyszínű kör. Ezután színezzük ki a , és éleket -asra, a és eleket pedig -esre, illetve -esre (13. ábra).
13. ábra Ha lenne egyszínű kör, akkor az csak -n keresztül haladhatna, és csak -as színű lehetne, és azt jelentené, hogy az , és csúcsok közül valamelyik kettő között még egy -as színű út halad, ami ellentmondás. Ezzel minden csúcsú gráfra igazoltuk az állítást.
Megjegyzések. 1. Az, hogy a teljes ötszög nem síkra rajzolható, például a következőképpen mutatható meg: Kössük össze a pontokat valamilyen sorrendben egymást nem metsző élekkel. A keletkező ötszög belsejében is, rajta kívül is csak két-két pontpárt köthet össze él, ezek a megmaradó csúcspárt elválasztják egymástól (14. ábra).
14. ábra 2. Síkra rajzolható gráfok a síkot lapokra bontják, ezekhez hozzávéve a gráfon kívüli tartomát is. Ha a gráf összefüggő, akkor a lapok , az élek és a csúcsok száma között fennáll az Euler-féle összefüggés. Ha a csúcsok száma legalább , akkor egy lapnak legalább oldala van, másrészt minden él két lapnak oldala, így . Ezt az Euler-tételbe helyettesítve az egyenlőtlenség adódik. Ha minden csúcs legalább -odfokú lenne, akkor ‐ mivel minden él két csúcshoz tartozik ‐, teljesülne. 3. Könnyen igazolható, hogy ha egy csúcsú gráf nem tartalmaz kört, akkor legfeljebb éle van. Ha azt vizsgáljuk, hogy egy tetszőleges gráf élei mikor színezhetők ki színnel úgy, hogy ne legyen benne egyszínű kör, akkor szükséges, hogy tetszőleges pozitív egészre bármely csúcsa között legfeljebb él haladjon. Ez a feltétel gyengébb, mint a síkra rajzolhatóság, és be lehet bizonyítani, hogy nemcsak szükséges, hanem elégséges is.
Surányi János, Kós Géza, Ujváry-Menyhárt Zoltán
|
|