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 file
Témakör(ök): Tizes alapú számrendszer, Feladat
Hivatkozás(ok):Feladatok: 1981/május: F.2316

Egy, a tízes számrendszerben felírt számot univerzálisnak nevezünk, ha tetszőleges csupa különböző számjegyből álló számot megkaphatunk belőle úgy, hogy a számból bizonyos számjegyeket törlünk. Készítsünk legfeljebb 100 jegyű univerzális számot. Mutassuk meg, hogy az univerzális számok legalább 55 számjegyet tartalmaznak.

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ű A szám számjegyei kijelölhetőek A-beli sorrendjükben. Valóban, A első számjegyét biztosan megtaláljuk az általunk felírt B szám első tíz jegye között, hiszen ott az összes számjegyet felsoroltuk. Majd A második, harmadik, általában a k-adik számjegyét ugyancsak kijelölhetjük a számunk második, harmadik, k-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 k értékét egytől A jegyeinek a számáig növeljük, közben A összes számjegyét kijelöljük, mégpedig pontosan abban a sorrendben, ahogy A-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 B szám univerzális.
Legyen most B tetszőleges univerzális szám. Mivel B univerzális, minden számjegynek elő kell fordulnia benne. Vegyük sorra B 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 s1-gyel, és legyen ez B-nek mondjuk j1-edik számjegye. Mivel B első (j1-1) számjegye között minden 0-tól és s1-től különböző számjegy legalább egyszer előfordul, j19. Menjünk tovább B számjegyein, addig, amíg minden s1-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 s2-vel, és legyen ez B-nek j2-edik számjegye. Általában, ha már kijelöltük B j1-edik, j2-edik, ..., jk-adik számjegyét, és ezek értéke rendre s1, s2, ..., sk volt, akkor B(jk+1)-edik számjegyén kezdve menjünk el B számjegyein addig, amíg minden, az s1, s2, ..., sk számjegyektől különböző számjegy legalább egyszer elő nem fordul. Legyen sk+i az utoljára elénk kerülő számjegy, és legyen ez B-nek jk+1-edik számjegye.
Az eljárásunk egyszer biztosan véget ér, hiszen a különböző számjegyek száma is és B számjegyeinek a száma is véges. Legyen a kapott számjegyek száma m, akkor egyrészt m10, másrészt tetszőleges 1<km mellett jk>jk-1+(10-k), hiszen jk-1 után jk-ig (10-k)-nál többféle számjegynek kell állnia. Ha m=10, ebből j19 alapján j1054 következik, hiszen

j10=j1+(j2-j1)+...+(j10-j9)9+9+8+7+6+5+4+3+2+1=54.

Megmutatjuk, hogy ha m=10 és j10=54, vagy ha m<10, akkor B 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 s1 egyáltalán nem fordul elő B-ben, csak a j1-edik helyen. Ha tehát A első számjegyének B(j1-1)-edik számjegyét választjuk, majd A második számjegyének tetszőleges, ettől és s1-től különböző számjegyet választunk, és végül a harmadik számjegyének az s1-et választjuk, akkor A nyilván nem állítható elő B-ből néhány számjegy elhagyásával.
Ha tehát m=10, és B univerzális, akkor j10>54, vagyis B-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 m<10, akkor B nem lehet univerzális. Legyenek ekkor ugyanis s1, s2, ..., sm a B-ből a fenti eljárással előállított számjegyek, és legyen sm+1, ..., s10 a tőlük különböző többi szám jegy tetszőleges sorrendben. Legyenek A számjegyei az s1, ..., s10 számjegyek ebben a sorrendben. Megmutatjuk, hogy A nem állítható elő B-ből.
Tegyük fel állításunkkal ellentétben, hogy A számjegyei a kívánt sorrendben megtalálhatóak B-ben, és legyen mondjuk si a Bbi-edik számjegye. Mivel s1 a B-ben először a j1-edik helyen fordul elő, b1j1. Belátjuk, hogy tetszőleges km mellett bkjk. Ha ugyanis ez nem volna így, válasszuk k-nak azt a legkisebb indexet, amelyre bk<jk. Akkor bk-1jk-1, tehát A elképzelt előállításában sk-1-et vagy Bjk-1-edik jegyeként, vagy azután jelöljük ki. Akkor viszont nem találhatjuk meg B-ben ezután, de még jk előtt sk-t, hiszen a konstrukciónk szerint jk-1 után B első sk-val egyenlő számjegye a jk-adik volt. Tehát bmjm, de m definíciója szerint B-ben a jm-edik számjegy után nem fordulhat elő az összes, az s1, s2, ..., sm 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:
*7890*8798*0789#7890*8798*0789#7890987*
Itt a * az 123456, # pedig a 65432123456 számjegysorozatot jelöli. Nem tudjuk, hány jegyből áll a legkisebb univerzális szám.