A B. 3930. feladat (2006. szeptember)

B. 3930. Bizonyítsuk be, hogy ha egy konvex sokszög csúcsainak száma oszható 3-mal, akkor felbontható egymást nem metsző átlókkal háromszögekre úgy, hogy a sokszög minden csúcsa páratlan sok háromszögnek pontja.

(4 pont)

A beküldési határidő 2006. október 16-án LEJÁRT.

Megoldás: Legyen a sokszög csúcsainak száma 3k, ahol k pozitív egész. Az állítást k szerinti teljes indukcióval igazoljuk. Ha k=1, akkor az állítás nyilvánvaló. Legyen tehát k2, és tegyük fel, hogy bármely 3(k-1) csúcsú konvex sokszög háromszögekre bontható a kívánt módon. Tekintsünk egy konvex sokszöget. A sokszögnek húzzuk be néhány átlóját az indukciós feltevésnek megfelelő módon, ezek egyben a K sokszögnek is átlói. Ezeken kívül húzzuk még be K-ban a P₁P_3k-3, a P₁P_3k-1 és P_3k-3P_3k-1 átlókat. Így K-t is felbontottuk háromszögekre. Ez megfelelő lesz, ugyanis a csúcsokra ugyanannyi háromszög illeszkedik, mint K' felbontásában, a P₁ és P_3k-3 pontokra 2-vel több (tehát ugyancsak páratlan sok), a P_3k-2, illetve P_3k csúcsokra egy-egy, P_3k-1-re pedig 3.

Statisztika:

176 dolgozat érkezett.
4 pontot kapott:	146 versenyző.
3 pontot kapott:	12 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	13 versenyző.
Nem versenyszerű:	2 dolgozat.

A KöMaL 2006. szeptemberi matematika feladatai