Feladat: 1970. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bajmóczy Ervin ,  Füredi Zoltán ,  Kóczy László ,  Martoni Viktor ,  Ruzsa Imre 
Füzet: 1971/május, 197 - 198. oldal  PDF  |  MathML 
Témakör(ök): Egyéb szinezési problémák, Természetes számok, Oszthatóság, Kombinatorikai leszámolási problémák, Háromszögek nevezetes tételei, Teljes indukció módszere, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1971/február: 1970. évi Kürschák matematikaverseny 3. feladata

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. Megadunk egy utasítást arra, hogyan kell a még nem színezett szakaszokat színezni. Legyen AB egy olyan szakasz, amelynek végpontjai az adott pontok közül valók és amely még nincs kiszínezve. A feltétel szerint létezik egy és csakis egy olyan törött vonal, mely eredetileg színezett szakaszokból áll és A-t B-vel köti össze. Jelölje VAB ezt a törött vonalat. Legyen mármost az AB szakasz

 
kék, ha VAB páratlan sok kék szakaszt tartalmaz és legyen
piros, ha VAB páros sok kék szakaszt tartalmaz.
 

(Megjegyezzük, hogy ez a ,,színezési szabály'' akkor is érvényes, ha AB már eleve is színezett volt.)
Megmutatjuk, hogy a fenti ,,színezési szabály'' kielégíti a feladat követelményeit. Legyen e célból ABC tetszőleges háromszög, melynek csúcsai az adott pontok közül valók.
Először is megadható olyan D pont, melyből az A-ba, B-be, C-be vezető, eredetileg színezett szakaszokból álló VDA, VDB, VDC utaknak nincsen D-től különböző közös pontjuk (megengedjük itt, hogy D egybeessen pl. A-val, ekkor VDA egyetlen pontból áll). Tekintsük ugyanis az A-t B-vel összekötő, eredetileg színezett szakaszokból álló VAB utat. C-ből A felé elindulva a VCA úton, előbb-utóbb elérjük a VAB út valamely D pontját (ha C rajta fekszik a VAB úton, akkor D=C; természetesen az is előfordulhat, hogy D=A vagy D=B). Könnyen látható, hogy az így megszerkesztett D pont a fenti kikötésnek eleget tesz (5. ábra).
 
 

5. ábra
 

Mármost a fenti színezési szabály szerint, az AB, BC, AC szakaszok között rendre annyi kék van, ahány páratlan szám előfordul az
 
x=a  VDA és VDB utakon fekvő kék szakaszok száma,
y=a  VDB és VDC utakon fekvő kék szakaszok száma és
z=a  VDC és VDA utakon fekvő kék szakaszok száma között.
 

Mivel x+y+z páros (hiszen VDA, VDB, VDC utak minden kék szakasza kétszer van beszámítva ebbe az összegbe), az ABC háromszögnek valóban páros sok kék oldala van.
 
II. Megoldás. Válasszunk ki egy tetszőleges A0 pontot és színezzük ki sárgára. Ezek után a többi pontot is kiszínezzük sárgával és zölddel a következőképpen: egy A0-ból kiinduló, eredetileg is színezett szakaszokból álló törött vonal mentén haladva, az i-edik pont legyen az (i-1)-edikkel azonos színű, ha a kettőt összekötő szakasz piros, és különböző színű, ha az összekötő él kék. Mivel a feltétel szerint bármely pontba egy és csakis egyféleképpen juthatunk el ilyen törött vonalon, azért minden pont színe egyértelműen meg van határozva.
Ezek után a következő ,,színezési szabályt'' adhatjuk meg: az AB él legyen
 
piros, ha A, B mindegyike zöld vagy mindegyike sárga, és legyen
kék, ha A, B különböző színűek.
 
Megállapíthatjuk, hogy az eredetileg megszínezett szakaszok e ,,színezési szabálynak'' megfelelően vannak színezve.
Tekintsünk mármost egy tetszőleges ABC háromszöget, melynek csúcsai az adott pontok közül valók. Ha A, B, C azonos színűek, akkor az AB, BC, AC szakaszok mindegyike piros. Ha, mondjuk A és B azonos és C tőlük különböző színű, akkor AB piros, AC és BC kék. A piros szakaszok száma tehát vagy 3 vagy 1, mindenképpen páratlan. Tehát a megadott ,,színezési szabály'' a feladat kikötésének eleget tesz.
 
Megjegyzések. 1. Több dolgozat a pontok száma szerinti teljes indukcióval igazolta az állítást.
2. Megmutatható ‐ erre több versenyző utalt is ‐, hogy a szakaszoknak a feladatbeli színezése egyértelmű. Legyen ugyanis AB tetszőleges szakasz. A feltétel szerint A és B összeköthető egy, eleve színezett élekből álló
A0A1...An¯(A0=A,An=B)
törött vonallal. Mármost az A0A1A2 háromszögben páratlan sok piros élnek kell lennie, ez meghatározza az A0A2 szakasz színét. Így az A0A2A3 háromszögben már két szakasz színe adott, ez meghatározza az A0A3 szakasz színét. Hasonlóan továbbmenve láthatjuk, hogy az AB szakasz színe is egyértelműen meg van határozva.
3. Elegendő volna a feladatban annyit feltenni, hogy bármely két pont legfeljebb egyféleképpen köthető össze eredetileg is megszínezett szakaszokból álló törött vonallal. Ilyenkor ugyanis (mint az könnyen igazolható) meg lehet még néhány további szakaszt színezni úgy, hogy a kapott szakaszokra már a feladat feltétele teljesüljön.