Feladat: Gy.2361 Korcsoport: 14-15 Nehézségi fok: nehéz
Füzet: 1987/március, 119 - 120. oldal  PDF  |  MathML 
Témakör(ök): Egyéb szinezési problémák, Sakktáblával kapcsolatos feladatok, Gyakorlat
Hivatkozás(ok):Feladatok: 1986/október: Gy.2361

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. Hívjunk egy résztéglalapot "egyszínűnek'', ha egyforma színűek a sarokmezői. Tekintsük a tábla 3‐3 mezőből álló "oszlopait''. Ha ezek között van olyan, amelynek mindhárom mezője egyszínű ‐ például kék , akkor föltehető, hogy minden további oszlopban legfeljebb egy kék mező van, hiszen egyébként létrejön egyszínű téglalap. Egy oszlopot viszont négyféleképpen lehet úgy kiszínezni, hogy legfeljebb egy kék mezőt tartalmazzon: vagy mindhárom mező sárga, vagy pedig egyetlen kék mező lehet három helyen, míg a további két mező sárga. Ez azt jelenti, hogy az "azonosan kék'' oszlopon kívüli hat további oszlop között van legalább kettő azonosan színezett, és így nyilván van egyszínű téglalap. (Azok lesznek a sarokmezők, amelyek színe a két azonosan színezett oszlopban legalább kétszer fordul elő.)
Föltehető tehát ezután, hogy mindkét szín előfordul mind a 7 oszlopban. Az ilyen típusú színezések száma viszont hat, és mivel az oszlopok száma hét, ilyenkor is lesznek azonosan színezett oszlopok, és így egyszínű téglalap.

 

II. megoldás. Általában megmutatjuk, hogy ha k≧1 és egy (k+1)×[k(k+12)+1] oldalú sakktábla minden egyes mezőjét adott k szín valamelyikével kiszínezzük, akkor a sakktáblán van egyszínű résztéglalap. Feladatunkban k=2 és így k+1=3 és k⋅(k+12)+1=7.
Hívjuk továbbra is oszlopnak a k+1-hosszúságú oldallal párhuzamos sávokat! Miután a színek száma (k) kevesebb ‐ 1-gyel ‐, mint az oszlopok mezőinek a száma, minden oszlopban van olyan szín, amelyik itt legalább kétszer fordul elő. Jelöljünk meg két-két ilyen azonos színű mezőt minden egyes oszlopban.
Az oszlopok száma nagyobb, mint k⋅(k+12), és itt újra fölhasználva, hogy k-féle szín van, azt kapjuk, hogy több, mint (k+12) olyan oszlop van, amelyekben a megjelölt mezők színe ugyanaz ‐ mondjuk piros.
Vegyük most szemügyre ezeket az oszlopokat és a bennük megjelölt piros mezőket. Egy oszlopban k+1 mező van, ezek közül (k+12)-féleképpen jelölhetünk meg kettőt. A megjelölt piros mezőket tartalmazó oszlopok száma azonban a fentiek szerint ennél nagyobb, van tehát kettő, ahol a megjelölt két-két piros mező ugyanúgy helyezkedik el. Ez a négy piros mező eszerint egy egyszínű téglalap négy sarokmezeje. A bizonyítást ezzel befejeztük.
 

Megjegyzések. 1. A II. megoldásból is látszik, hogy a kimondott állítás egy bizonyos értelemben éles. Ha ugyanis egy k színnel színezett sakktáblán az oszlopok mezőinek a száma (k+1)-nél kevesebb, akkor nyilván lehetséges, hogy minden egyes oszlopban legfeljebb egyszer szerepeljen minden szín, ilyenkor pedig nem jön létre egyszínű téglalap.
Ha pedig a tábla egyik oldala k+1, a másik pedig k⋅(k+12), akkor amennyiben az oszlopokat k darab (k+12) elemű csoportba osztjuk, és a kifestés során az i-edik blokk (1≦i≦k) oszlopaiban az i-edik szín fordul elő kétszer, mégpedig minden lehetséges módon ‐ ez (k+12) lehetőség ‐ a további k-1 szín pedig egyszer, akkor nyilván nem jön létre egyszínű téglalap.
2. Általában, ha adott k és n esetén Tk(n) jelöli azt a legkisebb pozitív egészt, amelyre a k színnel kifestett n×Tk(n) oldalú sakktábla tartalmaz egyszínű téglalapot, akkor a fentiekből következik, hogy n≦k esetén Tk(n) nem létezik, míg Tk(k+1)=k⋅(k+12)+1.
3. A fenti eredmény nyilvánvaló következménye az alábbi: ha egy végtelen négyzetrács mezőit véges sok színnel kifestjük, akkor létrejön egyszínű téglalap. Ez az állítás téglalap helyett négyzettel is igaz, ennek a bizonyítása azonban nehéz.