Feladat: 1982. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Surányi János 
Füzet: 1983/február, 57 - 60. oldal  PDF file
Témakör(ök): Egyéb szinezési problémák, Egyenlőtlenségek, Oszthatóság, Természetes számok, Számtani sorozat, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1983/február: 1982. évi Kürschák matematikaverseny 3. feladata

Az egész számok halmazát kiszíneztük száz színnel úgy, hogy mind a száz színt felhasználtuk és teljesül a következő: bárhogyan is választunk két [a,b] és [c,d] egyforma hosszú, egész végpontú intervallumot, ha a színe ugyanaz, mint c színe és b színe ugyanaz, mint d színe, akkor [a,b] és [c,d] teljes színezése megegyezik (azaz 0xb-a,x egész esetén a+x és c+x színe azonos). Bizonyítsuk be, hogy -1982 és 1982 színe különböző.

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 feladat feltételeiből következik, hogy az egész számok színezése 100 hosszúságú periódusokban ismétlődik az egész számegyenes mentén, és egy perióduson belül minden szín előfordul.

 

Ha ezt belátjuk, ebből következik, hogy két szám színe akkor és csak akkor egyezik meg, ha különbségük a 100 többszöröse. -1982 és 1982 tehát különböző színű, mert különbségük 3964, nem osztható 100-zal.
 

A színezés periodikus voltának belátásához előbb belátjuk, hogy
 

a) van olyan A és d1 természetes szám, amelyekre minden A-nál nagyobb szám színe megegyezik a d1-gyel nagyobb száméval,
b) hasonlóan van olyan B és d2 természetes szám, hogy minden -B-nél kisebb egész színe megegyezik a d2-vel kisebb száméval,
c) ezután belátjuk, hogy a két periodikus részszínezés az egész számegyenes egyetlen periodikus színezésének a része.
 

Az a) és b) részállítás bizonyítása ugyanazon gondolatmenettel történhet, elég tehát az a) állítás bizonyítását részletezni.
Nevezzük alapszámköznek azokat a számközöket, amelyeknek a kezdő és végső száma ugyanolyan színű és más egyező színű számpár nincs a számközben.
Egy alapszámköz legfeljebb 101 egész számot tartalmazhat, mert 100 színünk van, s így bármelyik számtól elindulva legkésőbb a 101-edik színe kell, hogy megegyezzék az előzők valamelyikével. Minden 101 egészet tartalmazó számköz tartalmaz is alapszámközt, hiszen az első számtól elindulva addig megyünk, míg először nem érünk a számköz egy korábbi számával egyező színű számához; ekkor ez a két egyező színű szám alapszámközt fog közre.
A természetes számok közt végtelen sok alapszámköz van, hiszen pl. a [101n, 101n+100] (n=0,1,2,...) számközök 101‐101 egészből állnak, s így mindegyik tartalmaz alapszámközt. Mivel egy alapszámköz legalább 2 és legfeljebb 101 egészet tartalmaz, kell olyan d1 egésznek lennie, hogy végtelen sok alapszámköz d1+1 egészet (d1 különböző színűt) tartalmaz. Legyenek [ai,ai+d1] (i=1,2,... és ai0), d1+1 pozitív egészből álló alapszámközök. Megmutatjuk, hogy minden A=a1-nél nagyobb n-re n és n+d1 színe megegyezik.
Legyen n>A. Mivel az ai nem-negatív egészek sorozata végtelen, választhatjuk j-t úgy, hogy ajn teljesüljön. Az alapszámköz definíciójából következik, hogy az [A, aj] és az [A+d1, aj+d1] számközök kezdő számai is egyező színűek, a záró egészek is. Világos, hogy a két számköz ugyanannyi egészből áll és j választása szerint n az első számközhöz tartozik. A feladatnak a színezésre vonatkozó feltétele szerint ekkor következik, hogy n+d1 színe megegyezik n színével. Ezzel az a) állítást igazoltuk. Meggondolásainkat a negatív egészekből álló alapszámközökre alkalmazva kapjuk a b) állítás igazolását.
 

Az a), ill. b) állítás helyességéből természetesen az is következik, hogy ha k pozitív egész és n>A, ill. m<-B, akkor n és n+kd1, ill. m és m-kd2 egyező színű.
A két periodikus rész kapcsolatának tisztázásához jegyezzük meg először is, hogy mind a két rész periodikus pl. d1d2 szerint, hiszen csak a fenti állításban k helyett az első esetben d2-t, a másodikban d1-et kell írni. Megmutatjuk, hogy ez igaz az egész számegyenesre is.
Legyen ugyanis r tetszés szerinti egész, u<-B, v>A, továbbá urv. Ekkor u-d1d2 és u, ill. v és v+d1d2 egyező színűek, így az [u-d1d2, v] és [u, v+d1d2] kielégítik a feladatban szereplő feltételeket, és az első tartalmazza r-et, így következik, hogy r és r+d1d2 ugyanolyan színű.
Azt kell még belátnunk, hogy a legrövidebb periódushossz 100. Itt használjuk ki azt az eddig még nem értékesített tényt, hogy egy egyik végpontjától megfosztott alapszámköz csupa különböző színű pontból áll. Eszerint az A-nál nagyobb egészek d1 színnel vannak színezve, nem kevesebbel, mert tartalmaznak d1+1 elemből álló alapszámközt, de nem is többel, hiszen színezésük d1 hosszúságú egyező periódusokból tevődik össze.
Ekkor azonban az egész számegyenes is d1 színnel van színezve, mert tetszés szerinti r egészhez van olyan s pozitív egész, hogy r+sd1d2>A. Ekkor r és r+sd1d2 színe egyező, de az utóbbi szám színe csak az A-nál nagyobb számoknál használt d1 szín valamelyike lehet. Az összes egész tehát d1 színnel van színezve, vagyis d1=100. Továbbá minden d1d2 hosszúságú periódus előfordul az A-nál nagyobb számok közt is, tehát d2 darab egyező színezésű részperiódusból tevődik össze. Az összes egész színezése tehát d1=100 különböző színű, egymás utáni egész színezésének periodikus ismétlésével származtatható. Mint láttuk, ebből a feladat állítása is következik.
 

Megjegyzések. 1. Nyilván nincs a 100-nak kitüntetett szerepe (azon kívül, hogy nem osztója 3964-nek). Ha 100 helyett k színt használunk fel a feladatban kívánt feltételeket kielégítve, akkor ezt csak úgy tehetjük, hogy k szomszédos pont különböző színű legyen és ez a színezés periodikusan ismétlődjék.
 

2. Ha csak a feladat állításának bizonyítására törekszünk, ehhez eljuthatunk anélkül, hogy az egész számegyenes színezését tisztáznánk.
 

II. Megoldás. Legyen M 1982-nél nagyobb természetes szám, továbbá akkora, hogy a [-M, M] számköz egészeinek színezésében mind a 100 szín előforduljon. Az M-nél nagyobb számok színezésében legalább egy S1 színnek végtelen sokszor elő kell fordulnia. Legyenek az S1 színű számok
M+a1<M+a2<...
A
-M-a1,-M-a2,,...,-M-a101
számok között kell legalább két egyszínűnek lennie, mondjuk -M-aj és -M-aiS2 színű (i<j). Ekkor a
[-M-aj,M+ai]=Iés[-M-ai,M+aj]=J
számközök kezdő számai S2 zínűek, a végsők S1 színűek és egyaránt 2M+ai+aj+1 egészet tartalmaznak. A feladat feltételei szerint így színezésük megegyezik.
A két számköz részben átfedi egymást, [-M-ai, M+ai] mindkettőhöz hozzátartozik. A csak I-hez tartozó
-M-aj,...,-M-ai-1(1)
számok számát jelöljük d-vel (d=aj-ai). Mivel I és J ugyanúgy van színezve, így speciálisan
[-M-aj,-M-ai]=I1és[-M-ai,-M-ai+d]=J1
részeik színezése is megegyezik.
Az (1) számok közt balról az első két egyező színű legyen, ha van
b1=-M-aj+b,ésb1+d1,
színük legyen S3. Ha az (1) számok mind különböző színűek, akkor d1=d, b1=-M-aj, b1+d1=b1+d=-M-ai+d=-M-aj, és S3=S2. Ez azt jelenti, hogy
-M-aj,-M-aj+1,...,-M-aj+b,-M-aj+b+1,...,-M-aj+b+d1-1
számok mind különböző színűek. Itt b=0 is lehet, ez esetben csak az utolsó d1 számú számról van szó; egyébként ekkor S3=S2, I1 és J1 egyező színezése folytán
b2=b1+d,ésb2+d1
színe is S3. Ekkor viszont a
[b1,b2]=I2,[b1+d1,b2+d1]=J2
számközökre is teljesülnek a feladatban szereplő feltételek, tehát ezeknek a számközöknek is megegyezik a színezése.
Belátjuk, hogy d1 osztója d-nek és I1 színezése periodikus d1 periódussal. Ez nyilvánvaló, ha d1=d, s így b1=-Maj, b1+d1=-M-ai. Feltehetjük tehát, hogy d1<d. Ekkor b1+d1 benne van a [b1, b2] számközben. Így I2 és J2-re nyert színezési feltétel szerint [b1, b1+d1] és [b1+d1, b1+2d1] ugyanúgy van színezve.
Ha még b1+2d1 is benne van I1-ben, akkor I2 és J2 színezésének egyezése folytán az utóbbi számköz és a hozzá csatlakozó [b1+2d1, b1+3d1] színezése is megegyezik. Legyen k1 az az egész, amelyre b1+(k1-1)d1-M-ai<b1+k1d1, akkor a gondolat ismételt alkalmazásával azt kapjuk, hogy a
[b1,b1+d1],[b1+d1,b1+2d1],...,[b1+(k1-1)d1,b1+k1d1]
számközök színezése mind megegyezik, és pedig az utolsó számtól eltekintve csupa különböző színű számból áll mindegyik.
Az utolsó számköz részben a J1 elejét fedi. Ez csak úgy lehet, hogy b=0, mert különben az I1-gyel egyező színezésű J1 a [b1, b1+d1]-ben, s így [b1+ +(k1-1)d1, b1+k1d1]-ben sem szereplő színű számokkal kezdődnék. Ez azt is jelenti,hogy b1=-M-aj, s így S3=S2. De nem lehetséges az sem, hogy b1+(k1-1)d1<-M-ai legyen, mert ekkor a [b1+(k1-1)d1,b1+k1d1] számköz belsejében is volna egy S2 színű, tehát a szélső számokkal egyező színű szám.
Ezzel beláttuk, hogy az I1 utolsó számának elhagyásával keletkező számköz egymással egyező színezésű, d1 különböző színű számból álló számközökből tevődik össze.
Térjünk végül vissza az egyező színezésű és egymást részben átfedő I és J számközhöz. Láttuk, hogy
[-M-aj,-M-ai], és a [-M-ai,-M-ai+d]
számközök színezése megegyezik. Ha az utóbbi számköz még teljesen I-hez tartozik, akkor [-M-ai+d,-M-ai+2d] színezése megegyezik az előbbi két számközével. Ha k az az egész, amelyre
-M-aj+(k-1)d-M-ai<-M-aj+kd,
akkor a
,[-M-ai,-M-ai+d],...[-M-ai+(k-1)d,-M-ai+kd]


egymáshoz csatlakozó számközök ugyanúgy vannak színezve és lefedik a [-M-aj,M+ai] számközt, tehát mindenesetre a [-M,M] számközt is. Ezek színezése tehát előző megállapításaink szerint d1 szerint periodikus, és egy periódus d1 különböző színű számból áll. Mivel [-M,M]-ben mind a 100 szín előfordul, így d1=100, és két szám színe pontosan akkor egyezik meg, ha különbségük osztható 100-zal. -1982 és 1982 tehát különböző színű.
 

Megjegyzés. Látszólag itt csak egy véges számközről bizonyítottuk be, hogy színezése periodikus 100 periódussal, valójában azonban ez a bizonyítás azt is adja, hogy az egész számegyenes periodikusan van kiszínezve 100 hosszúságú periódussal. Legyen ugyanis n tetszés szerinti egész szám és M akkora, hogy a [-M,M] számköz tartalmazza n-et, n+100-at és színezésében mind a 100 szín előfordul. Az elmondott bizonyítás ekkor is azt adja, hogy a [-M,M] számköz periodikusan van színezve 100 hosszúságú, különböző színű számokból álló periódussal, tehát n és n+100 egyező színű, n, n+1,...,n+99 viszont különböző színű számok.