Feladat: F.2929 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Csorba Péter ,  Csörnyei Marianna ,  Dőtsch András ,  Futó Gábor ,  Gröller Ákos ,  Kórász Árpád ,  Rákóczi Bálint ,  Ruzsa Zoltán ,  Sánta Zsuzsa ,  Szurdi Miklós 
Füzet: 1993/szeptember, 257 - 259. oldal  PDF  |  MathML 
Témakör(ök): Konstruktív megoldási módszer, Logikai feladatok, Teljes indukció módszere, Kombinatorika - Gráfelmélet, Feladat
Hivatkozás(ok):Feladatok: 1992/november: F.2929

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. Tekintsük az összes olyan összekötési lehetőséget, amelyben n szakasz szerepel, és mindegyiknek a végpontjai különböző színűek. Ilyen összesen n! számú van, tehát véges sok, ezért van közöttük minimális összhosszúságú. Válasszunk egy ilyen minimális hosszúságú szakasz-rendszert ‐ ha több ilyen is van, valamelyiket. Állítjuk, hogy ebben nincsen metsző szakaszpár. Tegyük fel ugyanis, hogy AB és CD olyan szakaszok, amelyek végpontjai kölünböző színűek ‐ például A és C piros,  B és D kék ‐ és van közös pontjuk, ábránkon ez az M pont. A háromszög-egyenlőtlenség alapján

BC<BM+MC  és  AD<AM+MD,
és ezekből:
AD+BC<CD+AB.

 
 

Ez ellentmond annak, hogy az AB és CD szakaszokat tartalmazó szakaszrendszer összhossza minimális volt. Ezért igaz a feladat állítása.
A leírt eljárás nemcsak a kívánt n összekötő szakasz létezését bizonyítja, hanem konstrukciót is tartalmaz a szakaszok meghúzására. Ha a piros-kék pontpárokat valahogy már összekötöttük n szakasszal, akkor a keresztezőket az ábra szerint módosítva, az n szakasz összhossza minden lépésben csökken, és az eljárás véges sok lépés után véget ér.
 

 Sánta Zsuzsa (Fazekas M. Főv. Gyak. Gimn. I. o. t.)
 

II. megoldás. A feladat állítását teljes indukcióval bizonyítjuk. n=1-re az állítás igaz. Tegyük föl ezután, hogy az állítás minden n-nél kisebb pozitív egészre igaz. Megmutatjuk, hogy ekkor n-re is igaz. Ehhez elegendő olyan egyenest találni, amelynek egyik oldalán ugyanannyi (n-nél kevesebb, de 0-nál több) piros pont van, mint kék. Tekintsük a 2n pont konvex burkát, és ezen belül egy új P pontot úgy, hogy a 2n+1 pont közül semelyik 3 ne essen egy egyenesre. Ilyen P pont biztosan van, hiszen a 2n pont (2n2) véges számú egyenest határoz meg, és P-t felvehetjük úgy, hogy ezen egyenesek egyikére se illeszkedjék. Húzzunk P-n át egy olyan e egyenest, amelyen egy sincs az adott 2n pont közül. Ha az e egyenes egyik oldalán ugyanannyi piros pont van mint kék, akkor készen vagyunk, mert így e mindkét oldalán lévő pontokra alkalmazható az indukciós feltevés. Ellenkező esetben legyen e jobb oldalán p darab piros pont és k darab kék. Forgassuk el az e egyenest P körül 180∘-kal. Ha e a forgatás közben egy pontot átlép, a p-k különbség 1-gyel változik (nő vagy csökken). 180∘-os forgatás után az e egyenes jobb oldalán lévő piros és kék pontok számának különbsége (n-p)-(n-k)=-(p-k) lesz. Mivel az e egyenes forgatása közben egy-egy pontot átlépve p-k mindig 1-gyel változott, és 180∘ forgás után az ellentettje lett, volt egy olyan helyzet, amikor p-k értéke zérus volt. Ekkor az e egyenes mindkét oldalán ugyanannyi a piros pont mint a kék, és alkalmazható az indukciós feltevés.
 

 Ruzsa Zoltán (Fazekas M. Főv. Gyak. Gimn. IV. o. t.)