A B. 4682. feladat (2015. január)

B. 4682. Adott $\displaystyle k$ pozitív egész számhoz keressük meg azt a legnagyobb $\displaystyle m$ pozitív egészet, amelyre a következő teljesül: ha a síkon $\displaystyle 3k$ különböző pont közül legfeljebb $\displaystyle m$ darab esik egy egyenesbe, akkor a pontok $\displaystyle k$ darab hármas csoportba oszthatók úgy, hogy az egy csoportban lévő pontok egy háromszög csúcsai.

Javasolta: Frank András (Nagykovácsi)

(5 pont)

A beküldési határidő 2015. február 10-én LEJÁRT.

Megoldási ötlet: Indukció.

Megoldás. Megmutatjuk, hogy $\displaystyle m=2k$.

Először azt látjuk be, hogy ha van olyan egyenes, amelyik a $\displaystyle 3k$ pont közül legalább $\displaystyle (2k+1)$-et tartalmaz, akkor a pontok nem oszthatók $\displaystyle k$ darab hármas csoportba úgy, hogy az egy csoportban lévő pontok egy háromszög csúcsai. Ez azonnal következik abból, hogy tetszőleges háromszög három csúcsa közül egy egyenes legfeljebb kettőt tartalmaz, ezért $\displaystyle k$ darab különböző háromszög csúcsai közül legfeljebb $\displaystyle 2k$ darabot tartalmazhat bármely egyenes.

Ha nincs olyan egyenes, amelyik $\displaystyle 2k$-nál többet tartalmaz a $\displaystyle 3k$ pont közül, akkor $\displaystyle k$ szerinti teljes indukcióval megmutatjuk, hogy a pontok $\displaystyle k$ darab hármas csoportba oszthatók úgy, hogy az egy csoportban lévő pontok egy háromszög csúcsai. Ha $\displaystyle k=1$, akkor a feltételünk szerint a három pont nem kollineáris, ezért egy háromszög csúcsait alkotja, tehát ekkor igaz az állítás. A $\displaystyle k=2$ esetet is külön bizonyítjuk, mert az indukciós lépés során fel fogjuk használni, hogy a pontok száma legalább 6. Ha a pontok közül semelyik három nem kollineáris, akkor bárhogyan is osztjuk őket két csoportba, az egy csoportban lévő pontok egy háromszög csúcsai lesznek. Ha a pontok közül pontosan négy, mondjuk $\displaystyle A$, $\displaystyle B$, $\displaystyle C$ és $\displaystyle D$ egy $\displaystyle e$ egyenesre esik, a maradék kettő, $\displaystyle E$ és $\displaystyle F$ pedig nincs rajta $\displaystyle e$-n, akkor például $\displaystyle \{A,B,E\}$, $\displaystyle \{ C,D,F\}$ jó beosztás (1. ábra). Végül ha a pontok közül semelyik négy nem kollineáris, de mondjuk $\displaystyle A$, $\displaystyle B$ és $\displaystyle C$ egy $\displaystyle e$ egyenesre esik, akkor a maradék három pont közül válasszunk ki kettőt, legyenek ezek $\displaystyle D$ és $\displaystyle E$. Feltehető, hogy a $\displaystyle DE$ és $\displaystyle e$ egyenesek metszéspontja nem $\displaystyle A$. Ekkor ha a hatodik pont $\displaystyle F$, akkor például $\displaystyle \{A,D,E\}$, $\displaystyle \{B,C,F\}$ jó beosztás (2. ábra).

1. ábra                                                             2. ábra

Tegyük fel, hogy az állítás igaz $\displaystyle k=n>1$-re. Legyen adott $\displaystyle 3(n+1)$ különböző pont úgy, hogy közülük legfeljebb $\displaystyle 2(n+1)$ esik egy egyenesbe. Tekintsük azokat az egyeneseket, melyek a pontok közül legalább kettőt tartalmaznak.

Legyen ezek száma $\displaystyle N$. (Az ilyen egyenesek száma véges, hiszen nyilván fennáll az $\displaystyle N\le \binom{3n+3}{2}$ egyenlőtlenség.) Jelölje ezeket az egyeneseket $\displaystyle \ell_1,\ell_2,\ldots,\ell_N$, és válasszuk úgy a számozást, hogy ha $\displaystyle |\ell_i|$ az adott pontok közül azoknak a száma, melyeket az $\displaystyle \ell_i$ egyenes tartalmaz, akkor minden $\displaystyle i=1,2,\ldots,N-1$ esetén teljesüljön az $\displaystyle |\ell_i|\ge |\ell_{i+1}|$ egyenlőtlenség (a számozás nem egyértelmű, mert lehetnek olyan egyenesek, melyek ugyanannyi pontot tartalmaznak).

Először megmutatjuk, hogy $\displaystyle |\ell_3|<2n+1$. Tegyük fel, hogy ez nem igaz. Ha $\displaystyle |\ell_3|\ge 2n+1$, akkor $\displaystyle |\ell_2|\ge 2n+1$ és $\displaystyle |\ell_1|\ge 2n+1$ is fennáll. Ezért e három egyenes az adott pontok közül legalább $\displaystyle 3(2n+1)-3=6n$ különbözőt tartalmaz, hiszen az egyeneseken lévő pontok közül legfeljebb az $\displaystyle \ell_1\cap \ell_2$, $\displaystyle \ell_1\cap \ell_3$ és $\displaystyle \ell_2\cap \ell_3$ pontokat számoltuk kétszer a $\displaystyle 3(2n+1)$ összegben (3. ábra). Viszont $\displaystyle n>1$ miatt $\displaystyle 6n>3n+3$, s ebből az ellentmondásból következik, hogy $\displaystyle |\ell_3|<2n+1$. Hasonló módon látjuk be, hogy $\displaystyle |\ell_2|<2n+2$. Ha ugyanis $\displaystyle |\ell_2|\ge 2n+2$, akkor $\displaystyle |\ell_1|\ge 2n+2$, ezért e két egyenes az adott pontok közül legalább $\displaystyle 2(2n+2)-1=4n+3>3n+3$ különbözőt tartalmaz, hiszen az egyeneseken lévő pontok közül legfeljebb az $\displaystyle \ell_1\cap \ell_2$ pontot számoltuk kétszer a $\displaystyle 2(2n+2)$ összegben. Ebből az ellentmondásból következik, hogy $\displaystyle |\ell_2|<2n+2$.

3. ábra

Tehát $\displaystyle |\ell_1|\le 2n+2$, $\displaystyle |\ell_2|\le 2n+1$, és ha $\displaystyle i>2$, akkor $\displaystyle |\ell_i|\le 2n$ teljesül. Válasszunk ki az $\displaystyle \ell_1$ egyenesen lévő adott pontok közül kettőt tetszőlegesen, és vegyünk hozzájuk harmadiknak az $\displaystyle \ell_2$ egyenesen lévő adott pontok közül egy olyat, amelyik nincs rajta az $\displaystyle \ell_1$ egyenesen. E három pont nyilván háromszöget alkot. A maradék $\displaystyle (3n+3)-3=3n$ pontra pedig teljesül az indukciós feltevésünk, mert közülük semelyik $\displaystyle 2n$ nincs egy egyenesen. Hiszen továbbra is csak az $\displaystyle \ell_i$ egyenesek tartalmaznak a pontok közül legalább kettőt, az $\displaystyle \ell_1$-en lévő maradék pontok száma legfeljebb $\displaystyle (2n+2)-2=2n$, az $\displaystyle \ell_2$-en lévő maradék pontok száma legfeljebb $\displaystyle (2n+1)-1=2n$, a többi egyenesre pedig $\displaystyle |\ell_i|\le 2n$ teljesül. Vagyis ezek a pontok beoszthatók $\displaystyle n$ darab hármas csoportba úgy, hogy az egy csoportban lévő pontok egy háromszög csúcsai. Ezért a $\displaystyle 3n+3$ pont is beosztható a feltételeknek megfelelően, s ezzel állításunkat beláttuk.

Statisztika:

76 dolgozat érkezett.
5 pontot kapott:	Andó Angelika, Baran Zsuzsanna, Csépai András, Fekete Panna, Gáspár Attila, Katona Dániel, Kovács Péter Tamás, Lajkó Kálmán, Mócsy Miklós, Molnár-Sáska Zoltán, Nagy Dávid Paszkál, Nagy-György Pál, Németh 123 Balázs, Schrettner Bálint, Szebellédi Márton, Szőke Tamás, Tóth Viktor, Williams Kada.
4 pontot kapott:	Bursics Balázs, Döbröntei Dávid Bence, Hansel Soma, Jenei Dániel Gábor, Kovács 246 Benedek, Nagy Simon József, Schwarcz Tamás, Váli Benedek.
3 pontot kapott:	6 versenyző.
2 pontot kapott:	27 versenyző.
1 pontot kapott:	15 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2015. januári matematika feladatai