Feladat: 1978. évi Kürschák matematikaverseny 2. feladata Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Cseri István ,  Csikós Balázs ,  Csók Tibor ,  Erdélyi Tamás ,  Mala József ,  Pyber László ,  Sali Attila ,  Szekeres Gábor 
Füzet: 1979/február, 52 - 53. oldal  PDF file
Témakör(ök): Egyéb sokszögek geometriája, Háromszögek nevezetes tételei, Egyéb szinezési problémák, Kombinatorikus geometria síkban, Teljes indukció módszere, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1979/február: 1978. évi Kürschák matematikaverseny 2. feladata

Egy páratlan oldalú konvex sokszög csúcsai úgy vannak megszínezve, hogy a szomszédos csúcsok különböző színűek. Bizonyítsuk be, hogy a sokszög háromszögekre bontható olyan egymást nem metsző átlókkal, amelyeknek végpontjai különböző szí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.

I. megoldás. Páratlan oldalú sokszög csúcsainak kívánt módon történő színezéséhez legalább három szín szükséges. Legyen ugyanis egy csúcs mondjuk piros, a következő kék. Ekkor tovább felváltva következik piros és kék csúcs, amíg egy harmadik szín fel nem lép. Ennek be kell következnie, mert különben páratlan számú csúcs esetén az utolsó csúcs is piros volna, meg a vele szomszédos első is.
Ezután eljárást adunk meg az átlók meghúzására. Mikor először jutunk harmadik színű csúcshoz, az az őt megelőző kettővel három szomszédos, különböző színű csúcs, mondjuk piros, kék és zöld. Ha a következő csúcs nem piros, akkor ezt a csúcsot s a zöldet összekötjük a pirossal. Ha a negyedik csúcs újra piros, de az ötödik nem kék, akkor a kék csúcsot kötjük össze a negyedikkel és az ötödikkel. Ha végül a negyedik csúcs piros, az ötödik kék, akkor a zöld csúcsot kötjük össze az elsővel és az ötödikkel. Mindhárom esetben két háromszöget vágnak le az átlók a sokszögről és visszamarad egy kettővel kevesebb ‐ tehát újra páratlan oldalszámú ‐ sokszög, amelyiknek szomszédos csúcsai különböző színűek. Így az eljárás folytatható. A továbbiakban meghúzandó átlók nem metszhetik a korábbiakat, mivel a sokszög konvex volta miatt azok az újabb sokszögön kívül haladnak vagy annak oldalai. Véges számú lépés után egy háromszög marad vissza, vagyis elérjük, hogy a sokszög háromszögekre van osztva a feladatban kívánt módon.

 
 

1. ábra
 

Megjegyzés. Az eljárást teljes indukciós bizonyításként is megfogalmazhattuk volna.
Többen észrevették, hogy az oldalszám páratlan volta csak annak biztosítására kellett, hogy a csúcsok legalább három színnel vannak színezve. Ezt mutatja a következő megoldás.
 
II. megoldás. Bebizonyítjuk, hogy a feladat állítása igaz minden olyan konvex sokszögre, amelyiknek a csúcsai legalább három színnel vannak megszínezve úgy, hogy a szomszédos csúcsok különböző színűek.
Ha van az összes többitől különböző színű csúcs, akkor egy ilyenből húzzuk meg az összes átlót és kapunk egy kívánt felbontást.
Ha minden színnel legalább két csúcs van színezve, akkor egy csúcsból elindulva nézzük az egymás utáni csúcsok színét, míg csak három különböző szín fel nem lép. Ekkor a harmadik színű csúcsot kössük össze a kettővel előtte levővel. Az átló különböző színű csúcsokat köt össze. Az általa lemetszett csúccsal maradt egyező színű a keletkezett eggyel kevesebb oldalú sokszögben, így az ugyanannyi színnel van színezve, mint az eredeti, tehát legalább hárommal, végül konvex, tehát egyetlen átlója sem metszheti a már meghúzott átlót. Ha tehát az eljárást ismételjük, véges számú lépésben eljutunk egy kívánt felbontáshoz. Ezzel bizonyítottuk állításunkat.
Ha egy sokszög csúcsai két színnel vannak a kívánt módon színezve, akkor a csúcsok felváltva egyik és másik színűek, tehát mindegyik színű csúcsból ugyanannyi van, így a csúcsok száma páros. Páratlan oldalú sokszög színezéséhez tehát legalább három színre van szükség, arra tehát vonatkozik a bizonyított tétel.