Feladat: F.2599 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Benczúr András ,  Cynolter G. ,  Lipták László 
Füzet: 1987/április, 156 - 157. oldal  PDF  |  MathML 
Témakör(ök): Egyéb szinezési problémák, Kombinatorikai leszámolási problémák, Konstruktív megoldási módszer, Számtani sorozat, Feladat
Hivatkozás(ok):Feladatok: 1986/október: F.2599

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. A színezést nem adjuk meg, csak létezését bizonyítjuk.
1-től 1986-ig 1986 természetes szám van, ezeket 21986 félképpen lehet két színnel kiszínezni.
Most felső becslést keresünk a "rossz'' színezések számára, tehát azokéra, amelyekben van 18 tagú, "egyszínű'' számtani sorozat. Az ilyen színezéseket úgy kapjuk, hogy kiválasztunk egy 18 tagú számtani sorozatot, ezt a két szín valamelyikével egyszínűre színezzük, majd a többi 1968 számot tetszőlegesen kiszínezzük.
Így minden "rossz'' színezést megkapunk, némelyiket (p1. a "csupa kéket'') többször is. Ha S-sel jelöljük a 18 tagú számtani sorozatok számát, akkor a rossz színezések száma tehát kisebb, mint 2S⋅21986. Ha belátjuk, hogy ez a szám kisebb az összes színezések számánál, vagyis

S<217,
akkor készen vagyunk.
Számoljuk ki S-et! Egy számtani sorozatot egyértelműen meghatároz legkisebb eleme: a1 és különbsége: d(≧1). Minthogy 18. tagja, a18=a1+17d, szintén nem lehet nagyobb 1986-nál, ezért a1≦1986-17d. Rögzített d-re tehát a1-et ennyiféleképpen választhatjuk meg, másrészt nyilván d≦[198617]=116, tehát

S=∑d=1116(1986-17d)=116⋅1986-17∑d=1116d==116⋅1986-17⋅116⋅1172=115014<217,


amit bizonyítani akartunk.
 

II. megoldás. Színezzük ki a számokat a következő módon: legyen piros minden 7-tel és 17-tel nem osztható szám, valamint minden 7⋅17-tel osztható szám, és legyen kék az összes többi. Belátjuk, hogy ekkor a számok közt nincs egyszínű 18 tagú számtani sorozat.
A következő segédtételt használjuk: ha p prím és nem osztója d-nek,. akkor k, k+d, k+2d, ..., k+(p-1)d ún. "teljes maradékrendszer mod p'', azaz sorra osztva őket p-vel, a maradékok (valamilyen sorrendben) a 0, 1, 2, ..., (p-1) számok lesznek. (Minden maradékot pontosan egyszer kapunk meg.) Két ilyen alakú szám, mondjuk k+id, k+jd (i<j) maradéka ugyanis csak úgy lehetne egyenlő, ha különbségük, (j-i)d osztható volna p-vel. De d nem osztható p-vel a feltevés szerint, és 0<j-i≦j<p miattj-i sem osztható p-vel. Minthogy pedig p prim, (j-i)d sem lehet osztható p-vel. Ezzel a segédtételt igazoltuk.
Legyen most 1≦a1<a2...<a18≦1986 egy számtani sorozat. Ennek különbsége, d<7⋅17=119, mert különben a18=a1+17d≧172⋅7=2023 volna, ami nem lehet. d tehát nem lehet egyszerre osztható 7-tel és 17-tel (mert 7 és 17 relatív prímek).
Ha d nem osztható sem 7-tel, sem 17-tel, akkor az a1, a2=a1+d, a3=a1+2d, a4=a1+3d, ..., a7=a1+6d számok valamelyike a segédtétel szerint osztható 7-tel, ugyanígy az a8, a9=a8+d, a10=a8+2d,...a14=a8+6d számok egyike is. Van tehát két 7-tel osztható tagja a sorozatnak. Másrészt a segédtétel szerint e számok közül legföljebb egy lehet osztható 17-tel, így a sorozat 7-tel osztható tagjai között biztosan van olyan, amelyik nem osztható 17-tel, és így kék. Másfelől a sorozat három szomszédos eleme közül legalább kettő nem osztható 7-tel, így ezek egyike 17-tel sem osztható, és így piros.
Ha tehát d sem 7-tel, sem pedig 17-tel nem osztható, akkor bármely d differenciájú, 18 tagú ‐ illetve már 14 tagú ‐ számtani sorozatnak van piros és kék eleme is.
Hátravan még az az eset, ha d a 7 és a 17 közül pontosan az egyiknek többszöröse. Jelöljük ezt p-vel, a másik számot pedig q-val. Ekkor a sorozatnak vagy minden tagja osztható p-vel, vagy egyik sem. A segédtétel szerint viszont az első q darab elem között van q-val osztható és q-val nem osztható is, és ezek színe biztosan különböző.
Ezzel a bizonyítást befejeztük.
 


Megjegyzések. 1. A feladat megoldása megjelent a TIT "Matematikai versenyek, 1986'' című kiadványában is. Sajnos igen kevés megoldónk tüntette fel dolgozatának ezt a forrását, pedig ezzel sok időt takaríthatott volna meg magának és a javítónak egyaránt. Ugyanis tökéletes megoldásnak fogadtuk el azt is, ha valaki semmi mást nem írt le, mint hogy hol található meg a feladat megoldása,
Ugyanakkor, bár a kiadványban két megoldás található, második megoldásért csak olyan versenyzőknek adtunk többletpontokat, akiknek legalább az egyik megoldása láthatóan önálló munka eredménye volt. A többletpontokat ugyanis a feladattal kapcsolatos többletmunka jutalmazására szeretnénk fenntartani.
2. Két versenyzőnk más, a feladat követelményeinek megfelelő színezést adott meg. Durham Michael(Szeged, Ságvári E. Gyak. Gimn., III. o. t.) konstrukciója: az első 289 szám kék, kivéve a 17k+1 alakúakat és 289-18=271-et; a következő 16⋅17=272 szám piros, kivéve a 17k+1 alakúakat és 289+272-18=543-t stb. ‐ Grallert Krisztina (Miskolc, Földes F. Gimn., IV. o. t.) az első számot pirosra színezte, a következő 2-t kékre, a következő 3-at pirosra s i. t., majd a 17 szomszédos piros szám után következő 16-ot kékre, ezután 15-öt pirosra, ...,1-et pirosra, 1-et kékre ... és így tovább. A színezések helyességét meglehetősen hosszadalmas volna igazolni, nem is próbálta meg egyik versenyző sem, mi számítógéppel láttuk be. Indokolás hiányában természetesen nem adhattunk maximális pontszámot ezekre a megoldásokra.
M. B.

3. Megmutatható, hogy ha p prímszám ‐ és a 17 az ‐, akkor az első p⋅2p darab pozitív egész még kiszínezhető két színnel úgy, hogy ne forduljon elő 18-tagú, egyszínű számtani sorozat. Esetünkben ez azt jelenti, hogy 1986 helyett még az első 2 228 224 pozitív egészre is igaz a feladat állítása.