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, , , , amelyek meghatározta háromszög nem tartalmaz további adott pontot, akkor 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.
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ő. |