| 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 és egyforma hosszú, egész végpontú intervallumot, ha színe ugyanaz, mint színe és színe ugyanaz, mint színe, akkor és teljes színezése megegyezik (azaz egész esetén és színe azonos). Bizonyítsuk be, hogy és 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. é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 és természetes szám, amelyekre minden -nál nagyobb szám színe megegyezik a -gyel nagyobb száméval, b) hasonlóan van olyan és természetes szám, hogy minden -nél kisebb egész színe megegyezik a -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 [, ] 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 egésznek lennie, hogy végtelen sok alapszámköz egészet ( különböző színűt) tartalmaz. Legyenek ( és ), pozitív egészből álló alapszámközök. Megmutatjuk, hogy minden -nél nagyobb -re és színe megegyezik. Legyen . Mivel az nem-negatív egészek sorozata végtelen, választhatjuk -t úgy, hogy teljesüljön. Az alapszámköz definíciójából következik, hogy az [, ] és az [, ] 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 választása szerint az első számközhöz tartozik. A feladatnak a színezésre vonatkozó feltétele szerint ekkor következik, hogy színe megegyezik 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 pozitív egész és , ill. , akkor és , ill. és 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. szerint, hiszen csak a fenti állításban helyett az első esetben -t, a másodikban -et kell írni. Megmutatjuk, hogy ez igaz az egész számegyenesre is. Legyen ugyanis tetszés szerinti egész, , , továbbá . Ekkor és , ill. és egyező színűek, így az [, ] és [, ] kielégítik a feladatban szereplő feltételeket, és az első tartalmazza -et, így következik, hogy és 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 -nál nagyobb egészek színnel vannak színezve, nem kevesebbel, mert tartalmaznak elemből álló alapszámközt, de nem is többel, hiszen színezésük hosszúságú egyező periódusokból tevődik össze. Ekkor azonban az egész számegyenes is színnel van színezve, mert tetszés szerinti egészhez van olyan pozitív egész, hogy . Ekkor és színe egyező, de az utóbbi szám színe csak az -nál nagyobb számoknál használt szín valamelyike lehet. Az összes egész tehát színnel van színezve, vagyis . Továbbá minden hosszúságú periódus előfordul az -nál nagyobb számok közt is, tehát darab egyező színezésű részperiódusból tevődik össze. Az összes egész színezése tehát 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 színt használunk fel a feladatban kívánt feltételeket kielégítve, akkor ezt csak úgy tehetjük, hogy 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 1982-nél nagyobb természetes szám, továbbá akkora, hogy a [, ] számköz egészeinek színezésében mind a 100 szín előforduljon. Az -nél nagyobb számok színezésében legalább egy színnek végtelen sokszor elő kell fordulnia. Legyenek az színű számok A két számköz részben átfedi egymást, [, ] mindkettőhöz hozzátartozik. A csak -hez tartozó
Az (1) számok közt balról az első két egyező színű legyen, ha van Belátjuk, hogy osztója -nek és színezése periodikus periódussal. Ez nyilvánvaló, ha , s így , . Feltehetjük tehát, hogy . Ekkor benne van a [, ] számközben. Így és -re nyert színezési feltétel szerint [, ] és [, ] ugyanúgy van színezve. Ha még is benne van -ben, akkor és színezésének egyezése folytán az utóbbi számköz és a hozzá csatlakozó [, ] színezése is megegyezik. Legyen az az egész, amelyre , akkor a gondolat ismételt alkalmazásával azt kapjuk, hogy a Az utolsó számköz részben a elejét fedi. Ez csak úgy lehet, hogy , mert különben az -gyel egyező színezésű a [, ]-ben, s így [ , ]-ben sem szereplő színű számokkal kezdődnék. Ez azt is jelenti,hogy , s így . De nem lehetséges az sem, hogy legyen, mert ekkor a számköz belsejében is volna egy színű, tehát a szélső számokkal egyező színű szám. Ezzel beláttuk, hogy az utolsó számának elhagyásával keletkező számköz egymással egyező színezésű, 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ő és számközhöz. Láttuk, hogy egymáshoz csatlakozó számközök ugyanúgy vannak színezve és lefedik a számközt, tehát mindenesetre a számközt is. Ezek színezése tehát előző megállapításaink szerint szerint periodikus, és egy periódus különböző színű számból áll. Mivel -ben mind a 100 szín előfordul, így , és két szám színe pontosan akkor egyezik meg, ha különbségük osztható 100-zal. é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 tetszés szerinti egész szám és akkora, hogy a számköz tartalmazza -et, -at és színezésében mind a 100 szín előfordul. Az elmondott bizonyítás ekkor is azt adja, hogy a 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 és egyező színű, , viszont különböző színű számok. |