Feladat: Gy.2716 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Dombi Gergely 
Füzet: 1992/november, 376 - 377. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorikus geometria síkban, Ponthalmazok, Esetvizsgálat, Gyakorlat
Hivatkozás(ok):Feladatok: 1991/szeptember: Gy.2716

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.

Nevezzünk egy körökből álló halmazt összefüggőnek, ha bármely körvonal tetszőleges pontjából a köríveken haladva el tudunk jutni az összes többi körvonalhoz. A továbbiakban a következő állítást bizonyítjuk:
Ha a körökből álló M halmaz pontosan m darab összefüggő részre bomlik, és pontosan k darab pont illeszkedik legalább két körre, akkor ezek a körök legalább k+m+1 részre osztják a síkot.
Először legyen m=1, azaz M összefüggő. Kezdjük el egymás után lerajzolni a köröket úgy, hogy a kapott körhalmaz mindig összefüggő legyen. Ezt megtehetjük, hiszen M összefüggősége miatt minden lépésben lesz olyan, még le nem rajzolt kör, amely metszi vagy érinti a már lerajzoltak valamelyikét.

 
 

1. ábra
 

Legyen az n-edik lépésben lerajzolt körnek l darab közös pontja a már korábban lerajzoltakkal; ekkor l≥1. Ezt a kört az l pont l darab ívre osztja, és mindegyik ív egy zárt síkrészt oszt ketté, vagy a végtelen síkrészből kerít le egy zárt darabot (1. ábra). Tehát a síkrészek száma az n-edik lépésben l-lel, a körök metszés, ill. érintési pontjainak száma pedig legfeljebb l-lel nő, hiszen az n-edik lépésben berajzolt körnek a már korábban berajzoltakkal keletkező l darab közös pontja között lehetnek olyanok, amelyek már az n-edik lépés előtt is legalább két körre illeszkedtek.
Az első lépésben a lerajzolt egyetlen kör két részre osztja a síkot, és a legalább két körre illeszkedő pontok száma 0. Az előzőek szerint minden lépésben legalább annyival nő a síkrészek száma, mint a körök metszés, ill. érintési pontjainak a száma, így ‐ miután összesen k darab pont illeszkedik legalább két körre ‐ a keletkező síkrészek száma legalább k+2.
Áttérve az m>1 esetre, ha az i-edik összefüggő részben (i=1,2,...,m) a köröknek ki darab metszés-, ill. érintési pontja van, akkor ebben a részben legalább ki+2 darab síkrész keletkezett (a végtelen síkrésszel együtt). Figyelembe véve, hogy ∑i=1mki=k, valamint azt, hogy a végtelen síkrészt az m darab összefüggő rész mindegyikében számoltuk, az összesen keletkező síkrészek száma legalább
∑i=1m(ki+2)-(m-1)==∑i=1mki+2m-(m-1)=k+m+1.



 
 

2. ábra
 

A feladatban k=12, tehát a síkrészek minimális száma 14. Ennyi síkrész keletkezik például akkor, ha négy, páronként metsző körünk van (2. ábra).