Feladat: 1986. évi Nemzetközi Matematika Diákolimpia 23. feladata Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Tóth Géza 
Füzet: 1986/november, 359 - 360. oldal  PDF  |  MathML 
Témakör(ök): Teljes indukció módszere, Konstruktív megoldási módszer, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):Feladatok: 1986/szeptember: 1986. évi Nemzetközi Matematika Diákolimpia 23. 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.

6. feladat. Adott a síkban egy véges sok rácspontból álló halmaz. Döntsük el, vajon minden esetben lehetséges-e ezek közül a pontok közül néhányat pirosra, a többit pedig fehérre színezni úgy, hogy minden olyan egyenesen, amely párhuzamos valamelyik koordináta-tengellyel, a rajta lévő piros pontok száma legfeljebb 1-gyel térjen el az ugyancsak rajta lévő fehér pontok számától.

 

Megoldás. A pontok számára vonatkozó teljes indukcióval bebizonyítjuk, hogy mindig létezik a kívánt színezés. Egy pont esetén az állítás nyilvánvaló. Tegyük fel tehát, hogy n≥2, és n-nél kevesebb pont esetén kiszínezhetők a pontok az előírt módon, és megadjuk az n pontnak egy megfelelő színezését.
Könnyű dolgunk van, ha található olyan P pont, melynek sorában további pont már nincs. Ekkor P-t elhagyva a megmaradt (n-1) pontot színezzük ki a megfelelő módon, és ha P oszlopában legalább annyi piros pont van, mint fehér, akkor P-t színezzük fehérre, ha eggyel több fehér pont van, mint piros, akkor pedig pirosra. Ekkor az n pontnak egy jó színezését kaptuk, hiszen P sorában és oszlopában teljesül a feltétel, a többi sorban és oszlopban pedig nem történt változás. Hasonló a helyzet, ha van olyan P pont, melynek oszlopában nincs további pont. Vizsgáljuk tehát azt a fennmaradó esetet, amikor minden pont sorában és oszlopában is van további pont. Ekkor egy tetszőleges A1 pontból kiindulva, annak sorában választhatunk egy tőle különböző A2 pontot, A2 oszlopában A3-t, A3 sorában A4-t, és így tovább felváltva. Minthogy véges sok (n) pontunk van, véges sok lépés után az A1, A2, ... pontsorozatban olyan tagot kell választanunk, amely már szerepelt. Legyen tehát Ar=Ap (r>p) az első ilyen ismétlődés. Ha r-p páros, akkor az Ap, Ap+1, ..., Ar-1 sorozatban minden tag az egyik szomszédjával egy sorban, a másikkal egy oszlopban van (ha Ar-1-t és Ap-t is szomszédoknak tekintjük). Gondoljunk utána, hogy ha r-p páratlan, akkor ugyanez mondható az Ap+1, Ap+2, ... Ar-1 sorozatról. Hagyjuk el tehát ezen sorozat pontjait, a maradékot az indukciós feltétel szerint kiszínezhetjük a kívánt módon, a sorozat pontjait pedig színezzük ezután felváltva pirosra, ill. fehérre. Ekkor az n pontnak egy jó színezését kapjuk, hiszen minden sorban és oszlopban ugyanannyival változtatjuk meg a piros, ill. fehér pontok számát. Ezzel az indukciós lépést elvégeztük, a feladat kérdésére igenlő választ adhatunk.