A B. 4372. feladat (2011. szeptember)

B. 4372. Mutassuk meg, hogy ha n pont úgy helyezkedik el, hogy bármely négy közül kiválasztható három, amelyek egy egyenesre esnek, akkor a pontok közül legalább n-1 kollineáris.

(3 pont)

A beküldési határidő 2011. október 10-én LEJÁRT.

Megoldás. Az állítást \(\displaystyle n\) szerinti indukcióval igazoljuk. Ha \(\displaystyle n\le 4\), akkor az állítás nyilvánvaló. Az indukciós lépéshez tegyük fel, hogy \(\displaystyle n\ge 5\), és \(\displaystyle n-1\) esetén az állítást már beláttuk. Hagyjuk el a ponthalmaz egyik pontját. A fennmaradó \(\displaystyle n-1\) elemű ponthalmazra a feltételek teljesülnek, tehát az indukciós feltevés alapján található benne egy \(\displaystyle n-2\) elemű \(\displaystyle P\) részhalmaz, melynek pontjai egy egyenesre esnek. Hagyjuk el most az eredeti ponthalmazból \(\displaystyle P\)-nek egy pontját. Az így kapott \(\displaystyle n-1\) elemű ponthalmazban is található egy \(\displaystyle n-2\) elemű \(\displaystyle Q\) részhalmaz, melynek pontjai egy egyenesre esnek. Mivel \(\displaystyle P\ne Q\), a \(\displaystyle P\cup Q\) halmaz legalább \(\displaystyle n-1\) elemű. Elég tehát megmutatni, hogy \(\displaystyle P\cup Q\) elemei egy egyenesre esnek.

Tegyük fel, hogy nem ez a helyzet, ekkor \(\displaystyle P\)-nek és \(\displaystyle Q\)-nak legfeljebb egy közös \(\displaystyle a\) eleme lehet. Ez kell is, hogy létezzen, hiszen \(\displaystyle |P\cap Q|\ge n-4\ge 1\). Mivel \(\displaystyle |P\setminus \{a\}|=|Q\setminus \{a\}|=n-3\ge 2\), létezik négy pont, \(\displaystyle b,c\in P\setminus \{a\}\) és \(\displaystyle d,e\in Q\setminus \{a\}\), melyek közül semelyik három nem esik egy egyenesre. Ez azonban ellentmond a feltételeknek.

Statisztika:

204 dolgozat érkezett.
3 pontot kapott:	152 versenyző.
2 pontot kapott:	28 versenyző.
1 pontot kapott:	15 versenyző.
0 pontot kapott:	8 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2011. szeptemberi matematika feladatai