15. FEJEZET: Kombinatorikus geometria

Feladat: 15.1.
Adott a síkon két véges ponthalmaz, S és T. Megadhatók-e olyan párhuzamos egyenesek, amelyek S minden pontját lefedik, de T egyetlen pontját sem fedik le?
 

Feladat: 15.2.
Kutató munka: Milyen véges síkbeli ponthalmazokra igaz, hogy feloszthatók két részre úgy, hogy a két rész pontjait nem lehet egyenessel szétválasztani? (Vö. [33]. 8. feladat.) Egy egyenesről akkor mondjuk, hogy elválasztja a két részt, ha az egyik rész pontjai az egyenes egyik oldalán vannak, a másik rész pontjai az egyenes másik oldalán vannak.
 

Feladat: 15.3.
[176] Négy félsík úgy helyezkedik el egy síkban, hogy együttesen az egész síkot lefedik, azaz a síknak mindegyik pontja legalább az egyik félsíknak belső pontja. Bizonyítandó, hogy a négy félsík közül kiválasztható három úgy, hogy e három félsík is lefedi együttesen az egész síkot. (Kürschák-verseny, 1951.)
 

Feladat: 15.4.
Adott véges sok fehérre és véges sok feketére színezett pont a síkon. Mindkét színűből legalább három van. A pontok közül semelyik három nincs egy egyenesen. Tudjuk továbbá, hogy bármely négy pont közül a fehérek és a feketék egy egyenessel szétválaszthatók. Bizonyítandó, hogy az összes fekete pont elválasztható egy egyenessel az összes fehér ponttól. (Ki miben tudós? 1984) Egy egyenesről akkor mondjuk, hogy elválaszt két ponthalmazt, ha az egyik ponthalmaz az egyenes egyik oldalán van, a másik ponthalmaz az egyenes másik oldalán van.
 

Feladat: 15.5.
* Adott a síkon n darab általános helyzetű pont. Bizonyítsuk be, hogy összeköthetők egy önmagát nem metsző zárt törött vonallal! (Arany Dániel-verseny 2001H)
 

Feladat: 15.6.
a) Mutassuk meg, hogy minden n>2 egész számra megadható n elemű ponthalmaz a síkon, amelynek pontosan n átmérője van. b) * Bizonyítsuk be, hogy egy n pontból álló síkbeli ponthalmaznak legfeljebb n darab átmérője lehet. (IMO 1965/6, [183])
 

Feladat: 15.7.
[187]. Book 2. Kutató munka: Kiszínezhetők-e a sík rácspontjai három színnel úgy, hogy a) minden színhez végtelen sok olyan, az x-tengellyel párhuzamos egyenes legyen, amelyen e szín végtelen sokszor fordul elő, b) ha három pont egy egyenesen van, akkor legyen köztük két azonos színű?
 

Feladat: 15.8.
Kutató munka: Adott véges sok általános helyzetű egyenes a síkon. Az általuk meghatározott tartományokat akarjuk két színnel kiszínezni úgy, hogy azonos színű tartományoknak ne legyen közös határvonala (vagyis közös egyenes szakasza, csúcsban érintkezhetnek). Van-e olyan helyzete az egyeneseknek, amikor ez nem lehetséges?
 

Feladat: 15.9.
Kutató munka: Adott n pont a síkon, semelyik kettő távolsága nem egyenlő. Mindegyiket összekötjük a hozzá legközelebbivel. Minimálisan hány szakaszt kell így behúznunk? És maximálisan? Mit mondhatunk az így kapott alakzatról, ha olyan gráfnak tekintjük, amelynek az adott pontok a csúcsai és a behúzott összekötő szakaszok az élei?
 

Feladat: 15.10.
Kutató munka: Mi a helyzet, ha 15.9. feladatban minden pontot a tőle legtávolabbival kötünk össze?
 

Feladat: 15.11.
[33]. 9. feladat, kissé módosítva. Kutató munka: Adott n általános helyzetű pont a síkon. (Tehát semelyik három nem esik egy egyenesbe.) Melyik állítások ekvivalensek? a) A pontok konvex burka n-szög. b) A pontok konvex n-szöget alkotnak. c) A pontok megszámozhatók úgy, hogy a megadott sorrendben egy konvex n-szög csúcsai. d) Semelyik három pont által alkotott háromszög nem tartalmaz további pontot a belsejében.
 

Feladat: 15.12.
Kutató munka: Igaz-e a következő: a) Ha adott öt általános helyzetű pont a síkon úgy, hogy közülük bármely négy konvex négyszöget alkot, akkor az öt pont is konvex ötszöget alkot? b) Ha adott n általános helyzetű pont a síkon úgy, hogy közülük bármely négy konvex négyszöget alkot, akkor az n pont is konvex n-szöget alkot? ([33]. 10. feladat.)
 

Feladat: 15.13.
[33]. 11. feladat. Adott a síkon öt pont, közülük semelyik három nem esik egy egyenesbe. Bizonyítsuk be, hogy közülük valamelyik négy konvex négyszöget alkot.
 

Feladat: 15.14.
Kutató munka: Adott a síkon n pont ( n>4), közülük semelyik három nem esik egy egyenesbe. A 15.13. állítása segítségével próbáljunk alsó becslést adni arra, hogy hány olyan négyes van e pontok között, amelyek konvex négyszöget határoznak meg.
 

Feladat: 15.15.
[183] Adott a síkon n pont ( n>4), közülük semelyik három nem esik egy egyenesbe. Bizonyítsuk be, hogy legalább ( n-3 2 ) olyan konvex négyszög van, amelyeknek csúcspontjai az adott pontok közül valók! (IMO 1969.)
 

Feladat: 15.16.
Kutató munka: Milyen k-ra igaz a következő állítás: Ha adott a síkon véges sok téglalap úgy, hogy mindegyik oldalai párhuzamosak a koordinátatengelyekkel és bármelyik k téglalapnak van közös pontja, akkor van olyan pont a síkon, amelyet mindegyik téglalap tartalmaz.
 

Feladat: 15.17.
Kutató munka: Milyen k-ra igaz a következő állítás: Ha adott véges sok téglatest úgy, hogy mindegyik oldalai párhuzamosak a koordinátatengelyekkel és bármelyik k téglatestnek van közös pontja, akkor van olyan pont, amelyet mindegyik téglatest tartalmaz.
 

Feladat: 15.18.
Adott a síkon négy konvex alakzat, amelyek közül bármely háromnak van közös pontja. Bizonyítsuk be, hogy akkor mind a négynek is van közös pontja.
 

Feladat: 15.19.
Bizonyítsuk be a Kétdimenziós Helly-tételt: Adott véges sok síkbeli konvex alakzat, közülük bármely háromnak van közös pontja. Ekkor az összesnek is van közös pontja.
 

Feladat: 15.20.
Kutató munka: Milyen a valós számra igaz a következő állítás: Ha adott a síkon véges sok pont úgy, hogy semelyik három nincs egy egyenesen és bármelyik három körül írt körének a sugara legfeljebb egységnyi, akkor az összes pont lefedhető egy a sugarú körrel.
 

Feladat: 15.21.
Kutató munka: Hogyan gyengíthető a 15.20. feladat állításának feltétele?
 

Feladat: 15.22.
Kutató munka: Milyen t számokra igaz a következő állítás: Ha adott a síkon véges sok pont úgy, hogy bármely kettő távolsága legfeljebb egységnyi, akkor az összes pont lefedhető egy legfeljebb t sugarú körrel. (Jung tétele, l. [189].)
 

Feladat: 15.23.
Egy köralakú biliárdasztalon 2400 darab 1 cm sugarú golyó helyezkedik el. Bizonyítsuk be, hogy legalább még egy ugyanekkora golyó lerakható az asztalra a többi elmozdítása nélkül, ha az asztal sugara legalább 1 méter.
 

Feladat: 15.24.
Elhelyezhető-e egy egységkörben három 1/2 oldalú négyzet úgy, hogy közülük semelyik kettőnek ne legyen közös belső pontja?
 

Megoldás: 15.5
Vegyük a fehér pontok konvex burkát és a fekete pontok konvex burkát. Bebizonyítjuk, hogy például a fehérek konvex burka nem tartalmazhat fekete pontot a belsejében. Ha ugyanis volna ennek belsejében egy fekete pont, akkor bontsuk a konvex burkot egy csúcsából induló átlókkal háromszögekre. (Itt használjuk, hogy legalább három fehér pont van.) A fekete pont valamelyik háromszög belsejében volna, tehát nem volna elválasztható a három fehér ponttól. Ugyanígy kapjuk, hogy a fekete pontok konvex burka sem tartalmazhat fehér pontot a belsejében.

Ebből azonban még nem következik, hogy a két konvex burok nem metszheti egymást! (Mutassunk erre példát!) Ám ha a két sokszögvonal metszené egymást, akkor volna egy-egy oldal, amelynek mindkét vége fehér, illetve mindkét vége fekete volna. E négy pont viszont nem volna elválasztható egymástól egy egyenessel, hiszen a metszéspontjuknak az egyenes mindkét partján kellene lennie.

Ennyi viszont már elég annak bizonyításához, hogy a két konvex buroknak nincs közös pontja. De ekkor a 13.16. feladat szerint van olyan egyenes, amely elválasztja őket.
 
 

Megoldás: 15.7
1. megoldás. Először b)-t bizonyítjuk.

Tekintsük azt a gráfot, amelynek csúcsai a ponthalmaz pontjai és élei az átmérők. Ha ebben a gráfban minden pont foka legfeljebb kettő, akkor összesen legfeljebb n éle van, tehát a feladat állítása teljesül.

Tegyük fel, hogy egy P pont foka nagyobb kettőnél. Legyenek a P-ből induló átmérők PQ1 , PQ2 , ..., PQk , k>2. A Qi pontok rajta vannak a P közepű d sugarú kör egy 60-os ívén. Ugyanis bármely két PQi szakasz által bezárt szög legfeljebb 60 -os, különben a két végpont távolsága nagyobb volna d-nél. Ebből az már következik, hogy az összes Qi pont rajta van egy 120 -os köríven, s akkor a két szélső közötti szög sem lehet nagyobb 60 -nál. Feltehetjük, hogy úgy számoztuk a Qi pontokat, hogy a számozás sorrendjében jönnek a köríven.

Tegyük fel, hogy valamelyik Qi -ből indul ki még egy átmérő (a PQi -n kívül) egy S pontba. Ez nem lehet a PQ1 Qk háromszög belsejében, sőt, annak a körcikknek a belsejében sem, amelyet PQ1 és PQk határol. Feltehetjük, hogy S-et a PQ1 szakasz elválasztja Qk -tól. Tekintsük a PS szakasz f felező merőlegesét! f-en rajta van a Qi pont, mert P-től is, Qi -től is d távolságra van. Ezért f-nek azonos oldalán van P és Qk . [Ha nem akarunk a szemléletre hivatkozni, akkor ezt a következőképpen igazolhatjuk. SQk szakasz metszi PQ1 szakaszt, a metszéspont legyen M. MQk szakaszt metszi PQi szakasz, a metszéspont legyen L. Végül f metszi az ML szakaszt.] Tehát Qk távolabb van S-től, mint P. Ebből SQk >SP=d következik, ami ellentmondás.

Ez azt jelenti, hogy minden k>2-ed fokú ponthoz tartozik k-2 darab elsőfokú pont a gráfban, s nyilván különböző pontokhoz különböző elsőfokú pontok tartoznak. Hagyjuk el a gráfból az elsőfokú pontokat a hozzájuk tartozó éllel. Azt láttuk be, hogy így csupa legfeljebb másodfokú pont marad. Ha tehát m darab elsőfokú pont volt, akkor maradt n-m pont, s legfeljebb ugyanennyi él. Viszont összesen m élt hagytunk el, tehát valóban legfeljebb n él volt eredetileg.

A bizonyításból a)-ra a példa már leolvasható: vegyünk egy ABC egységoldalú ABC szabályos háromszöget, és az A középpontú egységsugarú kör BC ^ ívén n-3 további pontot.

Megjegyzés. Páratlan n-re jó a szabályos n-szög n csúcsa, hiszen ennek a ponthalmaznak a leghosszabb átlók az átmérői, s ezekből páratlan n esetén pontosan n van.
 
2. megoldás. Nyilvánvaló, hogy egy átmérő mindkét végpontja az n pont konvex burkán van. Ha ugyanis AB egy tetszőleges szakasz a konvex burkon belül, amely a konvex burok kerületét A' és B' pontban metszi, akkor vagy A' és B' is csúcsa a konvex buroknak, vagy ha például B' nem csúcs, akkor van olyan C csúcs a konvex burkon, amely B'-nél távolabb van A'-től.

Az is nyilvánvaló, hogy két átmérő biztosan metszi egymást. Ha ugyanis nem metszenék egymást, akkor a végpontjaik paralelogrammát alkotnának, amelynek a két átmérő volna az egyik oldalpárja. De a paralelogramma valamelyik két átellenes pontja távolabb van egymástól, mint az oldal.

Ezzel a feladatot visszavezettük a 16.17. feladatra: ott láthatjuk, hogy a konvex buroknak legfeljebb annyi átlója húzható meg úgy, hogy bármely kettő messe egymást, ahány csúcsa van.
 
 

Megoldás: 15.17
A 15.14. feladat szerint legalább ( n 4 ) 5 ilyen négyes van. Azt kell tehát belátnunk, hogy ez nem kisebb ( n-3 2 )-nél, vagvis hogy n(n-1)(n-2)≥60(n-4). Ezt teljes indukcióval bizonyíthatjuk. n=5-re egyenlőség van, utána n-ről n+1-re a bal oldal n+1 n-2 -szeresére nő, a jobb oldal n-3 n-4 -szeresére. Utóbbi n>4-re kisebb.
 
 

Megoldás: 15.21
A konvex halmazoknak azt a tulajdonságát fogjuk használni (ami definiáló tulajdonságuknak is vehető), hogy ha egy konvex alakzat tartalmazza az A és a B pontot, akkor tartalmazza az egész AB szakaszt. Ebből következik az is, hogy ha egy konvex alakzat tartalmazza az A, B és C pontot, akkor tartalmazza az egész ABC háromszöget is.

Számozzuk meg a négy halmazt, és az i,j és k-adik egy tetszőlegesen választott közös pontját jelöljük Aijk -val. Kapunk négy pontot. Ha ezek egy konvex négyszöget alkotnak, akkor vegyük a két átló metszéspontját. Nyilván számozhatjuk úgy a csúcsokat, hogy az egyik átló végpontjai az A123 és az A124 pontok. Vagyis mindkét csúcs benne van az első két halmaz metszetében. De akkor a halmazok konvexitása miatt az egész átló is benne van e két halmaz metszetében. Ugyanígy a másik átló benne van a másik két halmaz metszetében. A metszéspontjuk tehát mind a négy halmaznak közös pontja. Lásd az 1. ábrát.

1. ábra

Ha a konvex burkuk egy háromszög, akkor a négy halmaz közül valamelyik tartalmazza mind a három csúcsot. A halmaz konvexitásából következik, hogy akkor tartalmazza az egész háromszöget is, így a belső pontját is, amely viszont a három másik halmaz közös pontja. Ez a pont tehát mind a négy halmazban benne van.
 
 

Megoldás: 15.22
Négy halmazra a 15.18. feladatnál bizonyítottuk az állítást. Ezután k>4 halmazra teljes indukcióval bizonyíthatunk. Tegyük fel, hogy k-1-re már tudjuk az állítást és legyen k halmazunk, amelyek közül bármely három metszi egymást. Legyenek a halmazok az A1 , A2 ,…, Ak halmazok. Fontos megállapítás, hogy a 15.18. feladatban bizonyítottak szerint e halmazok közül bármely négynek is van közös pontja. Tekintsük a Bi = Ai ∩ Ak halmazokat. Ezek konvexek, mert konvex halmazok metszete is konvex. Azt állítjuk, hogy a Bi halmazok közül is bármely három metszetének van közös pontja. Ez ugyanis annyit jelent, hogy bármely négy Ai -nek is van közös pontja, amit viszont már tudunk. Tehát a Bi halmazoknak van közös pontjuk, s ez nyilván közös pontja az Ai halmazoknak is.