Feladat: F.2461 Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1984/október, 309. oldal  PDF  |  MathML 
Témakör(ök): Egyéb szinezési problémák, Feladat
Hivatkozás(ok):Feladatok: 1984/február: F.2461

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.

Legyen i tetszőleges egész szám. Tekintsük az (1, i), (2, i), (3, i), (4, i) koordinátájú pontnégyest. Mind a négy pont három különböző színt kaphat, ezt a négy pontot tehát 34=81 különböző módon színezhettük. Ha veszünk 82 ilyen pontnégyest, pl. futtatjuk i-t 1-től 82-ig, akkor ezek között lesz kettő, amelyek teljesen azonosan vannak színezve, vagyis van két különböző i és j az 1 és 82 között, amelyre (1, i) színe megegyezik (1, j) színével, (2, i) színe (2, j) színével stb.
De az (1, i), (2, i), (3, i), (4, i) pontnégyes között van két azonos színű, hiszen csak három színünk van. Legyenek (a,i), és (b,i) ilyenek (1a<b4). Ekkor (a,i), (a,j), (b,j), (b,i) négy egyszínű rácspont, amelyek a koordinátatengelyekkel párhuzamos oldalú téglalapot alkotnak.

 

Megjegyzés. A fenti megoldás mutatja, hogy ha egy 4×81-es táblázat minden mezőjét három szín valamelyikével kiszínezünk, akkor van két sor és két oszlop, amelyek négy találkozási pontja egyező színű. Ugyanígy belátható, hogy ha nem három, hanem k színünk van, akkor bármely (k+1)×kk+1-es táblázatban van két ilyen sor és oszlop. Érdekes, de nehezebb kérdés, hogy mekkora az a minimális négyzet alakú táblázat, amiben már feltétlenül van két ilyen sor és oszlop.
A megoldás gondolatmenete további általánosítást is lehetővé tesz. Tegyük fel, hogy k színnel kiszíneztük a rácspontokat. Ekkor akármilyen m egészre kiválasztható végtelen sok sor és m különböző oszlop úgy, hogy a kiválasztott sorok és oszlopok találkozásánál álló rácspontok mind azonos színűek legyenek. Nem mindig választható ki azonban végtelen sok sor és végtelen sok oszlop ugyanezzel a tulajdonsággal. Ennek megmutatására elég az (x,y) rácspontot pirosra színezni, ha |x|>|y| és kékre, ha |x||y| .