Feladat: Gy.2196 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Bóna M. ,  Dinnyés Enikő ,  Hajdú S. ,  Makó B. ,  Pál G. ,  Szabó 544 A. ,  Szalay Gy. ,  Vasy A. 
Füzet: 1986/január, 10 - 11. oldal  PDF  |  MathML 
Témakör(ök): Ponthalmazok, Halmazelmélet, Háromszögek nevezetes tételei, Indirekt bizonyítási mód, Kombinatorikus geometria síkban, Egyenes, Mértani helyek, Egyéb sokszögek geometriája, Gyakorlat
Hivatkozás(ok):Feladatok: 1984/április: Gy.2196

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.

A feladat szövege nem egészen pontos. Ha ugyanis csak 3 pontunk van, akkor nem mindig található olyan egyenes, amelyik az összes piros pontot elválasztja az összes feketétől, bár a feltétel teljesül, ha pl. A és B piros, C fekete és C az AB szakasz belsejében van, akkor bárhogyan húzunk meg egy egyenest, ez a síkot két (konvex) félsíkra osztja, C a két félsík valamelyikében van, s ez a félsík vagy a CA vagy CB szakaszt is tartalmazza, azaz tartalmaz piros pontot is (1. ábra). Fel kell tehát tennünk, hogy a pontok száma legalább 4.

 
 
1. ábra
 

Egy síkbeli alakzat konvex burkának azt a síkidomot nevezzük, amelyik tartalmazza az alakzatot, és amelyet az adott alakzatot tartalmazó minden konvex alakzat tartalmaz. A konvex burok tehát a legszűkebb olyan konvex halmaz, amely az adott alakzatnak valamennyi pontját tartalmazza. Véges sok pont konvex burka konvex sokszög (vagy szakasz vagy pont), amelynek csúcsai az adott pontok közül valók.
Egy egyenes a síkot két, közös pont nélküli konvex félsíkra osztja, ezért ha néhány pont benne van az egyik félsíkban, akkor ezek konvex burka is ebben a félsíkban van. Ha tehát egy egyenes elválasztja a piros pontokat a feketéktől, akkor a két ponthalmaz konvex burkát is el kell választania. A bizonyítandó állítás így ekvivalens a következővel: a piros, illetve a fekete pontok konvex burka szétválasztható egy alkalmas egyenessel. Ezt fogjuk bizonyítani.
Először azt látjuk be, hogy az adott feltétel mellett (ti. hogy bármely 4 pont közül a pirosak és feketék egy egyenessel szétválaszthatók), a konvex burkoknak nem lehet közös pontjuk.
 
 
2. ábra
 

Vizsgáljuk először azt az esetet, ha a két konvex burok határának ‐ az általános esetben ez két sokszög ‐ van közös pontja. Tegyük fel, hogy egyik konvex burok sem fajult ponttá. Ilyenkor 2 piros, ill. 2 fekete pontot összekötő szakasz metszi egymást, vagy pedig egy oldalban és egy csúcsban, esetleg egyetlen közös csúcsban találkozik (2. ábra). Mivel a konvex burok konvex halmazként két pontjával együtt a pontokat összekötő szakaszt is tartalmazza, ekkor egyik esetben sem létezhet olyan egyenes, amelyik ebből a pontnégyesből a különböző színű pontokat elválasztja. A két konvex burok határának tehát nem lehet közös pontja.
Ha viszont az egyik (nem üres) pl. a fekete pontokat tartalmazó konvex burok tartalmazná a másikat (lehet, hogy ez utóbbi csak 1 pont), akkor, mivel feltettük, hogy van legalább 4 pontunk, a "fekete'' konvex burok valódi sokszög. Osszuk fel ezt a sokszöget nem metsző átlókkal háromszögekre! Valamelyik háromszög tartalmaz a belsejében vagy a határán piros pontot. A háromszög csúcsai feketék, és így erre a 4 pontra nem teljesül a feltétel. A két konvex buroknak tehát valóban nem lehet közös pontja.
Ezek után rátérünk annak bizonyítására, hogy van olyan egyenes, amely a konvex burkokat elválasztja. Tudjuk, hogy két közös pont nélküli konvex sokszög pontjai között létezik minimális távolság (esetleg több). Azt állítjuk, hogy egy ilyen minimális hosszúságú szakasz felezőmerőlegese megfelelő egyenes.
Legyen A a piros, B pedig a fekete konvex burok egy-egy olyan pontja, amelyekre AB minimális. (A és B nem feltétlenül eredetileg "színes'' pontok.) Tegyük fel, hogy f felező merőlegesük nem választja el a konvex burkokat, vagyis f egy C pontja hozzá tartozik pl. a piros pontok konvex burkához (3. ábra).
 
 
3. ábra
 

Ismét felhasználva, hogy egy konvex halmaz két pontját összekötő szakasz is a konvex halmazhoz tartozik, kapjuk, hogy az AC szakasz teljes egészében benne van a piros pontok konvex burkában. Tekintsük a B pont AC-re eső merőleges vetületét (az ábrán T). Mivel BAC∢ hegyesszög, Taz AC szakasz belsejében van, ezért T is a piros pontok konvex burkához tartozik. A BAT derékszögű háromszögben BT<BA, és így T közelebb van B-hez, mint A, azaz feltevésünkkel ellentétben AB nem minimális távolság a két konvex burok között. Ez azt jelenti, hogy az f egyenes valóban elválasztja a konvex burkokat, és így a piros,illetve a fekete pontokat is.