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. A feladat állítását teljes indukcióval bizonyítjuk. Ha , akkor a háromszöget kell az számmal megszámozni, és ez lehetséges, mégpedig egyféleképpen. Tegyük most fel, hogy -re igaz a tétel, vagyis egy háromszögekre bontott, konvex -szög háromszögeit meg lehet számozni a kívánt módon. Legyen egy konvex -szög, amelyiket egymást nem metsző átlók háromszögekre bontanak. Hagyjuk el a csúcsot, és a belőle induló szakaszok helyett húzzuk meg a szakaszokat. Ezzel a sokszög egy felosztását kaptuk átlók útján. Ezek az átlók sem metszhetik egymást, mert azok az átlók, amelyek az eredeti sokszögben is meg voltak húzva, nem metszik egymást, egy olyan átló pedig, amelyik egy átló helyébe lépett, csak olyan átlót metszhetne át, amelyiknek egyik végpontja és közt van, ide azonban nem esik csúcsa egyik sokszögnek sem. Az új átlók a -szöget háromszögekre bontják. Az eredeti sokszögnek azok a részháromszögei ugyanis, amelyeknek nem csúcsa , szerepelnek a -szög felbontásában is. Az eredeti sokszögben van egy háromszög, ezt összehúztuk a átlóra, a háromszögek helyébe pedig, ha , a háromszögek lépnek. Ezek együtt hézag és átfedés nélkül kitöltik a sokszöget. Ezek a háromszögek az indukciós feltevés szerint megszámozhatók a kívánt módon az , , , számokkal. Ezután a -szög felbontásában azok a háromszögek, amelyek a -szög felbontásában is szerepelnek, tartsák meg sorszámukat. Ha , és ha a háromszög fellép, akkor kapja azt a sorszámot, amit a -szög felbontásában a háromszög kapott (ez i vagy j). Végül a háromszögnek a sorszám jut. Világos, hogy így minden háromszögnek van a sorszámával egyező indexű csúcsa. A -szög háromszögei is megszámozhatók tehát a kívánt módon. Megjegyzések. 1. A bizonyítás menetét követve az is belátható, hogy mindig csak egyféleképpen végezhető el a háromszögek megszámozása a követelményeknek megfelelően. 2. Abból a feltételből, hogy egy konvex -szöget egymást nem metsző átlók háromszögekre bontanak, következik, hogy átlóval háromszögre van felosztva a sokszög. Valóban, minden átló meghúzása 1-gyel növeli a részsokszögek számát, a részsokszögek oldalainak együttes száma pedig 2-vel szaporodik, mert a korábbi oldalakon kívül a meghúzott átló is oldala lesz két sokszögnek. Ha tehát átló meghúzása után csupa háromszög keletkezett, akkor egyfelől háromszög keletkezett oldallal, másfelől a keletkezett részsokszögek oldalainak együttes száma . Ebből következik állításunk. Ezeknek a részadatoknak a kiszámítása azonban fölöslegesen terhelte volna a megoldásra rendelkezésre álló időt. 3. Más lehetőségek is kínálkoztak indukciós bizonyításra. Ezeket csak röviden jelezzük. a) Fogalmazzuk az indukciós feltételt úgy, hogy a -nál kisebb -ekre igaz az állítás. Egy -szög felbontásában szerepel egy háromszög. Ennek a sorszámot kell kapnia. Maradt két -nál nem több oldalú sokszög, vagy esetleg csak egy, ezeknek a háromszögeit az indukciós feltevés felhasználásával meg tudjuk a kívánt módon számozni. b) Könnyen látható, hogy és legalább egyikéből indul ki átló. Egy ilyennel két részsokszögre bontva, azok részháromszögei az indukciós feltétel felhasználásával megszámozhatók a kívánt módon. c) Többen azt bizonyították be, hogy van legalább két olyan csúcs, amelyikből nem indul ki átló. Ennél valamivel többet is állíthatunk. Egy ilyen "átlómentes'' csúccsal szomszédos csúcsokat átlónak kell összekötnie, ha a sokszög háromszögekre van bontva (amiből következik az is, hogy két szomszédos csúcs nem lehet egyszerre átlómentes). Nevezzük a keletkező háromszöget szélsőnek és jelöljük a szélső háromszögek számát -sel. Ezeknek két oldala sokszögoldal, a harmadik átló. Lesz olyan háromszög, amelyiknek egy oldala sokszögoldal, kettő átló, és lehetnek olyan háromszögek is, amelyeknek mindegyik oldala átló. Az utóbbiak számát jelöljük -vel Ekkor | | az átlók kétszeres számát adja, vagyis -et. Innen adódik, vagyis a szélső háromszögek száma 2-vel nagyobb a "belső'' háromszögekénél, tehát legalább 2. Két szélső háromszög "középső'' (átlómentes) csúcsa közül legalább az egyik különbözik -tól is, -től is. Egy ilyen háromszög csak a középső csúcs sorszámát kaphatja. Egy ilyen háromszöget elhagyva a maradó sokszög háromszögeit meg tudjuk számozni az indukciós feltétel alapján a kívánt módon. Adhatunk közvetlen utasítást is a háromszögek megszámozására. II. megoldás. Adjuk a felosztásban szereplő háromszögnek, ha , a számot. Ezzel minden háromszög kapott számot. Az is világos, hogy mindegyiknek a száma legalább és legfeljebb . Elég tehát még azt belátni, hogy két háromszög nem kaphatta ugyanazt a sorszámot. Ha a fenti háromszögön kívül még valamelyiknek csúcsa , akkor ennek nem lehet csúcsa a sokszög kerületének -tól -on át -ig menő részén, mert az azt -vel összekötő átló metszené -t. Nem lehet egy ilyen háromszögnek egy csúcsa a kerület részén, egy pedig a részen, mert az ezeket összekötő átló metszené -t is, -t is. Ekkor azonban a kérdéses háromszögnek vagy legkisebb indexű csúcsa, vagy a legnagyobb indexű, s így a háromszög -től különböző sorszámot kap. Ezzel a feladat állítását bebizonyítottuk. Megjegyzés. A feladat állítása igaz marad akkor is, ha tetszés szerinti sorrendben írjuk a csúcsok mellé a sorszámokat. Ha egy ilyen sorszámozás mellett és szomszédosak, akkor könnyen látható, hogy az állítás nem lényegesen más, mint az eredeti. Tegyük tehát fel, hogy nem szomszédosak. Ismét teljes indukcióval bizonyítunk. Ha , akkor és átellenes csúcsok. Ha a négyszög a átlóval van kettéosztva, akkor nyilván a háromszögnek kell az 1 számot kapnia, a másiknak a 2-t. Ha viszont a átló van meghúzva, akkor bármelyik háromszög kaphatja az 1-et és a másik a 2-t. Tegyük fel, hogy az állítás igaz a legfeljebb oldalú sokszögekre és legyenek egy háromszögekre bontott -szög csúcsai tetszés szerinti sorrendben -val jelölve, de és ne legyen szomszédos. Ha szerepel az átlók között, akkor ez két olyan sokszögre osztja a -szöget, amelyek külön-külön eleget tesznek a feladat feltételeinek (csak itt már két szomszédos csúcs az, amelyeknek az indexét nem használhatjuk fel a háromszögek számozásánál), ezek háromszögei tehát megszámozhatók az indukciós feltevés szerint a kívánt módon. Ha a átló nincs meghúzva, akkor legyen és a legközelebbi csúcs két oldalán, amelyik össze van kötve -val. Mivel a sokszög háromszögekre van bontva, a átlónak szerepelnie kell a kijelölt átlók közt. Vágjuk ketté ezzel a -szöget, és a -t tartalmazó sokszögben zárjuk még ki az -t, a -t tartalmazó sokszögben a -t a háromszögek számozására megengedett értékek közül. Ekkor a részsokszögek háromszögei megszámozhatók az indukciós feltétel szerint a kívánt módon, és ez a számozás megfelelő lesz a -szögre is, mivel a -t tartalmazó sokszögben -t, a -t tartalmazóban pedig -t felhasználtuk számozásra. |