Feladat: B.3458 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Babos Attila ,  Balka Richárd ,  Bérczi Kristóf ,  Birkner Tamás ,  Buti Tamás ,  Horváth Márton ,  Konfár András ,  Paulin Roland ,  Sparing Dániel ,  Tóth János 
Füzet: 2002/február, 86 - 87. oldal  PDF file
Témakör(ök): Egyéb szinezési problémák, Síkgeometriai bizonyítások, Kombinatorikus geometria, Feladat
Hivatkozás(ok):Feladatok: 2001/április: B.3458

Adott a síkon n piros pont. Mutassuk meg, hogy elhelyezhető 2n kék pont úgy, hogy a piros pontok által meghatározott minden háromszög belsejében van legalább egy kék.

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.

Megadunk egy eljárást a kék pontok egy megfelelő elhelyezésére. Először vegyünk fel egy olyan e egyenest, ami nem párhuzamos egyetlen olyan egyenessel sem, ami legalább két piros pontot tartalmaz. Ilyen e egyenes van, mert az n darab piros pont legfeljebb (n2) különböző irányt határoz meg, a síkon pedig végtelen sok különböző irány létezik. Ezután minden piros ponton át rajzoljunk egy-egy e-vel párhuzamos egyenest. Az e definíciójából következően így n db különböző párhuzamos egyenest kapunk úgy, hogy mindegyikük pontosan egy piros pontot tartalmaz. Rögzítsünk egy d távolságot, ami bármely olyan valódi háromszög mindhárom magasságánál rövidebb, amelynek a csúcsai piros pontok. Ezek után az előbbi n egyenes mindegyikén vegyünk föl két kék pontot az egyenesen lévő piros pontra szimmetrikusan, attól éppen d távolságra. Így a kék pontok száma 2n.


 1. ábra 2. ábra 

Megmutatjuk, hogy ha az F, G, H piros pontok háromszöget alkotnak, akkor ennek belsejében van legalább egy kék pont. Legyenek f, g és h a háromszög csúcsain átmenő, e-vel párhuzamos egyenesek. E három különböző egyenes közül egy a másik kettő között van. Feltehetjük, hogy ez a g (2. ábra). Ekkor g az FH szakaszt annak valamely G' belső pontjában metszi. Mivel GG' legalább akkora, mint az EFG háromszög G-ből induló magasságszakasza, azért a GG' szakasz belsejében ‐ s így az EFG háromszög belsejében ‐ van kék pont.
 Babos Attila (ELTE Radnóti M. Gyak. Gimn., 12. évf.) dolgozata alapján

 

Megjegyzés. Megmutatható, hogy ha a piros pontok konvex burka (azaz a legkisebb olyan konvex sokszög, amelyik mindegyik piros pontot tartalmazza) k-oldalú sokszög, akkor 2n-2-k kék pont is elég ahhoz, hogy minden piros háromszög belsejében legyen közülük legalább egy. A konvex burok csúcsain átmenő e-vel párhuzamos egyenesekre ugyanis elég csak 1-1 kék pontot elhelyeznünk, sőt a két szélső egyenesre egyet sem kell tennünk (lásd a 3. ábrát).

3. ábra