Feladat: B.3614 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Salát Máté 
Füzet: 2004/február, 86 - 87. oldal  PDF  |  MathML 
Témakör(ök): Ponthalmazok, Testek szinezése, Feladat
Hivatkozás(ok):1951/december: Egyenlőtlenségek (4)
Feladatok: 2003/február: B.3614, 1951/november: 341. matematika feladat

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 adott pontok véges sok egyenest határoznak meg. Így létezik olyan egyenes, amely ezek egyikével sem párhuzamos. Húzzunk párhuzamost egy ilyen egyenessel az összes adott ponton át. Ezek a párhuzamos egyenesek mind különböznek egymástól. Metsszük el ezeket a párhuzamos egyeneseket egy újabb egyenessel. A metszéspontok halmaza ugyanannyi pontból áll, mint az adott ponthalmaz, a két halmaz elemeit a párhuzamos egyenesek kölcsönösen egyértelműen feleltetik meg egymásnak. A metszéspontok által meghatározott szakaszok felezőpontjait kékre festve megállapíthatjuk, hogy legfeljebb annyi kék pont van, mint piros, mivel ha az adott pontok közül két pontpár felezőpontja egybeesett, akkor képeik (párhuzamos vetületeik) felezőpontjai is egybeesnek. Jelölje az adott pontok számát n. Jelölje a metszéspontok közül a két szélsőt A és B, AB felezőpontját F.
A kék pontok száma legalább 2(n-2)+1=2n-3, ugyanis a középső n-2 metszéspontot A, illetve B középpontból felére kicsinyítve csupa kék pontot kapunk, melyek közül az előbbiek mind az AF szakasz belső pontjai, az utóbbiak mind a BF szakasz belső pontjai, és még az F pont is kék. Következésképp a piros pontok száma is legalább 2n-3.
A piros pontok száma lehet 2n-3, ha például az A1,A2,...,An pontokat egy számegyenes 1,2,...,n pontjaiban vesszük föl. Ekkor ugyanis a felezőpontok éppen a 2 nevezőjű törtek 1 és az n között, így a számuk éppen 2n-3.

 
II. megoldás. Ha n=1, akkor egyetlen felezőpont sem jön létre. Megmutatjuk, hogy ha 2n, akkor a piros pontok minimális száma 2n-3.
Először is, ha Ai a számegyenesen az i-1 számot kijelölő pont, akkor pontosan azok a pontok lesznek pirosak, melyek egy 0-nál nagyobb, ám 2n-2-nél kisebb egész szám felét jelölik ki; ez éppen 2n-3 pont.
Most már csak annyit kell megmutatnunk, hogy az Ai pontok tetszőleges elhelyezkedése esetén lesz ennyi piros pont. Ezt n szerinti teljes indukcióval igazoljuk.
Ha n=2, akkor mindig pontosan 1=22-3 piros pont jön létre. Ha pedig n pont mindig legalább 2n-3 piros pontot határoz meg, akkor az A1,...,An+1 pontokból kiindulva rajzoljuk meg a P={A1,...,An} halmaz C konvex burkát. Legyen ennek egy csúcsa B, az e pedig legyen olyan egyenes, amely C-t B-ben érinti. Legyen még B1 és B2 a P\{B} halmaz két olyan pontja, mely az e egyeneshez a lehető legközelebb helyezkedik el. A P\{B} halmaz indukciós feltevésünk szerint legalább 2n-3 piros pontot határoz meg; legyen ezek halmaza F. A B1B és a B2B szakaszok felezőpontja nem esik egybe, és nem lehet eleme F-nek sem, hiszen mindkét pont közelebb esik az e egyeneshez, mint a B1B2 szakasz felezőpontja, míg F pontjai legalább olyan távol vannak az e-től, mint a B1B2 szakasz felezőpontja. Ez tehát két újabb piros pont, vagyis a P halmaz legalább (2n-3)+2=2(n+1)-3 piros pontot határoz meg, ahogyan azt az indukciós lépéshez igazolnunk kellett.