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