|
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 szakasz szerepel, és mindegyiknek a végpontjai különböző színűek. Ilyen összesen 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 és olyan szakaszok, amelyek végpontjai kölünböző színűek ‐ például és piros, és kék ‐ és van közös pontjuk, ábránkon ez az pont. A háromszög-egyenlőtlenség alapján
és ezekből:
Ez ellentmond annak, hogy az és 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 ö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 szakasszal, akkor a keresztezőket az ábra szerint módosítva, az 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. -re az állítás igaz. Tegyük föl ezután, hogy az állítás minden -nél kisebb pozitív egészre igaz. Megmutatjuk, hogy ekkor -re is igaz. Ehhez elegendő olyan egyenest találni, amelynek egyik oldalán ugyanannyi (-nél kevesebb, de -nál több) piros pont van, mint kék. Tekintsük a pont konvex burkát, és ezen belül egy új pontot úgy, hogy a pont közül semelyik ne essen egy egyenesre. Ilyen pont biztosan van, hiszen a pont véges számú egyenest határoz meg, és -t felvehetjük úgy, hogy ezen egyenesek egyikére se illeszkedjék. Húzzunk -n át egy olyan egyenest, amelyen egy sincs az adott pont közül. Ha az egyenes egyik oldalán ugyanannyi piros pont van mint kék, akkor készen vagyunk, mert így mindkét oldalán lévő pontokra alkalmazható az indukciós feltevés. Ellenkező esetben legyen jobb oldalán darab piros pont és darab kék. Forgassuk el az egyenest körül -kal. Ha a forgatás közben egy pontot átlép, a különbség -gyel változik (nő vagy csökken). -os forgatás után az egyenes jobb oldalán lévő piros és kék pontok számának különbsége lesz. Mivel az egyenes forgatása közben egy-egy pontot átlépve mindig -gyel változott, és forgás után az ellentettje lett, volt egy olyan helyzet, amikor értéke zérus volt. Ekkor az 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.)
|
|