|
Feladat: |
F.2316 |
Korcsoport: 18- |
Nehézségi fok: nehéz |
Megoldó(k): |
Ákosfai Z. , Alberti G. , Borsó Zs. , Böröczky K. , Böröczky Lilla , Csere K. , Csörgő T. , Dobrosi D. , Erdős 228 L. , Feledi Gy. , Fóris Z. , Halász P. , Hetyei G. , Hideg Sz. , Holbok I. , Károlyi Gy. , Kerényi I. , Király Z. , Kovács 567 Judit , Litkei F. , Magyar Á. , Magyar Cs. , Megyesi G. , Mihálykó Cs. , Mohay T. , Poór L. , Porkoláb Z. , Sigray I. , Simek R. , Szabó E. , Szállási Z. , Terenyi Z. , Törőcsik J. , Weisz F. |
Füzet: |
1982/január,
17 - 18. oldal |
PDF | MathML |
Témakör(ök): |
Tizes alapú számrendszer, Feladat |
Hivatkozás(ok): | Feladatok: 1981/május: F.2316 |
|
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. Írjuk fel csökkenő sorrendben egymás után a tízes számrendszer tíz számjegyét, és a kapott együttest írjuk le tízszer egymás után. Száz jegyű számot kapunk, amelyben tetszőleges, legfeljebb tíz jegyű szám számjegyei kijelölhetőek -beli sorrendjükben. Valóban, első számjegyét biztosan megtaláljuk az általunk felírt szám első tíz jegye között, hiszen ott az összes számjegyet felsoroltuk. Majd második, harmadik, általában a -adik számjegyét ugyancsak kijelölhetjük a számunk második, harmadik, -adik tíz számjegyből álló blokkjában, hiszen ezek mindegyikében külön‐külön minden számjegy megtalálható. Így ha értékét egytől jegyeinek a számáig növeljük, közben összes számjegyét kijelöljük, mégpedig pontosan abban a sorrendben, ahogy -ban követik egymást. Mivel egy csupa különböző számjegyből álló szám legfeljebb tíz jegyű, ezzel beláttuk, hogy az általunk felírt szám univerzális. Legyen most tetszőleges univerzális szám. Mivel univerzális, minden számjegynek elő kell fordulnia benne. Vegyük sorra számjegyeit az első számjegyen kezdve mindaddig, amíg minden 0-tól különböző számjegy legalább egyszer elő nem fordul köztük. Jelöljük a legutoljára elénk kerülő számjegyet -gyel, és legyen ez -nek mondjuk -edik számjegye. Mivel első számjegye között minden 0-tól és -től különböző számjegy legalább egyszer előfordul, . Menjünk tovább számjegyein, addig, amíg minden -től különböző számjegy legalább egyszer elő nem fordul. Jelöljük az utoljára elénk kerülő számjegyet -vel, és legyen ez -nek -edik számjegye. Általában, ha már kijelöltük -edik, -edik, , -adik számjegyét, és ezek értéke rendre , , , volt, akkor -edik számjegyén kezdve menjünk el számjegyein addig, amíg minden, az , , , számjegyektől különböző számjegy legalább egyszer elő nem fordul. Legyen az utoljára elénk kerülő számjegy, és legyen ez -nek -edik számjegye. Az eljárásunk egyszer biztosan véget ér, hiszen a különböző számjegyek száma is és számjegyeinek a száma is véges. Legyen a kapott számjegyek száma , akkor egyrészt , másrészt tetszőleges mellett , hiszen után -ig -nál többféle számjegynek kell állnia. Ha , ebből alapján következik, hiszen | |
Megmutatjuk, hogy ha és , vagy ha , akkor nem lehet univerzális. Az első esetben ugyanis a pontos egyenlőségek miatt a fenti konstrukcióval előállított blokkokban minden keresett számjegy pontosan egyszer fordul elő, és amit nem keresünk, az nem is fordulhat elő. Így például egyáltalán nem fordul elő -ben, csak a -edik helyen. Ha tehát első számjegyének -edik számjegyét választjuk, majd második számjegyének tetszőleges, ettől és -től különböző számjegyet választunk, és végül a harmadik számjegyének az -et választjuk, akkor nyilván nem állítható elő -ből néhány számjegy elhagyásával. Ha tehát , és univerzális, akkor , vagyis -nek valóban legalább 55 számjegye van. Így készen vagyunk a feladat állításának a bizonyításával, és belátjuk, hogy ha , akkor nem lehet univerzális. Legyenek ekkor ugyanis , , , a -ből a fenti eljárással előállított számjegyek, és legyen , , a tőlük különböző többi szám jegy tetszőleges sorrendben. Legyenek számjegyei az , , számjegyek ebben a sorrendben. Megmutatjuk, hogy nem állítható elő -ből. Tegyük fel állításunkkal ellentétben, hogy számjegyei a kívánt sorrendben megtalálhatóak -ben, és legyen mondjuk a -edik számjegye. Mivel a -ben először a -edik helyen fordul elő, . Belátjuk, hogy tetszőleges mellett . Ha ugyanis ez nem volna így, válasszuk -nak azt a legkisebb indexet, amelyre . Akkor , tehát elképzelt előállításában -et vagy -edik jegyeként, vagy azután jelöljük ki. Akkor viszont nem találhatjuk meg -ben ezután, de még előtt -t, hiszen a konstrukciónk szerint után első -val egyenlő számjegye a -adik volt. Tehát , de definíciója szerint -ben a -edik számjegy után nem fordulhat elő az összes, az , , , számjegyektől különböző számjegy. Megjegyzés. Belátható az is, hogy egy univerzális szám legalább 69 jegyű, és hogy az alábbi 89 jegyű szám univerzális: | | Itt a az 123456, pedig a 65432123456 számjegysorozatot jelöli. Nem tudjuk, hány jegyből áll a legkisebb univerzális szám.
|
|