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 . Jelölje a metszéspontok közül a két szélsőt és , felezőpontját . A kék pontok száma legalább , ugyanis a középső metszéspontot , illetve középpontból felére kicsinyítve csupa kék pontot kapunk, melyek közül az előbbiek mind az szakasz belső pontjai, az utóbbiak mind a szakasz belső pontjai, és még az pont is kék. Következésképp a piros pontok száma is legalább . A piros pontok száma lehet , ha például az pontokat egy számegyenes pontjaiban vesszük föl. Ekkor ugyanis a felezőpontok éppen a 2 nevezőjű törtek 1 és az között, így a számuk éppen .
II. megoldás. Ha , akkor egyetlen felezőpont sem jön létre. Megmutatjuk, hogy ha , akkor a piros pontok minimális száma . Először is, ha a számegyenesen az számot kijelölő pont, akkor pontosan azok a pontok lesznek pirosak, melyek egy 0-nál nagyobb, ám -nél kisebb egész szám felét jelölik ki; ez éppen pont. Most már csak annyit kell megmutatnunk, hogy az pontok tetszőleges elhelyezkedése esetén lesz ennyi piros pont. Ezt szerinti teljes indukcióval igazoljuk. Ha , akkor mindig pontosan piros pont jön létre. Ha pedig pont mindig legalább piros pontot határoz meg, akkor az pontokból kiindulva rajzoljuk meg a halmaz konvex burkát. Legyen ennek egy csúcsa , az pedig legyen olyan egyenes, amely -t -ben érinti. Legyen még és a halmaz két olyan pontja, mely az egyeneshez a lehető legközelebb helyezkedik el. A halmaz indukciós feltevésünk szerint legalább piros pontot határoz meg; legyen ezek halmaza . A és a szakaszok felezőpontja nem esik egybe, és nem lehet eleme -nek sem, hiszen mindkét pont közelebb esik az egyeneshez, mint a szakasz felezőpontja, míg pontjai legalább olyan távol vannak az -től, mint a szakasz felezőpontja. Ez tehát két újabb piros pont, vagyis a halmaz legalább piros pontot határoz meg, ahogyan azt az indukciós lépéshez igazolnunk kellett. |