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. 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. |