Feladat: B.4937 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Biczó Benedek 
Füzet: 2018/december, 538 - 539. oldal  PDF  |  MathML 
Témakör(ök): Feladat, Teljes indukció módszere, Egyéb szinezési problémák
Hivatkozás(ok):Feladatok: 2018/február: B.4937

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.

Színezzük ki a sík rácspontjait k színnel. A feladat feltétele szerint van olyan rácsnégyszög, amelynek a csúcsai egyforma színűek. Ez legyen az A négyszög. Ezután készítünk egy új színezést úgy, hogy az A négyszög csúcsainak színezését lecseréljük a k+1, k+2, k+3 és k+4 színre. A feladat feltétele alapján ennél a színezésnél is létezik olyan négyszög, amelynek a csúcsai egyforma színűek, legyen ez a B négyszög. Ennek a négyszögnek egyik csúcsa sem fog egybeesni az A négyszög csúcsaival, mert k+1-től k+4-ig a színekből csak egy-egy darab csúcs van, viszont a B négyszög mind a négy csúcsának ugyanolyan színűnek kell lennie. Tehát a B négyszögnek biztosan nincs közös csúcsa az A négyszöggel. Most a B négyszög csúcsait festjük át k+5, k+6, k+7, k+8 színűre. Ekkor is létezik olyan négyszög amelynek csúcsai egyforma színűek (legyen ez a négyszög C), aminek nem lehet közös csúcsa sem A-val, sem B-vel, mert C olyan négyszög, amelynek mindegyik csúcsa egyszínű, viszont az A és B csúcsainak színei csak pontosan egyszer fordulnak elő az újabb színezésben. Az eljárást folytatva, tegyük fel, hogy már n darab páronként diszjunkt rácsnégyszöget kiválasztottunk. Akkor az előző eljárással kiválaszthatunk egy további olyat, amely az eddigiektől teljesen különböző. Végtelen sok olyan négyszöget fogunk kapni, amelyeknek nincs közös csúcsa.

 

 Biczó Benedek (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 9. évf.)
 dolgozata alapján