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. Adott a síkon pont, közülük semelyik három nem esik egy egyenesre. Mutassuk meg, hogy található közöttük pont, melyek konvex burka nem háromszög.
I. Megoldás. Ha , akkor az állítás nyilvánvaló, esetén pedig ekvivalens azzal, hogy található pont, melyek konvex burkának legalább 4 csúcsa van. Ha találunk pontot, melyek konvex burkának legalább 4 csúcsa van, azok közül már könnyűszerrel elhagyhatunk pontot úgy, hogy a megmaradók konvex burkának még mindig legalább 4 csúcsa legyen. Ha a pontok halmazának konvex burka nem háromszög, akkor a fenti megjegyzés értelmében készen is vagyunk. Feltehető tehát, hogy konvex burka egy háromszög. Tegyük fel, hogy valamely esetén az pontokat már definiáltuk úgy, hogy minden esetén a ponthalmaz konvex burka éppen az háromszög. A halmaznak legalább pontja van, ezért az előbbi megállapításunkhoz hasonlóan feltehetjük, hogy e halmaz konvex burka is egy háromszög. Ennek két csúcsa nyilván és , a harmadikat jelöljük -gyel. Megállapíthatjuk tehát, hogy ha nem található a pontok között olyan, melyek konvex burka nem háromszög, akkor létezik egy pontsorozat -ben úgy, hogy minden esetén konvex burka az háromszög. Hasonlóan készíthetjük el a és pontsorozatokat is. Az így kapott pont között kell legyen kettő olyan, amelyik egybeesik. Az általánosság megszorítása nélkül feltehetjük, hogy . Ekkor a | | ponthalmaznak legalább pontja van, és mindegyik belső pontja mind az , mind a háromszögnek. Ez azonban lehetetlen, hiszen a két háromszögnek nincs közös belső pontja. Ez az ellentmondás igazolja az állítást. Megjegyzések. 1. Nem nehéz megmutatni, hogy a feladatban helyébe már nem írható. Valóban, legyen egy szabályos háromszög, melynek középpontja , és legyen , , rendre az , és szakaszok felezőpontja. Legyen , és egy-egy sugarú körív, mely az és , és , illetve és pontokat köti össze. Vegyük fel a , , íveken az , és pontokat. Ha és elég nagy, akkor a elemű ponthalmazból nem választható ki pont, melyek konvex burka nem háromszög. Ha ugyanis elég nagy, akkor minden egyenes elválasztja egymástól a és pontokat. Ha tehát egy részhalmaza konvex burkának csúcsa az és pont is, akkor az pontokon kívül legfeljebb további pontot tartalmazhat, tehát legfeljebb pontja lehet. Hasonlóképpen okoskodhatunk akkor is, ha a konvex burok a vagy a pontok közül tartalmaz legalább kettőt csúcsként. Következésképpen minden elemű részhalmazának konvex burka mind az , mind a és úgyszintén a pontok közül is csak egyet tartalmazhat csúcsként, és így szükségképpen háromszög lesz.
2. Jelölje az valós szám fölső egész részét, vagyis az -nél nem kisebb egész számok közül a legkisebbet. Megmutatható, hogy az alábbi erősebb állítás is igaz. Tegyük fel, hogy , és adott a síkon pont, melyek közül semelyik három nem esik egy egyenesre. Ekkor található közöttük pont, melyek konvex burka nem háromszög. A következőkben erre az állításra adunk még két bizonyítást. Jegyezzük meg, hogy a feltételnek csak akkor van értelme, ha pozitív egész szám, és hogy esetén az állítás nyilván igaz. Ennek megfelelően a megoldások során feltesszük, hogy egész számot jelöl. Páratlan esetén a fenti konstrukció apró módosításával ellenőrizhetjük azt is, hogy ha a pontok száma , akkor az állítás már nem marad igaz.
II. Megoldás. Tegyük fel, hogy a legalább elemű általános helyzetű ponthalmaz nem tartalmaz pontot, melyek konvex burka nem háromszög. Legyen konvex burka az háromszög, és legyen . Az első megoldásban ismertetett módon készítsük el az sorozatot úgy, hogy minden esetén konvex burka az háromszög legyen.
Rendezzük sorba az pontokat az -ból nézve pozitív irányban, és jelölje közülük a két szélsőt és . Az és egyenesek szakasszal alkotott metszéspontját jelölje és . Az általánosság megszorítása nélkül feltehetjük, hogy a , , , pontok ebben a sorrendben követik egymást a egyenesen. A és háromszögek közül valamelyik tartalmazza a másikat. Ezek közül a kisebbik, melyet lefed a és háromszögek egyesítése, tartalmazza a legalább elemű ponthalmazt. Az általánosság megszorítása nélkül feltehetjük, hogy pontjainak legalább a fele a háromszögbe esik (ábra). Válasszunk ki ezek közül pontot, ezek halmazát jelölje . Tekintsük végül a halmazt. -nak eleme van, és minden eleme az háromszögbe, vagy annak határára esik. Ezért az , , pontok a halmaz konvex burkán helyezkednek el. A konvex buroknak tartalmaznia kell továbbá a halmaznak legalább egy pontját is, ami ellentmond az indirekt feltevésünknek. III. Megoldás. (Ez a megoldás Lippner Gábortól származik.) Akárcsak az első megoldásban, most is feltehetjük, hogy a pontok konvex burka egy háromszög. Két olyan pontot, mely a háromszög belsejében fekszik, kössünk össze egy piros, kék vagy zöld színű szakasszal aszerint, hogy az általuk meghatározott egyenes a háromszög három oldala közül melyiket nem metszi: az , a vagy a oldalt. Jelölje rendre , és azon pontok halmazát, melyekből indul ki piros, kék, illetve zöld színű szakasz. Az feltevés miatt az háromszög belsejében legalább 2 pont helyezkedik el, és ezért a halmaz megegyezik a háromszög belsejében lévő pontok halmazával, tehát eleme van. Megmutatjuk, hogy a , , halmazok valamelyikének az elemszáma legalább . Ennek igazolásához készítsük el a halmazok Venn-diagrammját, ahol az egyes betűk a megfelelő részhalmazok elemszámát jelölik.
Ha mondjuk , akkor van olyan pont a háromszög belsejében, amelyet minden további ponttal piros színű szakasz köt össze, ekkor tehát hiszen . Feltehetjük tehát, hogy . Ez azt jelenti, hogy . Ha most , és mindegyike kisebb lenne, mint , akkor összegzés után a | | egyenlőtlenséghez jutnánk, ami lehetetlen. Valóban igaz tehát, hogy valamelyik halmaz elemszáma legalább . Az általánosság megszorítása nélkül feltehetjük, hogy . Tekintsük a legalább elemű halmazt, ennek konvex burka tartalmazza az és csúcsokat. Legyen , és tekintsük -nek egy olyan pontját, melyre a szakasz piros. Mivel a egyenes nem metszi az szakaszt, az pont nem lehet az háromszög belsejében. Ezért konvex burka nem lehet háromszög. Már csak annyit kell megjegyeznünk, hogy ekkor -ből kiválasztható egy elemű részhalmaz, melynek konvex burka szintén nem háromszög.
2. Legyen egész szám, . Bizonyítandó, hogy ha , , () darab különböző valós szám, akkor az számok között legalább különböző szám található. Mutassuk meg, hogy esetén az állítás nem feltétlenül igaz.
I. Megoldás. Tegyük fel, hogy az állítás nem igaz, vagyis az , , számok között legfeljebb különböző szám található, ezek halmazát jelölje . Világos, hogy minden esetén az , , számok páronként különbözők, vagyis -nek egy 3-elemű részhalmazát alkotják. Továbbá, ha , és , akkor , és . Az halmaz ismeretében az halmaz tehát egyértelműen meghatározható. Minthogy léteznek indexek úgy, hogy , ami azonban lehetetlen. A második állítás bizonyításához tekintsük a halmazt, ahol . Legyen , és jelölje a halmaz 3-elemű részhalmazait. Ha , ahol egész számok, akkor legyen , és , ekkor nyilván . Ezért elegendő megmutatni, hogy az () számok mind különbözők. vagy semmilyen esetén nem állhat fenn, hiszen az számok mind negatívak, míg a , számok mind pozitívak. Az sem lehet, hogy , hiszen a számok mindegyike valamelyik alakú intervallumba esik, míg a számok mindegyike valamelyik alakú intervallumba esik, ahol egész szám. Legyen most és , ahol és egész számok. Tegyük fel, hogy , ekkor Mivel és , ez csak úgy lehet, ha , következésképpen . Itt és , ezért az egyenlőség csak úgy állhat fenn, ha , és ekkor szükségképpen , is igaz. A számok tehát mind különbözők. Ugyanilyen gondolatmenettel megállapíthatjuk azt is, hogy mind az számok, mind a számok különbözők, amivel a bizonyítás végére értünk.
II. Megoldás. A feladat első részére mutatunk egy másik indoklást, ez Kiss Demetertől származik. Tegyük fel ismét, hogy az állítással ellentétben a összeg között legfeljebb különböző szám található. Ekkor ezek közül valamelyik, jelöljük ezt -val, legalább alkalommal fordul elő. Ha valamilyen -re az , és összegek közül kettő is egyenlő lenne -val, akkor az , , számok között lenne két megegyező. Az általánosság megszorítása nélkül feltehetjük tehát, hogy minden esetén az , és összegek közül pontosan egy lesz -val egyenlő. Az ezen összegek közül fennmaradó összeg most már csak különböző értéket vehet fel, van tehát egy olyan érték, jelöljük ezt -vel, amely legalább alkalommal fordul elő. Az előző okoskodáshoz hasonlóan tehát feltehetjük, hogy minden esetén az , és összegek közül az egyik -val, egy másik pedig -vel egyenlő. A még megmaradó összeg pedig már csak legfeljebb különböző értéket vehet fel, lesz tehát köztük kettő, amelyik megegyezik. Ekkor azonban az ezekhez tartozó , , számhármasok is megegyeznek, mely ellentmondás bizonyítja az állítást.
A továbbiakban a feladat második részére mutatunk több megoldást.
III. Megoldás. Tekintsük a halmazt, ahol . Legyen és az halmaz két 3-elemű részhalmaza. Az I. megoldáshoz hasonlóan, annyit kell csak megmutatnunk, hogy ha akkor a két részhalmaz szükségképpen megegyezik, és . Valóban, ekkor . Ha az számot hármas számrendszerben írjuk fel, akkor annak 0-tól különböző számjegyei között vagy három 1-es, vagy egy 1-es és egy 2-es számjegy szerepel, hiszen nem lehetséges. A felírás egyértelműsége miatt az első esetben és az halmaznak ugyanaz a 3-elemű részhalmaza. Mivel , ebből , majd is következik, ahogyan azt bizonyítani kívántuk. A második esetben azt kapnánk, hogy és az halmaznak ugyanaz a 2-elemű részhalmaza. Mivel , ez meg kellene egyezzen az halmazzal, ahonnan következne, ami nem lehetséges.
IV. Megoldás. Ahogyan azt az eddigi megoldások is sugallják, elegendő azt megmutatni, hogy minden pozitív egész esetén létezik egy olyan halmaz, melyre akkor és csak akkor teljesül, ha az , , számok valamilyen sorrendben megegyeznek az , , számokkal. Valóban, ekkor nem nehéz megmutatni, hogy a alakban felírható szám (ahol az halmaz tetszőleges 3-elemű részhalmaza) mind különböző. Ha akkor a választás nyilván megfelelő. Elegendő megmutatni azt, hogy létezik olyan végtelen sorozat, hogy minden esetén nem írható fel alakban, ahol racionális számok. Tegyük fel ugyanis, hogy létezik ilyen sorozat, tekintsük a halmazt, és tegyük fel, hogy teljesül valamilyen esetén. Legyen az , , , , , indexek között előforduló legnagyobb szám. Ha most nem ugyanannyiszor szerepelne az egyenlőség két oldalán, akkor átrendezés után egy alakú egyenlőséghez jutnánk. Ezért ugyanannyiszor szerepel az , , számok között, mint az , , számok között. Mindkét oldalról elhagyva a -vel egyenlő tagokat, és az előbbi lépést megismételve végül azt kapjuk, hogy az , , számok valamilyen sorrendben valóban megegyeznek az , , számokkal. Tegyük fel tehát, hogy , és a számokat már meghatároztuk a fenti kívánalomnak megfelelően. Ekkor az alakban felírható számok halmaza megszámlálhatóan végtelen, míg az összes valós szám halmaza nem az, létezik tehát olyan valós szám, mely nem írható fel alakban. Ezért a kívánt tulajdonságú sorozat létezése azonnal következik a teljes indukció elvéből. Megjegyzések. 1. Az előző megoldásban nem konstruktív módon igazoltuk egy alkalmas sorozat létezését. Megmutatható, hogy például a választással, ahol az -edik pozitív prímszámot jelöli, megfelelő sorozathoz jutunk. Ennek bizonyítása azonban már túl messzire vezetne.
2. Ahogyan azt Kocsis Albert Tihamér észrevette, a feladat átalánosítható a következő módon. Legyenek egész számok, . Ha () különböző valós szám, akkor a (, ) számok között legalább különböző szám található, esetén pedig ez nem mindig van így. Ennek igazolását az olvasó könnyen elvégezheti, nincsen szükség hozzá alapvetően új gondolatra.
3. Merőben más a helyzet, ha kéttagú összegeknél maradunk. Világos, hogy ha egész szám, , és , , , () különböző valós szám, akkor az , , , , , összegek között legalább különböző szám található. Meglepő módon ez az állítás lényegesen nem javítható. Érdemes elgondolkozni a következő feladaton: minden egész számra létezik különböző valós szám, , , , úgy, hogy az , , , , , összegek között legfeljebb különböző szám található.
3. Egy négyzetrácsban tekintsünk egy adott háromszöghöz hasonló legkisebb területű rácsháromszöget. Bizonyítsuk, hogy körülírt körének középpontja nem rácspont.
I. Megoldás. (Gerencsér Balázs megoldása.) Tekintsünk egy olyan rácsháromszöget, melynek körülírt körének középpontja is rácspont. Az általánosság megszorítása nélkül feltehetjük, hogy az egyik csúcspont () az origó. Legyenek a másik két csúcs koordinátái és , a körülírt kör középpontjáé pedig . Az és szakaszok egyenlőségéből a Pitagorasz tétel alapján nyerjük, hogy , ahonnan leolvasható, hogy , és így és is páros számok. Hasonlóképpen kapjuk, hogy és is páros számok. Tekintsük most az rácsháromszöget, ahol | | Ebben a háromszögben | | és | | Az háromszög oldalai tehát rendre megegyeznek az háromszög megfelelő oldalainak -ed részével, a két háromszög ennek megfelelően hasonló. Ilyen módon találtunk egy, az háromszöghöz hasonló, annál kisebb területű rácsháromszöget. Ez bizonyítja az állítást.
II. Megoldás. Tegyük fel, hogy egy rácsháromszög körülírt körének középpontja is rácspont. Legyenek az egyik oldalvektor koordinátái , az pontból a szóban forgó oldal csúcsaiba mutató vektorok koordinátái pedig , illetve . Ekkor , , , , , egész számok, melyekre a Pitagorasz tétel alapján | | teljesül. Mivel (a körülírt kör sugarának négyzete), , és így is páros szám. Következésképpen és is páros számok. Ha az vektort az origó körül -os szöggel elforgatjuk pozitív irányba, akkor az vektort kapjuk, ezt arányban nagyítva pedig az vektorhoz jutunk, melynek mindkét koordinátája egész szám. Megállapíthatjuk tehát, hogy -t bármely csúcsa körüli -os szöggel történő arányú forgatva nyújtás egy hozzá hasonló, ám nála kisebb rácsháromszögbe viszi. Ez bizonyítja az állítást.
Megjegyzés. Bontsunk fel egy húrsokszöget valamely csúcsából induló átlóinak segítségével háromszögekre. Mivel ezen háromszögek körülírt köreinek ugyanaz a középpontja, ez a megoldás mutatja azt is, hogy a feladat állítása háromszög helyett tetszőleges húrsokszögre is igaz. |