Feladat: N.116 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bérczi Gergely ,  Braun Gábor ,  Frenkel Péter ,  Győri Nikolett ,  Kun Gábor ,  Kutalik Zoltán ,  Lippner Gábor ,  Lukács László ,  Pap Gyula ,  Terék Zsolt 
Füzet: 1997/április, 228 - 229. oldal  PDF file
Témakör(ök): Egyéb sokszögek geometriája, Háromszögek nevezetes tételei, Szélsőérték-feladatok differenciálszámítás nélkül, Nehéz feladat
Hivatkozás(ok):Feladatok: 1996/november: N.116

Egy kiállítóterem alaprajza konkáv n-szög. A teremben teremőröket kell elhelyeznünk úgy, hogy mindegyik fal mindegyik pontja látható legyen valamelyik őr helyéről. Legfeljebb hány őrre van szükség?

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.

Megmutatjuk, hogy [n3] őr mindig elegendő, és létezik olyan n-szög, amikor ugyanennyi szükséges is.
Először a szükségességet bizonyítjuk. Ha n=3k, akkor tekintsük az ábrán látható n-szöget.
Ebben az A2, A5, ..., A3k-1 csúcsok közül semelyik kettőt nem lehet ugyanarról a helyről látni (az ábrán besatíroztuk azokat a tartományokat, amelyekről ezeket a csúcsokat látni lehet), tehát legalább k őrre szükség van. Ha n=3k+1 vagy n=3k+2, akkor egy, illetve két újabb csúcs beillesztésével például az A1A3k oldalt két, illetve három részre oszthatjuk. Ezzel tehát mutattunk olyan n-szöget, amelyhez legalább [n3] őrre szükség van.
Az elégségesség bizonyításához először bontsuk fel az  n-szöget  n-3  átlójával  n-2  háromszögre. Ismeretes, hogy ez mindig lehetséges (bizonyítását lásd pl.
Surányi János: Matematikai versenytételek, III. kötet, 59. oldal, Tankönyvkiadó, Bp., 1992). Teljes indukcióval megmutatjuk, hogy a csúcsokat ki lehet színezni három színnel úgy, hogy mindegyik, a felbontásban szereplő háromszögben a három csúcs különböző színű. Ez n=3 esetén triviális. Ha n4, akkor van olyan háromszög, amely az n-szögnek két oldalára illeszkedik. (Pl. azért mert több oldal van, mint háromszög, és egy háromszög nem illeszkedhet három oldalra.) Ezt a háromszöget az n-szög két szomszédos oldala fogja közre, a harmadik oldala egy átló. Ha ezt a háromszöget elhagyjuk, a maradék (n-1)-szög kiszínezhető. Az elhagyott háromszögnek két csúcsát színeztük ki, mégpedig különböző színnel, mert az átló egy másik háromszögnek is oldala. Ezért a harmadik csúcs színét is megfelelően meg tudjuk választani.
Színezzük ki tehát a csúcsokat három színnel, és tekintsük azt a színt, amelyik a legkevesebbszer szerepel. Az ilyen színű csúcsokhoz egy-egy őrt állítva, az őrök minden falat és a sokszög minden belső pontját látják, számuk pedig nem lehet több n3-nál.

 Győri Nikolett (Fazekas M. Főv. Gyak. Gimn., I. o.t.) és
 
 Lukács László (Miskolc, Földes F. Gimn., II. o.) dolgozatából