Feladat: Gy.2076 Korcsoport: 14-15 Nehézségi fok: átlagos
Megoldó(k):  Borsodi Brigitta 
Füzet: 1983/április, 163 - 164. oldal  PDF  |  MathML 
Témakör(ök): Egyéb szinezési problémák, Gyakorlat
Hivatkozás(ok):Feladatok: 1982/október: Gy.2076

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.

Négy pont esetén egy, a feltételeknek megfelelő színezés látható az ábrán.

Állítjuk, hogy több pont esetén már nem lehet a szakaszokat megfelelően kiszínezni.
Először is belátjuk, hogy semelyik pontból sem indulhat 3 ugyanolyan színű szakasz. Válasszunk ki ugyanis a pontok közül 4-et. Jelöljük ezeket A, B, C és D-vel. Állításunkkal ellentétben kösse össze A-t B,C és D-vel ugyanolyan színű szakasz. Legyen ez a szín mondjuk piros. Ekkor sem BC, sem BD, sem CD nem lehet piros, mert akkor nem teljesülne a b) feltétel. Legyen BC zöld, ekkor az a) feltétel miatt BD és CD is csak zöld lehet. így viszont BCD háromszög oldalai egyszínűek, ellentétben a b) feltétellel.
Egy pontból tehát legfeljebb 2 ugyanolyan színű szakasz indulhat, és mivel csak kétféle színt használhatunk fel az egy pontból induló szakaszok színezésénél, ezért egy pontból legfeljebb 4 szakasz indulhat. Ebből már következik, hogy a pontok száma legfeljebb 5 lehet. Az 5 pont, ha nincs közülük 3 egy egyenesen, összesen 10 szakaszt határoz meg. Ha kiválasztok egyet és abból két piros szakaszt indítok, akkor azokból a pontokból, ahová ezek a szakaszok befutnak, egy további piros szakasz indul. A b) feltétel miatt ezek különböző szakaszok, ezért legalább 4 piros szakasz van. Mivel ez a másik két színre is igaz, s mind a három szint fel kell használni, minimum 12 szakasz kellene. Az 5 pont között viszont csak 10 szakasz húzható, így 5 pont esetén sem lehet a szakaszokat úgy kiszínezni, hogy valamennyi feltétel teljesüljön. Ezzel állításunkat igazoltuk.
 

Borsodi Brigitta (Tata, Eötvös J. Gimn., II. o. t.) dolgozata alapján

 

Megjegyzés. Nagyon sok hibás dolgozat érkezett a feladat félreértelmezése miatt. Többen külön-külön vizsgálták a 3 feltétel teljesülését, holott azoknak egyszerre kell teljesülniük.
Néhányan nem találták meg 4 pontra a jó színezést, mivel azt úgy keresték, hogy 3 ponthoz talált megoldáshoz hozzávettek egy pontot. Így valóban nem lehet a feladat feltételeit teljesíteni, hiszen a 4 pont közül bárhogyan is választunk ki 3-at, az általuk meghatározott szakaszok között van két egyező színű.
Nem kaptak pontot azok, akik egyetlen színezést mutatva meg, kijelentették, hogy az 5 pontra nem végezhető el. Ez még nem jelenti, hogy nem létezik esetleg a feladat feltételeit kielégítő megoldás. Ezt láthattuk is, 4 pont esetén is egyaránt találhatunk jó és rossz színezést.
A hiányos dolgozatok többsége 5 pontra bizonyította a színezés lehetetlenségét, de nem mutatta meg, hogy 5-nél több pont esetén sem lehetséges a feltételeknek eleget tenni. A kérdés viszont az volt, hogy "legfeljebb hány pont'' színezhető.