Feladat: B.4992 Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 2020/május, 286 - 287. oldal  PDF  |  MathML 
Témakör(ök): Feladat, Számtani sorozat, Számhalmazok
Hivatkozás(ok):Feladatok: 2018/december: B.4992

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.

Azt fogjuk belátni, hogy az n≥8 esetekben bármelyik kiinduló színezés esetén elérhető, hogy a számok pirosak legyenek, viszont n≤7 esetén mindig megadható olyan alaphelyzet is, amikor ez nem érhető el.
Először azt mutatjuk meg, hogy nyolc szomszédos szám esetén mindig megadható olyan néhány lépésből álló színezési sorozat, amely végül a nyolc szám közül egynek a színét megváltoztatja, a többit pedig változatlanul hagyja.
Az alábbi táblázatban a felső sorban elhelyezett számok jelentsék a nyolc szám közül annak a sorszámát, amelynek a színét kizárólagosan meg akarjuk változtatni, míg az alatta elhelyezkedő sorozatok azt, hogy ez a változtatás (csak ennek a nyolc számnak a felhasználásával) milyen lépésekkel érhető el.

 
123456784, 5, 65, 6, 74, 5, 61, 2, 32, 3, 41, 2, 31, 2, 32, 3, 4  5, 6, 76, 7, 81, 4, 72, 3, 43, 4, 51, 4, 72, 3, 43, 4, 5  1, 4, 72, 5, 86, 7, 84, 5, 65, 6, 73, 4, 51, 4, 72, 5, 82, 5, 85, 6, 76, 7, 82, 5, 81, 2, 31, 4, 72, 5, 86, 7, 8
 

Tehát ha n≥8, akkor bármelyik kék számra tekinthetünk egy szomszédos nyolcast és azzal ezt a számot a fenti sorozatok valamelyikével pirosra színezhetjük.
Meg kell még mutatni, hogy n≤7-re mindig van olyan kiinduló helyzet, amelyből nem színezhető a megengedett lépésekkel midegyik szám pirosra.
Ha n=1 vagy n=2, és nem csak piros színű számaink vannak, akkor nem tudjuk a színezésüket megváltoztatni.
Legyen ezek után 3≤n≤7 és induljunk ki abból a helyzetből, amikor a 2 kék, a többi szám pedig piros színű. Nevezzük a színezés szempontjából fontos számoknak a 2, 3, 5, 6 közül azokat, amelyek nem nagyobbak, mint az aktuális n. A következő táblázatban a fontos számokat félkövéren szedtük.
 
1234567
 

n=7-ig a lehetséges háromtagú számtani sorozatok:
{1,2,3},{2,3,4},{3,4,5},{4,5,6},{5,6,7},{1,3,5},{2,4,6},{3,5,7},{1,4,7}.
Természetesen, ha n<7, akkor ezek közül azokat el kell hagyni, amelyekben az n-nél nagyobb szám is előfordul.
A bizonyítás szampontjából azonban ez nem jelent problémát, mert sorra ellenőrizhetően mindegyik ilyen sorozatban a ,,fontos számok'' közül pontosan nulla vagy kettő szerepel, azaz ezen lépések egyike sem fogja a színezésben szereplő kék számok paritását megváltoztatni. Induláskor csak egy szám, nevezetesen a 2 volt kék, így nem érhető el, hogy mindegyik szám piros legyen.
 

 Terjék András József (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 9. évf.)
 dolgozata alapján