Feladat: 1992. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Boda Péter ,  Németh Ákos ,  Tichler Krisztián ,  Újváry-Menyhárt Zoltán 
Füzet: 1993/február, 53 - 55. oldal  PDF file
Témakör(ök): Sík geometriája, Ponthalmazok, Egyéb szinezési problémák, Egyéb sokszögek geometriája, Kombinatorikus geometria síkban, Háromszögek nevezetes tételei, Pont körüli forgatás, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1993/február: 1992. évi Kürschák matematikaverseny 3. feladata

Adott a síkban véges sok pont, amelyek közül semelyik három nem esik egy egyenesre. Bizonyítsuk be, hogy kiszínezhetők két színnel úgy, hogy ne legyen olyan félsík, mely a pontok közül pontosan hármat tartalmaz, és azok egyszínűek.

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.

Vegyük a ponthalmaz konvex burkát, azt a legkisebb sokszöget, amelyik az összes pontot tartalmazza. (Lásd az alábbi 1. megjegyzést). Ennek csúcsai az adott pontok közül valók, és a feltétel szerint az oldalszakaszok belsejére nem esik adott pont.
Egy olyan félsík, amelyikbe három adott pont esik, tartalmazza a pontok meghatározta háromszöget, így tartalmaz a konvex burok belsejében levő pontot. A határegyenese tehát átmetszi a konvex burkot, ezért a félsík tartalmazza a konvex burok legalább egy csúcsát.
A burok belsejében lehetnek az adott pontok közül olyanok, amelyeket egy olyan félsík sem tartalmaz, amelyikbe csak három adott pont esik. Ezek színezése a feladat követelményének teljesülését nem befolyásolja. Ez adhatja azt a gondolatot, hogy az összes belső pontot fessük ugyanolyanra, mondjuk kékre.

 
 

1. ábra
 

A burok csúcsait ezután több lépésben színezzük ki. Első lépésben fessük az összeset pirosra. Ha most van három szomszédos csúcs, A, B, C, amelyek meghatározta háromszög nem tartalmaz további adott pontot, akkor B színét változtassuk kékre (1. ábra). Ha ezután is maradt ilyen csúcs-hármas, akkor ismételjük az eljárást. Ez véges számú lépésben befejeződik.
Megmutatjuk, hogy így megfelelő színezéshez jutunk. Jegyezzük meg, hogy nem keletkezik a konvex burkon két szomszédos kék csúcs, mert ha egy csúcsot kékre festünk, akkor a szomszédos csúcsok már nem lehetnek olyan háromszög középső csúcsai, amelyiknek mind a három csúcsa piros.
Ha egy félsík három csúcsot tartalmaz, akkor az azok meghatározta háromszög nem tartalmaz további adott pontot, tehát vagy a középső csúcs kék, a két szomszédja piros, vagy azért nem változtattuk meg a középső csúcs színét, mert a csúcsok nem voltak egyszínűek.
 
 

2. ábra
 

Ha két csúcsot tartalmaz a félsík, akkor tartalmaz a konvex burok belsejében lévő, tehát kék pontot, viszont a két csúcsnak legfeljebb az egyike lehet kék.
Ha végül a három pontot tartalmazó félsík egy csúcsot tartalmaz, akkor a határegyenese átmetszi az abból induló két oldalt (2. ábra). A tartalmazott csúcs és a két szomszédja tehát olyan háromszöget határoz meg, amelyik tartalmaz a burok belsejében levő (tehát kék) pontot, s így a csúcsot meghagytuk pirosnak. Ezzel állításunkat beláttuk.
Megjegyzések. 1. A sík egy véges ponthalmazának a konvex burkát megkaphatjuk például úgy, hogy választunk egy félsíkot, amelyik tartalmazza a ponthalmazt. Annak a határegyeneshez legközelebbi (egyik) pontján át a határegyenessel párhuzamost húzunk, majd ezt forgatjuk a rajta levő, vagy ha több van, az egyik szélső adott pont körül úgy, hogy a ponthalmaz az egyik oldalán legyen, amíg újabb adott pont nem kerül rá. Ezután ekörül, illetőleg megint a szélső körül forgatjuk tovább az egyenest ugyanabban az irányban (3. ábra). Az eljárás véges számú lépésben befejeződik azzal, hogy visszajutunk az egyenes kezdő helyzetéhez. A forgásközéppontok a keresett konvex burok csúcsai.
\epsfbox{93-02-55.eps}{3., 4. ábra}
 
 

3. ábra
 

 
 

4. ábra
 

2. A megoldásban leírt eljárást adta meg Boda Péter. Ez láthatóan általában nem egyértelmű, több megfelelő színezéshez is vezethet aszerint, hogy hogyan választjuk azokat a háromszögeket, amelyek középső csúcsát átszínezzük.
A feladat többi megoldói a következő eljárást adták. A belső pontok kékre festése után pirosra festjük a konvex burok egy csúcsát, ha az a szomszédos csúcsokkal olyan háromszöget alkot, amelyik tartalmaz a belsejében adott pontot. Végül az esetleg színezetlenül maradt csúcsok alkotta íveken egy irányba haladva a szomszédos piros csúcs utánit kékre festjük és a következőket felváltva pirosra és kékre, míg a következő piros csúcsig nem érünk (4. ábra), a burok két szélső csúcsa lehet kék is, piros is.
A leírt színezés is kiadja ezt, ha egy irányba haladva mindig a legközelebbi háromszöget vesszük, amelyiknek a középső csúcsát át kell színezni. Ebből látható, hogy ez az eljárás is megfelelő.