Feladat: F.1769 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Angyal József ,  Pósfai János 
Füzet: 1971/október, 55 - 56. oldal  PDF file
Témakör(ök): Kombinatorikus geometria síkban, Feladat
Hivatkozás(ok):Feladatok: 1971/április: F.1769

Adva van a síkon n db egyenes, bármelyik kettőjük metszi egymást, de egyetlen metszésponton sem megy át három egyenes. Legföljebb hány új egyenest kapunk, ha összekötünk minden olyan metszéspont-párt, amelyiket nem köt össze az eredeti egyenesek egyike sem?

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. Az n egyenes (n2)=p különböző metszéspontot határoz meg, legyen közülük egy az M pont, és legyenek az ezt meghatározó egyenesek a és b. M-et egy más, M' metszésponttal összekötve mindenesetre új egyenest kapunk ‐ az adottakhoz képest ‐, ha M' sem a-n, sem b-n nincs rajta, vagyis ha M' a további (n-2) egyenes metszéspontjai közül való. Az ilyenek száma (n-22)=q. A gondolható pq összekötés 2-esével mindenesetre ugyanazt az egyenest adja ‐ MM' és M'M szerepekben ‐, így ha más egybeesés nem lép föl,

12pq=12(n2)(n-22)=18n(n-1)(n-2)(n-3)
új egyenest kapunk, különben pedig kevesebbet.
 

Pósfai János (Szombathely, Nagy Lajos Gimn., IV. o. t.)
 

II. megoldás. Elég a kérdést n4 esetén vizsgálni, hiszen könnyű belátni, hogy n=3 esetén nincs lehetőség új összekötésre.
n=4 esetén legyenek az egyenesek a, b, c, d. Új összekötő egyenest kapunk, ha a és egy további egyenes metszéspontját összekötjük a hátralevő egyenesek metszéspontjával, pl. a és b metszéspontját c és d metszéspontjával. b-t előbb c-vel, majd d-vel cserélve még 2 összekötést kapunk, együttvéve 3-at.
Az n>4 esetekben a megoldást az n=4 esetre vezethetjük vissza. Az előbbi a, b, c, d egyenes szerepére más 4 egyenest véve az adottak közül, mindhárom előbbi új egyenes helyére más összekötő egyenest kapunk, azt értve ezen, hogy az összekötést meghatározó két metszéspont közül legalább az egyik különböző az előbbiektől. (Maga az egyenes lehet azonos egy már megkapottal, ti. olyan esetben, ha egy összekötő egyenes átmegy egy további metszésponton.) Eszerint az összekötési lehetőségek száma legföljebb 3-szor annyi, mint az adott n egyenes közül kiválasztható négyesek száma:
3(n4)=n(n-1)(n-2)(n-3)124

Angyal József (Budapest, Berzsenyi D. Gimn., IV. o. t.)