Feladat: 1985. évi Kürschák matematikaverseny 1. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Benczúr András ,  Birkás György ,  Bóna Miklós ,  Csizmadia György ,  Kós Géza ,  Makay Géza ,  Montágh Balázs ,  Rimányi Richárd ,  Szigeti Zoltán ,  Szkaliczki Tibor ,  Tóth Géza ,  Zaránd Gergely 
Füzet: 1986/február, 51 - 52. oldal  PDF file
Témakör(ök): Négyszögek geometriája, Háromszögek nevezetes tételei, Kombinatorikus geometria síkban, Teljes indukció módszere, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1986/február: 1985. évi Kürschák matematikaverseny 1. feladata

A P0P1...Pn konvex (n+1)-szöget n-2 egymást nem metsző átlóval n-1 háromszögre bontottuk. Bizonyítsuk he, hogy a háromszögek megszámozhatók az 1,2,...,n-1 számokkal úgy, hogy i=1,2...,n-1-re az i sorszámú háromszögnek valamelyik csúcsa Pi legyen.

I. megoldás. A feladat állítását teljes indukcióval bizonyítjuk. Ha n=2, akkor a P0P1P2 háromszöget kell az 1 számmal megszámozni, és ez lehetséges, mégpedig egyféleképpen.
Tegyük most fel, hogy n=(k-1)-re igaz a tétel, vagyis egy háromszögekre bontott, konvex k-szög háromszögeit meg lehet számozni a kívánt módon. Legyen P0P1...Pk egy konvex (k+1)-szög, amelyiket egymást nem metsző átlók háromszögekre bontanak. Hagyjuk el a Pk csúcsot, és a belőle induló PkPj szakaszok helyett húzzuk meg a Pk-1Pj szakaszokat. Ezzel a P0P1...Pk-1 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 Pk-1Pj átló pedig, amelyik egy PkPj átló helyébe lépett, csak olyan átlót metszhetne át, amelyiknek egyik végpontja Pk-1 és Pk közt van, ide azonban nem esik csúcsa egyik sokszögnek sem.
Az új átlók a (k-1)-szöget háromszögekre bontják. Az eredeti sokszögnek azok a részháromszögei ugyanis, amelyeknek nem csúcsa Pk, szerepelnek a (k-1)-szög felbontásában is. Az eredeti sokszögben van egy PjPk-1Pk háromszög, ezt összehúztuk a Pk-1Pj átlóra, a PiPjPk háromszögek helyébe pedig, ha i<j<k-1, a PIPjPk-1 háromszögek lépnek. Ezek együtt hézag és átfedés nélkül kitöltik a P0P1...Pk-1 sokszöget. Ezek a háromszögek az indukciós feltevés szerint megszámozhatók a kívánt módon az 1,2,...,k-2 számokkal.
Ezután a k-szög felbontásában azok a háromszögek, amelyek a (k-1)-szög felbontásában is szerepelnek, tartsák meg sorszámukat. Ha i<j<k-1, és ha a PiPjPk háromszög fellép, akkor kapja azt a sorszámot, amit a k-szög felbontásában a PiPjPk-1 háromszög kapott (ez i vagy j). Végül a PjPk-1Pk háromszögnek a k-1 sorszám jut. Világos, hogy így minden háromszögnek van a sorszámával egyező indexű csúcsa. A (k+1)-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 m-szöget egymást nem metsző átlók háromszögekre bontanak, következik, hogy m-3 átlóval m-2 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 k átló meghúzása után csupa háromszög keletkezett, akkor egyfelől k-1 háromszög keletkezett 3k+3 oldallal, másfelől a keletkezett részsokszögek oldalainak együttes száma m+2k. 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 k-nál kisebb n-ekre igaz az állítás. Egy (k+1)-szög felbontásában szerepel egy P0PjPk háromszög. Ennek a j sorszámot kell kapnia. Maradt két k-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 P0 és Pn 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 s-sel. Ezeknek két oldala sokszögoldal, a harmadik átló. Lesz n+1-2s 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 b-vel Ekkor
3b+2(n+1-2s)+s=2(n+1)-3(s-b)
az átlók kétszeres számát adja, vagyis (2n-4)-et. Innen
s=(b+2)
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 P0-tól is, Pn-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ő PiPjPk háromszögnek, ha i<j<k, a j számot. Ezzel minden háromszög kapott számot. Az is világos, hogy mindegyiknek a száma legalább 1 és legfeljebb n-1. Elég tehát még azt belátni, hogy két háromszög nem kaphatta ugyanazt a sorszámot.
Ha a fenti PiPjPk háromszögön kívül még valamelyiknek csúcsa Pj, akkor ennek nem lehet csúcsa a sokszög kerületének Pk-tól P0-on át Pi-ig menő részén, mert az azt Pj-vel összekötő átló metszené PiPk-t. Nem lehet egy ilyen háromszögnek egy csúcsa a kerület PiPj részén, egy pedig a PjPk részen, mert az ezeket összekötő átló metszené PiPj-t is, PjPk-t is. Ekkor azonban Pj a kérdéses háromszögnek vagy legkisebb indexű csúcsa, vagy a legnagyobb indexű, s így a háromszög j-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 0,1,...,n sorszámokat. Ha egy ilyen sorszámozás mellett P0 és Pn 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 n=3, akkor P0 és P3 átellenes csúcsok. Ha a négyszög a P0P3 átlóval van kettéosztva, akkor nyilván a P0P1P3 háromszögnek kell az 1 számot kapnia, a másiknak a 2-t. Ha viszont a P1P2 á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 k oldalú sokszögekre és legyenek egy háromszögekre bontott (k+1)-szög csúcsai tetszés szerinti sorrendben P0,P1,...,Pk-val jelölve, de P0 és Pk ne legyen szomszédos. Ha P0Pk szerepel az átlók között, akkor ez két olyan sokszögre osztja a (k+1)-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 P0Pk átló nincs meghúzva, akkor legyen Pi és Pj a legközelebbi csúcs Pk két oldalán, amelyik össze van kötve P0-val. Mivel a sokszög háromszögekre van bontva, a PiPj átlónak szerepelnie kell a kijelölt átlók közt. Vágjuk ketté ezzel a (k+1)-szöget, és a P0-t tartalmazó sokszögben zárjuk még ki az i-t, a Pk-t tartalmazó sokszögben a j-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 (k+1)-szögre is, mivel a P0-t tartalmazó sokszögben j-t, a Pk-t tartalmazóban pedig i-t felhasználtuk számozásra.