Kezdőlap


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ű $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 $s_{1}$ -gyel, és legyen ez $B$ -nek mondjuk $j_{1}$ -edik számjegye. Mivel $B$ első $(j_{1} - 1)$ számjegye között minden 0-tól és $s_{1}$ -től különböző számjegy legalább egyszer előfordul, $j_{1} \geq 9$ . Menjünk tovább $B$ számjegyein, addig, amíg minden $s_{1}$ -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 $s_{2}$ -vel, és legyen ez $B$ -nek $j_{2}$ -edik számjegye. Általában, ha már kijelöltük $B$ $j_{1}$ -edik, $j_{2}$ -edik, $...$ , $j_{k}$ -adik számjegyét, és ezek értéke rendre $s_{1}$ , $s_{2}$ , $...$ , $s_{k}$ volt, akkor $B (j_{k} + 1)$ -edik számjegyén kezdve menjünk el $B$ számjegyein addig, amíg minden, az $s_{1}$ , $s_{2}$ , $...$ , $s_{k}$ számjegyektől különböző számjegy legalább egyszer elő nem fordul. Legyen $s_{k + i}$ az utoljára elénk kerülő számjegy, és legyen ez $B$ -nek $j_{k + 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 $m \leq 10$ , másrészt tetszőleges $1 < k \leq m$ mellett $j_{k} > j_{k - 1} + (10 - k)$ , hiszen $j_{k - 1}$ után $j_{k}$ -ig $(10 - k)$ -nál többféle számjegynek kell állnia. Ha $m = 10$ , ebből $j_{1} \geq 9$ alapján $j_{10} \geq 54$ következik, hiszen

\begin{matrix} j_{10} = j_{1} + (j_{2} - j_{1}) + ... + (j_{10} - j_{9}) \geq 9 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 54. \end{matrix}

Megmutatjuk, hogy ha

m = 10

és

j_{10} = 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

s_{1}

egyáltalán nem fordul elő

B

-ben, csak a

j_{1}

-edik helyen. Ha tehát

A

első számjegyének

B (j_{1} - 1)

-edik számjegyét választjuk, majd

A

második számjegyének tetszőleges, ettől és

s_{1}

-től különböző számjegyet választunk, és végül a harmadik számjegyének az

s_{1}

-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

j_{10} > 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

s_{1}

s_{2}

...

s_{m}

B

-ből a fenti eljárással előállított számjegyek, és legyen

s_{m + 1}

...

s_{10}

a tőlük különböző többi szám jegy tetszőleges sorrendben. Legyenek

A

számjegyei az

s_{1}

...

s_{10}

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

s_{i}

B b_{i}

-edik számjegye. Mivel

s_{1}

B

-ben először a

j_{1}

-edik helyen fordul elő,

b_{1} \geq j_{1}

. Belátjuk, hogy tetszőleges

k \leq m

mellett

b_{k} \geq j_{k}

. Ha ugyanis ez nem volna így, válasszuk

k

-nak azt a legkisebb indexet, amelyre

b_{k} < j_{k}

. Akkor

b_{k - 1} \geq j_{k - 1}

, tehát

A

elképzelt előállításában

s_{k - 1}

-et vagy

B j_{k - 1}

-edik jegyeként, vagy azután jelöljük ki. Akkor viszont nem találhatjuk meg

B

-ben ezután, de még

j_{k}

előtt

s_{k}

-t, hiszen a konstrukciónk szerint

j_{k - 1}

után

B

első

s_{k}

-val egyenlő számjegye a

j_{k}

-adik volt. Tehát

b_{m} \geq j_{m}

, de

m

definíciója szerint

B

-ben a

j_{m}

-edik számjegy után nem fordulhat elő az összes, az

s_{1}

s_{2}

...

s_{m}

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:

\begin{matrix} * 7890 * 8798 * 0789 # 7890 * 8798 * 0789 # 7890 987 * \end{matrix}

Itt a

*

az 123456,

#

pedig a 65432123456 számjegysorozatot jelöli. Nem tudjuk, hány jegyből áll a legkisebb univerzális szám.