Feladat: 1998. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 1999/február, 72 - 74. oldal  PDF  |  MathML 
Témakör(ök): Síkbeli ponthalmazok távolsága, Konvex sokszögek, Konstruktív megoldási módszer, Teljes indukció módszere, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1999/február: 1998. évi Kürschák matematikaverseny 3. feladata

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.

Tekintsünk egy N elemű H ponthalmazt, amely megfelel a feladatban szereplő feltételeknek. Tegyük fel, hogy H konvex burkának n csúcsa van. Ezt a konvex n-szöget egy csúcsából kiinduló átlói segítségével n-2 háromszögre bonthatjuk, amelyek mindegyikében H-nak pontosan egy pontja helyezkedik el, a második feltétel értelmében. Egy ilyen háromszög határára ‐ az első feltétel miatt ‐ H-nak nem eshet más pontja, mint a szóban forgó háromszög 3 csúcsa. A H halmaz tehát pontosan a konvex burkának a csúcspontjaiból és az előbb említett n-2 pontból áll. Ennek következtében N=2n-2=2(n-1), azaz páros szám.
A következőkben megmutatjuk, hogy minden 3-nál nagyobb N páros szám esetén megadható a síkon N pont a követelményeknek megfelelően. Legyen n=N+22, ekkor n3. Tekintsünk egy tetszőleges P0P1...Pn-1 konvex n-szöget. Ennek a belsejében vegyünk fel n-2 további pontot a következőképpen. Minden 1in-2 esetén legyen Qi a P0PiPn-1 és Pi-1PiPi+1 háromszögek közös részének tetszőleges belső pontja. Azt állítjuk, hogy a H={P0,P1,...,Pn-1,Q1,...,Qn-1} ponthalmaz megfelel a feltételeknek.
Legyen 0i<j<kn-1. Azt állítjuk, hogy a PiPjPk háromszög belseje H pontjai közül egyedül a Qj pontot tartalmazza. Először azt mutatjuk meg, hogy Qj valóban a PiPjPk háromszög belső pontja. A PiPjPk szögtartomány tartalmazza a P0, Pj, Pn-1 pontokat, és így a P0PjPn-1 háromszög minden pontját is. Minthogy Qj ennek a háromszögnek belső pontja, Qj a PiPjPk szögtartomány belsejében van (1. ábra).
Hasonlóképpen látható, hogy Qj a PiPk egyenesre támaszkodó, Pj-t tartalmazó félsík belsejében található, hiszen ez a félsík tartalmazza a Pj-1, Pj, Pj+1 pontokat, és Qj a Pj-1PjPj+1 háromszög belső pontja (2. ábra).
A Qj pont tehát az 1. ábrán látható nyílt szögtartomány és a 2. ábrán látható nyílt félsík közös részében van, ez pedig éppen a PiPjPk háromszög belső pontjainak halmaza. Most megmutatjuk, hogy ez a halmaz H pontjai közül a Qj-n kívül egyetlen pontot sem tartalmaz. A P0P1...Pn-1 sokszög konvex, ezért egyik csúcsa sem eshet a PiPjPk háromszög belsejébe. Tekintsük most valamelyik Ql pontot, ahol lj. Ez a pont a Pl-1PlPl+1 háromszög belsejében helyezkedik el. Ha l<i, akkor a P0Pi egyenes elválasztja ezt a háromszöget a PiPjPk háromszögtől, tehát Ql valóban nem eshet az utóbbi háromszög belsejébe. Az i<l<j, j<l<k, illetve k<l esetekben a megfelelő elválasztó egyenesek rendre a PiPj, PjPk és PkPn-1 egyenesek. A 3. ábra az l=j-1 esetet szemlélteti. Ezzel állításunkat bizonyítottuk.
Hátravan még annak igazolása, hogy H pontjai közül semelyik három nem esik egy egyenesre. A konstrukcióból azonnal következik, hogy semelyik PiPj egyenes nem illeszkedhet H-nak egyetlen további pontjára sem. Ha tehát egy egyenes H pontjai közül hármat is tartalmazna, akkor tartalmaznia kellene legalább két Q típusú pontot. Legyenek ezek Qs és Qt. A QsQt egyenes a P0P1...Pn-1 sokszög kerületét két pontban metszi, jelöljük ezeket U-val és V-vel. Ha ezek közül az egyik, mondjuk U a sokszög Pi csúcsa volna, akkor V szükségképpen a sokszög valamely PjPk oldalának belső pontja lenne. Ekkor a PiPjPk háromszög a Qs és a Qt pontokat is tartalmazná, fenti állításunkkal ellentétben. Ha pedig U és V rendre a sokszög PiPj és PkPl oldalainak lenne belső pontja (feltehető, hogy Pi, Pj, Pk és Pl ilyen sorrendben, egy konvex négyszög csúcsai), akkor H-nak összes pontja, amely a QsQt egyenesre illeszkedik, a PiPjPkPl négyszög belsejébe esne. Ez azonban lehetetlen, hiszen a fenti állításból könnyen levezethető, hogy ez a négyszög H-nak pontosan két pontját tartalmazza.
Ezzel a feladat megoldását befejeztük.

 
Megjegyzések. 1. Páros N esetén a keresett ponthalmaz létezésére indukciós bizonyítás is adható, amelyet csak vázolunk. Tegyük fel, hogy a P0P1...Pn-1 konvex sokszöget, és annak Q1, ..., Qn-2 belső pontjait már meghatároztuk úgy, hogy semelyik 3 pont nem esik egy egyenesre, és minden PiPjPk háromszög belsejébe pontosan egy Q pont esik. Vegyük fel a Pn pontot úgy, hogy P0P1...Pn-1Pn konvex (n+1)-szög legyen, semelyik PnPiPn+1 háromszög ne tartalmazzon egyetlen Qj pontot sem, továbbá Pn ne legyen rajta egyik olyan egyenesen sem, amely az eddigi pontok közül kettőre már illeszkedik. ,,Látszik'', hogy ezt mindig megtehetjük. A szabatos bizonyítás megfogalmazása azonban egyáltalán nem magától értetődő. Ezek után vegyük fel a Qn-1 pontot a Pn-1PiPn (0in-1) háromszögek közös részeinek belsejében, ami éppen a Pn-1P0Pn és Pn-1Pn-2Pn háromszögek közös részének belseje. Eközben vigyázunk arra, hogy Qn-1 ne essék egyetlen olyan egyenesre sem, amelyeket az eddigi pontok meghatároznak. A keletkező {P0,P1,...,Pn,Q1,...,Qn-1} ponthalmaz konvex burka éppen a P0P1...Pn sokszög, és semelyik 3 pontja nem esik egy egyenesre. Az indukciós feltevésből adódik, hogy a PiPjPk belsejébe pontosan egy pont esik, ha n{i,j,k}. A Qn-1 pont konstrukciója alapján ugyanez elmondható a Pn-1PnPi háromszögekről is. Végül tekintsük bármelyik PiPjPk háromszöget, ahol i<j<n-1. A PiPjPn-1Pn négyszögbe, melyet annak PjPn-1 átlója a PnPn-1Pj és a Pn-1PjPi háromszögekre bont, az előzőek alapján pontosan 2 pont esik. Ezek egyike a Qn-1 pont, amely a Pn-1PnPi háromszög egyetlen belső pontja a tekintett pontok közül. Ezért a másik pont szükségképpen a PiPjPn-1 háromszögbe esik, és oda más pont nem is eshet (4. ábra).
2. Ha az n=3 esetén felrajzolható, lényegében egyértelmű konstrukcióból kiindulunk, és arra a fenti indukció lépéseit alkalmazzuk, akkor az első megoldásban ismertetett konstrukcióhoz hasonló pontrendszerhez jutunk. Felmerülhet az a gondolat, hogy lehetséges-e ,,geometriailag más szerkezetű'' ponthalmazokat is mutatni, amelyek a feltételeknek szintén megfelelnek. Ilyen ponthalmazokat is képezhetnénk az indukciós eljárás segítségével, ha nem ragaszkodunk ahhoz, hogy a P0, P1, ..., Pn csúcspontokkal rendelkező konvex sokszög csúcsai éppen ilyen sorrendben kövessék egymást.
Az 5. ábrán három különböző konstrukciót mutatunk N=10 (n=6) esetén.