 |
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