Feladat: 2001. évi Kürschák matematikaverseny 1. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Lippner Gábor 
Füzet: 2002/február, 67 - 69. oldal  PDF  |  MathML 
Témakör(ök): Síkbeli ponthalmazok távolsága, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 2002/február: 2001. évi Kürschák matematikaverseny 1. feladata

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 n=1, akkor az állítás nyilvánvaló, n>1 esetén pedig ekvivalens azzal, hogy található 2n pont, melyek konvex burkának legalább 4 csúcsa van. Ha találunk m≥2n pontot, melyek konvex burkának legalább 4 csúcsa van, azok közül már könnyűszerrel elhagyhatunk m-2n pontot úgy, hogy a megmaradók konvex burkának még mindig legalább 4 csúcsa legyen.
Ha a pontok P halmazának konvex burka nem háromszög, akkor a fenti megjegyzés értelmében készen is vagyunk. Feltehető tehát, hogy P konvex burka egy A1B1C1 háromszög. Tegyük fel, hogy valamely i<n esetén az A1,...,Ai pontokat már definiáltuk úgy, hogy minden j≤i esetén a P∖{A1,...,Aj-1} ponthalmaz konvex burka éppen az AjB1C1 háromszög. A P∖{A1,...,Ai} halmaznak legalább 2n 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 B1 és C1, a harmadikat jelöljük Ai+1-gyel.
Megállapíthatjuk tehát, hogy ha nem található a pontok között 2n olyan, melyek konvex burka nem háromszög, akkor létezik egy A1,A2,...,An pontsorozat P-ben úgy, hogy minden i≤n esetén P∖{A1,...,Ai-1} konvex burka az AiB1C1 háromszög. Hasonlóan készíthetjük el a B1,B2,...,Bn és C1,C2,...,Cn pontsorozatokat is. Az így kapott 3n pont között kell legyen kettő olyan, amelyik egybeesik. Az általánosság megszorítása nélkül feltehetjük, hogy Aj=Bk. Ekkor a

P∖{A1,A2,...,An}∖{B1,B2,...,Bn}∖{C1}
ponthalmaznak legalább n-1≥1 pontja van, és mindegyik belső pontja mind az AjB1C1, mind a BkA1C1 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 3n-1 helyébe 3n-2 már nem írható. Valóban, legyen A1B1C1 egy szabályos háromszög, melynek középpontja O, és legyen A, B, C rendre az OA1, OB1 és OC1 szakaszok felezőpontja. Legyen kA, kB és kC egy-egy R sugarú körív, mely az A1 és A, B1 és B, illetve C1 és C pontokat köti össze. Vegyük fel a kA, kB, kC íveken az A2,...,An, B2,...,Bn-1 és C2,...,Cn-1 pontokat. Ha n≥2 és R elég nagy, akkor a P={A1,...,An,B1,...,Bn-1,C1,...,Cn-1} 3n-2 elemű ponthalmazból nem választható ki 2n pont, melyek konvex burka nem háromszög. Ha ugyanis R elég nagy, akkor minden AiAj egyenes elválasztja egymástól a Bk és Cℓ pontokat. Ha tehát P egy részhalmaza konvex burkának csúcsa az Ai és Aj pont is, akkor az A1,...,An pontokon kívül legfeljebb n-1 további pontot tartalmazhat, tehát legfeljebb 2n-1 pontja lehet. Hasonlóképpen okoskodhatunk akkor is, ha a konvex burok a Bi vagy a Ci pontok közül tartalmaz legalább kettőt csúcsként. Következésképpen P minden 2n elemű részhalmazának konvex burka mind az Ai, mind a Bi és úgyszintén a Ci pontok közül is csak egyet tartalmazhat csúcsként, és így szükségképpen háromszög lesz.
 
2. Jelölje ⌈x⌉ az x valós szám fölső egész részét, vagyis az x-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 n≠3, és adott a síkon ⌈3n/2⌉-1 pont, melyek közül semelyik három nem esik egy egyenesre. Ekkor található közöttük n 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 n pozitív egész szám, és hogy n≤2 esetén az állítás nyilván igaz. Ennek megfelelően a megoldások során feltesszük, hogy n>3 egész számot jelöl. Páratlan n esetén a fenti konstrukció apró módosításával ellenőrizhetjük azt is, hogy ha a pontok száma ⌈3n/2⌉-2, akkor az állítás már nem marad igaz.
 
II. Megoldás. Tegyük fel, hogy a P legalább ⌈3n/2⌉-1 elemű általános helyzetű ponthalmaz nem tartalmaz n pontot, melyek konvex burka nem háromszög. Legyen P konvex burka az ABC háromszög, és legyen A1=A. Az első megoldásban ismertetett módon készítsük el az A1,A2,...,A⌈n/2⌉ sorozatot úgy, hogy minden i≤⌈n/2⌉ esetén P∖{A1,...,Ai-1} konvex burka az AiBC háromszög legyen.

Rendezzük sorba az A2,...,A⌈n/2⌉ pontokat az A-ból nézve pozitív irányban, és jelölje közülük a két szélsőt X és Y. Az AX és AY egyenesek BC szakasszal alkotott metszéspontját jelölje X' és Y'. Az általánosság megszorítása nélkül feltehetjük, hogy a B, X', Y', C pontok ebben a sorrendben követik egymást a BC egyenesen. A BCX és BCY háromszögek közül valamelyik tartalmazza a másikat. Ezek közül a kisebbik, melyet lefed a BYY' és CXX' háromszögek egyesítése, tartalmazza a P'=P∖{A1,A2,...,A⌈n/2⌉,B,C} legalább n-3 elemű ponthalmazt. Az általánosság megszorítása nélkül feltehetjük, hogy P' pontjainak legalább a fele a BYY' háromszögbe esik (ábra). Válasszunk ki ezek közül ⌈(n-3)/2⌉ pontot, ezek halmazát jelölje P''. Tekintsük végül a Q=P''∪{A1,A2,...,A⌈n/2⌉,B} halmazt. Q-nak ⌈(n-3)/2⌉+⌈n/2⌉+1=n eleme van, és minden eleme az AY'B háromszögbe, vagy annak határára esik. Ezért az A, Y, B pontok a Q halmaz konvex burkán helyezkednek el. A konvex buroknak tartalmaznia kell továbbá a P'' 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 ABC 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 AB, a BC vagy a CA oldalt. Jelölje rendre P, K és Z azon pontok halmazát, melyekből indul ki piros, kék, illetve zöld színű szakasz. Az n≥4 feltevés miatt az ABC háromszög belsejében legalább 2 pont helyezkedik el, és ezért a P∪K∪Z halmaz megegyezik a háromszög belsejében lévő pontok halmazával, tehát ⌈3n/2⌉-4 eleme van. Megmutatjuk, hogy a P, K, Z halmazok valamelyikének az elemszáma legalább n-2. 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 a≠0, 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
|P|=⌈3n/2⌉-4≥n-2,
hiszen n≥4. Feltehetjük tehát, hogy a=b=c=0. Ez azt jelenti, hogy |P∪K∪Y|=x+y+y+v. Ha most |P|=y+z+v, |K|=z+x+v és |Z|=x+y+v mindegyike kisebb lenne, mint n-2, akkor összegzés után a
3n-8≤2(⌈3n/2⌉-4)=2(x+y+z+v)≤|P|+|K|+|Z|≤3(n-3)=3n-9
egyenlőtlenséghez jutnánk, ami lehetetlen.
Valóban igaz tehát, hogy valamelyik halmaz elemszáma legalább n-2. Az általánosság megszorítása nélkül feltehetjük, hogy |P|≥n-2≥2. Tekintsük a P'=P∪{A,B} legalább n elemű halmazt, ennek konvex burka tartalmazza az A és B csúcsokat. Legyen D∈P, és tekintsük P-nek egy olyan E pontját, melyre a DE szakasz piros. Mivel a DE egyenes nem metszi az AB szakaszt, az E pont nem lehet az ABD háromszög belsejében. Ezért P' konvex burka nem lehet háromszög. Már csak annyit kell megjegyeznünk, hogy ekkor P'-ből kiválasztható egy n≥4 elemű részhalmaz, melynek konvex burka szintén nem háromszög.