Megoldás: 15.6
1. megoldás.
Először b)-t bizonyítjuk.
Tekintsük azt a gráfot, amelynek csúcsai a ponthalmaz pontjai és élei az átmérők. Ha ebben a gráfban minden pont foka legfeljebb kettő, akkor összesen legfeljebb
n éle van, tehát a feladat állítása teljesül.
Tegyük fel, hogy egy
P pont foka nagyobb kettőnél. Legyenek a
P-ből induló átmérők
PQ1
,
PQ2
, ...,
PQk
,
k>2. A
Qi
pontok rajta vannak a
P közepű
d sugarú kör egy 60-os ívén. Ugyanis bármely két
PQi
szakasz által bezárt szög legfeljebb 60 -os, különben a két végpont távolsága nagyobb volna
d-nél. Ebből az már következik, hogy az összes
Qi
pont rajta van egy 120 -os köríven, s akkor a két szélső közötti szög sem lehet nagyobb 60 -nál. Feltehetjük, hogy úgy számoztuk a
Qi
pontokat, hogy a számozás sorrendjében jönnek a köríven.
Tegyük fel, hogy valamelyik
Qi
-ből indul ki még egy átmérő (a
PQi
-n kívül) egy
S pontba. Ez nem lehet a
PQ1
Qk
háromszög belsejében, sőt, annak a körcikknek a belsejében sem, amelyet
PQ1
és
PQk
határol. Feltehetjük, hogy
S-et a
PQ1
szakasz elválasztja
Qk
-tól. Tekintsük a
PS szakasz
f felező merőlegesét!
f-en rajta van a
Qi
pont, mert
P-től is,
Qi
-től is
d távolságra van. Ezért
f-nek azonos oldalán van
P és
Qk
.
[Ha nem akarunk a szemléletre hivatkozni, akkor ezt a következőképpen igazolhatjuk.
SQk
szakasz metszi
PQ1
szakaszt, a metszéspont legyen
M.
MQk
szakaszt metszi
PQi
szakasz, a metszéspont legyen
L. Végül
f metszi az
ML szakaszt.] Tehát
Qk
távolabb van
S-től, mint
P. Ebből
SQk
>SP=d következik, ami ellentmondás.
Ez azt jelenti, hogy minden
k>2-ed fokú ponthoz tartozik
k-2 darab elsőfokú pont a gráfban, s nyilván különböző pontokhoz különböző elsőfokú pontok tartoznak. Hagyjuk el a gráfból az elsőfokú pontokat a hozzájuk tartozó éllel. Azt láttuk be, hogy így csupa legfeljebb másodfokú pont marad. Ha tehát
m darab elsőfokú pont volt, akkor maradt
n-m pont, s legfeljebb ugyanennyi él. Viszont összesen
m élt hagytunk el, tehát valóban legfeljebb
n él volt eredetileg.
A bizonyításból a)-ra a példa már leolvasható: vegyünk egy
ABC egységoldalú
ABC szabályos háromszöget, és az
A középpontú egységsugarú kör
BC
^
ívén
n-3 további pontot.
Megjegyzés. Páratlan
n-re jó a szabályos
n-szög
n csúcsa, hiszen ennek a ponthalmaznak a leghosszabb átlók az átmérői, s ezekből páratlan
n esetén pontosan
n van.
2. megoldás.
Nyilvánvaló, hogy egy átmérő mindkét végpontja az
n pont konvex burkán van. Ha ugyanis
AB egy tetszőleges szakasz a konvex burkon belül, amely a konvex burok kerületét
A' és
B' pontban metszi, akkor vagy
A' és
B' is csúcsa a konvex buroknak, vagy ha például
B' nem csúcs, akkor van olyan
C csúcs a konvex burkon, amely
B'-nél távolabb van
A'-től.
Az is nyilvánvaló, hogy két átmérő biztosan metszi egymást. Ha ugyanis nem metszenék egymást, akkor a végpontjaik paralelogrammát alkotnának, amelynek a két átmérő volna az egyik oldalpárja. De a paralelogramma valamelyik két átellenes pontja távolabb van egymástól, mint az oldal.
Ezzel a feladatot visszavezettük a
16.17. feladatra: ott láthatjuk, hogy a konvex buroknak legfeljebb annyi átlója húzható meg úgy, hogy bármely kettő messe egymást, ahány csúcsa van.